Sample Questions – Algorithm Design

1. Define asymptotic notation. Differentiate between Big-O, Big-Ω, and Big-Θ.

2. What is the difference between greedy algorithms and dynamic programming?

3. Define recurrence relation. Give an example.

4. Describe the Divide and Conquer approach. Give one example.

5. Define time complexity and space complexity.

6. Write and solve the recurrence relation for the Quick Sort algorithm.

Prof. Ossama Ismail

 Sample Questions – Algorithm Design
7. Given a weighted graph, explain how Prim's algorithm constructs a Minimum
Spanning Tree (MST).

8. Write a recursive algorithm to find the n-th Fibonacci number.

9. Implement a function to solve the 0/1 Knapsack problem using dynamic

programming.

10. Write an algorithm to count the number of connected components in an undirected

graph.

Prof. Ossama Ismail

 Sample Questions – Algorithm Design
11. Implement binary search and analyze its time complexity.

12. Design an algorithm to check whether a graph is bipartite.

13. Solve the Longest Common Subsequence (LCS) problem using dynamic
programming.

Prof. Ossama Ismail

 Sample Questions – Algorithm Design
14. Write a function to generate all permutations of a string.

15. Design and explain an algorithm for Activity Selection using greedy strategy.

16. Implement a DFS-based topological sort for a Directed Acyclic Graph.

17. Write a function to compute the minimum number of coins needed to make change
for a given value.

Prof. Ossama Ismail

 Sample Questions – Algorithm Design
18. Describe the Randomized QuickSort algorithm.
How does randomization improve the expected performance of QuickSort? Derive its
expected time complexity.

19. Write a randomized algorithm to find the k-th smallest element in an unsorted array.
Analyze its expected time complexity.

In Randomized QuickSort, the pivot is chosen:

A) Always the first element
B) Always the last element
C) Randomly from the array (Answer)
D) Middle of the array

What is the expected time complexity of Randomized QuickSort on an array of size n?

A) O(n²)
B) O(n log n) (answer)
C) O(log n)
D) O(n)

• True or False
• Randomization can improve the average-case performance of certain algorithms. (T)
• Monte Carlo algorithms always produce a correct result, but their running time is variable.
(F)

Prof. Ossama Ismail

 Sample Questions – Algorithm Design
• Randomized algorithms are only useful for sorting problems. (F)
• In Randomized QuickSort, the worst-case time complexity can still be O(n²). (T)
• A Monte Carlo algorithm may produce incorrect answers but always runs in bounded time.
(T)
More Questions

Answers

Prof. Ossama Ismail

 Sample Questions – Algorithm Design
1. Describe the Greedy method and explain its applicability to algorithm design.

2. Design a greedy algorithm for Activity Selection and prove its correctness.

3. Apply the divide and conquer method to find the majority element in an array.

4. Compare the performance of merge sort and quicksort under different inputs.

Prof. Ossama Ismail

 Sample Questions – Algorithm Design
5. Explain the concept of orientation (clockwise, counterclockwise) and how it's used in
computational geometry.

6. Write an algorithm to check if a point lies inside a polygon.

7. Describe any one application of computational geometry in real-world problems.

Prof. Ossama Ismail

 Sample Questions – Algorithm Design

8. What are the advantages and disadvantages of using randomized algorithms?

Algorithms Sample Questions

Question 1:
a. What is the solution to the recursive formula

T(1) = 1 and T(n) = T( 𝑛/2 ) + n ? Explain why?

i. T(n) = Θ(log(n)).
ii. ii. T(n) = Θ(log2 (n)).
iii. iii. T(n) = Θ(n).
iv. iv. T(n) = Θ(n log(n)).
v. v. T(n) = Θ(n2 ).

b. What is the solution to the recursive formula

T(1) = 1 and T(n) = T( 𝑛/2 ) + T( 𝑛/2 ) ? Explain why?

i. T(n) = Θ(log(n)).
ii. ii. T(n) = Θ(log2 (n)).
iii. T(n) = Θ(n).

Prof. Ossama Ismail

 Sample Questions – Algorithm Design
c. Given n balls {b1, b2, . . . ,bn}, each colored either green or red, Get the number of
comparison that is needed to determine the Majority ball, using only pairwise equality
comparisons. (The Majority problem is to find the element that occurs more than half the time
in an array, assuming it exists).

Question 2. TV-Programs
There is a television set and a video recorder. There was made the list of the TV-Programs of one
day, which must be recorded to videotape. Programs must be recorded so that there would be the
least of the tapes.
Each program lasts not less than 10 minutes and not more than one hour. At the beginning of
program advertisement is shown for 1 minute, the time of program contains the time of
advertisement that must be recorded so that there would be the least of the tapes. Write a program
that finds and prints the smallest number of the needful tapes.

The input data is containing four numbers in each line: time of the beginning and the end of the
program, expressed in hours and minutes, HH MM HH MM. Not more than 30 programs are
prepared per day.

Prof. Ossama Ismail

 Sample Questions – Algorithm Design

Question Sixteen: Given an array of n real numbers, consider the problem of finding the maximum
sum in any contiguous subvector of the input. For example, in the array
{ 31, -41, 59, 58, 97, -93, -23, 84}
the maximum is achieved by summing the third through seventh elements, where
59+26+(53)+58+97 = 187. When all numbers are positive, the entire array is the answer, while
when all numbers are negative, the empty array maximizes the total at 0.
a. Give a simple, clear, and correct O(n2)-time algorithm to find the maximum contiguous
sub-vector.

b. Now give a O(n)-time dynamic programming algorithm for this problem. To get partial
credit, you may instead give a correct O(n log n) divide-and-conquer algorithm.

Question 4. Shifted Array

Suppose you are given an array A of n sorted numbers that has been circularly shifted k positions
to the right. For example, {35,42,5,15,27,29} is a sorted array that has been circularly shifted k=2
positions, while {27,29,35,42,5,15} has been shifted k=4 positions.

a. Suppose you know what k is. Give an O(1) algorithm to find the largest number in A.

b. Suppose you do not know what k is. Give an O(log n) algorithm to find the largest number
in A. For partial credit, you may give an O(n) algorithm.

Prof. Ossama Ismail

 Sample Questions – Algorithm Design
Question 5. Point-in-Polygon (PIP):
Consider a polygon made up of n vertices (xi,yi) where i ranges from 0 to n-1. The last vertex
(xn,yn) is assumed to be the same as the first vertex (x0,y0), that is, the polygon is closed. Given a
test point (xp,yp), it is required to do the following :-
Write a program to determine if it is inside, outside, or on the boundary of the polygon. Find the
time complexity of your code.

Question 6.
Adding two Matrices: This example demonstrates adding two 2-dimensional arrays A and B. The
sequential program can be written as follows: (complexity is O (n2)).

for i = 0 to n-1
for j = 0 to n-1
C[i][j] = A[i][j] + B[i][j]

Prof. Ossama Ismail

 Sample Questions – Algorithm Design
Question 7.
1- Consider Insertion-Sort and Merge-Sort. For each algorithm, what will be the
worst case asymptotic upper bound on the running time if you know additionally
that
a) the input is already sorted.
b) the input is reversely sorted.
c) the input is a list containing n copies of the same number.

For each case and each sorting algorithm, state your answer and justify it in one
sentence.

2- Quicksort is guaranteed to run in time O (n log n) so long as the pivot is

a) randomly selected.
b) set to the median of the first, middle, and last array element.
c) set to the median of the array.
d) d) none of the above

3- What are the various factors to be considered in deciding a sorting algorithm?

Factors to be considered in deciding a sorting algorithm are,

1. Programming time
2. Executing time for program
3. Memory or auxiliary space needed for the program’s
environment.

4- What is meant by linear search?

5- What is binary search?

Prof. Ossama Ismail

 Sample Questions – Algorithm Design
6- Write a C program to perform searching operations using linear and binary
search.
7- Compare the quick-sort and merge-sort algorithms in terms of their time and
space complexity. Which is better in terms of time complexity? Which is
better in terms of space complexity?

8- What is the worst-case time for serial search finding a single item in an array?
A. Constant time
B. Logarithmic time
C. Linear time
D. Quadratic time

9- What is the worst-case time for binary search finding a single item in an
array?
A. Constant time
B. Logarithmic time
C. Linear time
D. Quadratic time

10- What additional requirement is placed on an array, so that binary search may
be used to locate an entry?
A. The array elements must form a heap.
B. The array must have at least 2 entries.
C. The array must be sorted.
D. The array's size must be a power of two.

Prof. Ossama Ismail

 Sample Questions – Algorithm Design
Question 8.
Using prim’s or Kruskal’s algorithm solve those graphs and get the
minimum cost of it:

Question Nine:
Apply Dijkstra Algorithm:
2) What is the shortest path to travel from A to F? (Justify you answer)

Question Tweleve:
Assume you have a glass of water with height 10 cm
placed on a horizontal table. Filled with water at height
4cm. Write a code to calculate the angle at which the
water will start to leak from the top of the glass (assume
the rotation at the pivot centered of the cup).

Prof. Ossama Ismail

 Sample Questions – Algorithm Design
Question Thirteen:
Write a formal description or a code to use a pre-made discrete uniform distribution
generator to make a linear function discrete distribution generator. A linear distribution
is the one that follows the equation F(x)=x. i.e., the ratio between the probability of
generating the number 5 to the probability of generating
the number 3 is 5/3.

Question Fourteen:
A spanning tree of a graph is just a subgraph that contains all the vertices and is
a tree. A graph may have many spanning trees. Find the minimum
spanning tree for the following graph:

Prof. Ossama Ismail

 Sample Questions – Algorithm Design
Question Fifteen:
Suppose a computer password consists of four to eight letters and/or digits. How many different
possible passwords are there? Remember
that an upper-case letter is different from a lower-case one. Write an algorithm to generate all
possible passwords. Calculate the complexity of your algorithm?

Question Sixteen:
Given n line segments in the plane, show that determining if any pair of lines segments
intersects has an Ω (n log n) lower bound.

Prof. Ossama Ismail

 Sample Questions – Algorithm Design
Question Seventeen:
Write the merge sorting algorithm and show a step by step implementation upon applying it on
the numbers: 17, 5, 23, 8, 43, 50, 20, and 12. What is the complexity of this algorithm?

Prof. Ossama Ismail