Dept. of Comp. Sc. And Engg.

,ITER, S'O'A University

Algorithm Design-I (CSE 3131)
Practice Questions
Q-9. (a) for (i=1; i<n; i++) {
j=i;
while ((j>0) && (s[j] < s[j-1])) {
swap(&s[j],&s[j-1]);
j = j-1;
}
}
Identify the goal achieved by the above code. Also give its
running time.

(b) What value is returned by the following function? Express your

answer as a function of n. Give the worst-case running time using
Big Oh notation.
function conundrum(n)
r := 0
for i := 1 to n do
for j := i + 1 to n do
for k := i + j − 1 to n do
r := r + 1
return(r)

(c) Suppose the following algorithm is used to evaluate the polynomial

p(x) = a n x n + a n−1 x n−1 + . . . + a 1 x + a 0
p := a 0 ;
xpower := 1;
for i := 1 to n do
xpower := x ∗ xpower;
p := p + a i ∗ xpower
end
(1) How many multiplications are done in the worst-case? How many
additions?
(2) How many multiplications are done on the average?
(3) Can you improve this algorithm?

Q-8. (a) Consider the following code fragment.

for i=1 to n/2 do
for j=i to n-i do
for k=1 to j do
output ‘‘iter’’
Assume n is even. Let T (n) denote the number of times ‘iter’ is
printed as a function of n.
(1) Express T (n) as three nested summations.
(2) Simplify the summation. Show your work.

(b) For each of the following pairs of functions f (n) and g(n),
determine whether
f (n) = O(g(n)), g(n) = O(f (n)), or both.
(1) f (n) = 2(log n) 2 , g(n) = log n + 1
(2) f (n) = 4n log n + n, g(n) = (n 2 − n)/2
Dept. of Comp. Sc. And Engg.,ITER, S'O'A University
(c) For each of the following functions f find a simple function g
such that f (n) =Θ(g(n)).
(1) f1(n) = (1000)2n + 4n .
(2) f2(n) = n + n log n +√n.

Q-7. (a) Read numbers from a file. Sort them using any sorting algorithm
which runs in nlgn time.
(b) Which sorting algorithm is practically considered as best and why?

(c) Randomization is a powerful tool in algorithm design justify.

Q-6. (a) What is lower bound of sorting?

(b) Suppose you are given an array A of n sorted numbers that has been
circularly shifted k positions to the right. Suppose you know what
k is. Give an O(1) algorithm to find the largest
number in A.
(c) In the above question, suppose you do not know what k is. Give an
O(lg n) algorithm to find the largest number in A. For partial
credit, you may give an O(n) algorithm.

Q-5. (a) For some constant c, T(n) < 2T(n/2) + cn, when n > 2, and
T(2) ≤ c. Show by unrolling the above recurrence that it is
bounded by O(n lg n) when n >1.
(b) Design a recursive algorithm to multiply two integers.

(c) Analyse the above designed algorithm to show that it runs in

O(n lg 3)=O(n 1.59)

Q-4. (a) On the context of divide and conquer how does merge sort differ
from quick sort?

(b) What are different approaches to solve a recurrence relation.

(c) Write the partition function for quicksort.

Q-3. (a) Write the pseudo code for Kruskal's algorithm. Also give its
running time.
(b) Show that the Kruskal's algorithm produces a minimum spanning tree
of graph G.
(c) Show that the Reverse-Delete algorithm produces a minimum spanning
tree of graph G.

Q-2. (a) Write the pseudo code for Prim's algorithm. Also give its running
time.
(b) Show that the Prim's algorithm produces a minimum spanning tree of
graph G.
(c) Can Prim’s and Kruskal’s algorithm yield different minimum
spanning trees? Explain why or why not.

Q-1. (a) Write the BFS algorithm. Also mention its running time.

(b) Prove that if graph G has a topological ordering then G is a DAG.

(c) Suppose an arithmetic expression is given as a tree. Each leaf is

an integer and each internal node is one of the standard
Dept. of Comp. Sc. And Engg.,ITER, S'O'A University
arithmetical operations (+, −, ∗, /). Give an O(n) algorithm for
evaluating such an expression, where there are n nodes in the
tree.

Q0. (a) Write the DFS algorithm. Also mention its running time.

(b) Prove that if graph G is a DAG, then G has a topological ordering.

(c) Write a function to traverse binary search tree and return the ith
node in sorted
order.

Q1. You are a given a unimodal array of n distinct elements, meaning that its
entries are in increasing order up until its maximum element, after which its
elements are in decreasing order. Give an algorithm to compute the maximum
element that runs in O(log n) time.

Q2. You are given a sorted (from smallest to largest) array A of n distinct
integers which can be positive, negative, or zero. You want to decide whether
or not there is an index i such that A[i] = i. Design the fastest algorithm
that you can for solving this problem.

Q3. You are given an n by n grid of distinct numbers. A number is a local

minimum if it is smaller than all of its neighbors. (A neighbor of a number
is one immediately above, below, to the left, or the right. Most numbers have
four neighbors; numbers on the side have three; the four corners have two.)
Use the divide-and-conquer algorithm design paradigm to compute a local
minimum with only O(n) comparisons between pairs of numbers. (Note: since
there are n2 numbers in the input, you cannot afford to look at all of them.
Hint: Think about what types of recurrences would give you the desired upper
bound.)

Q4. Write a function to perform integer division without using either the /
or * operators. Find a fast way to do it.

Q5. An inversion of a permutation is a pair of elements that are out of

order. Show that a permutation of n items has at most n(n - 1) / 2
inversions. Which permutation(s) have exactly n(n - 1) / 2 inversions?

Q6. Stable sorting algorithms leave equal-key items in the same relative
order as in the original permutation. Explain what must be done to ensure
that mergesort is a stable sorting algorithm.

Q7. Suppose that you are given a sorted sequence of distinct integers {a1, a2,
…, an}. Give an O(lg n) algorithm to determine whether there exists an i index
such as ai = i. For example, in {-10, -3, 3, 5, 7}, a 3 = 3. In {2, 3, 4, 5, 6,
7}, there is no such i.

Q8. The Floyd-Warshall algorithm for finding all pairs shortest path-length
is as follows:

for k=1 to n do

for p = 1 to n do
Dept. of Comp. Sc. And Engg.,ITER, S'O'A University
for q = 1 to n do

if Dk+1 pq > Dk pk + Dk kq then do

Dk+1 pq := Dk pk + Dk kq

a. What is n and what is the initialization step in the algorithm?

b. What does the algorithm return, or where is the final result stored?

c. Describe how would you modify the algorithm in order to obtain the actual
shortest path, in addition to the shortest path-length?

Q9. 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(lgn) algorithm to find the
largest number in A.
Q10. The mode of a set of numbers is the number that occurs most frequently
in the set. The set (4,6,2,4,3,1) has a mode of 4. Give an efficient and
correct algorithm to compute the mode of a set of n numbers.

Q11. Consider the following code:

// A recursive search function that returns location of x in

// given array arr[l..r] if present, otherwise -1

int Search(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid1 = l + (r - l)/3;
int mid2 = mid1 + (r - l)/3;

// If x is present at the mid1

if (arr[mid1] == x) return mid1;

// If x is present at the mid2

if (arr[mid2] == x) return mid2;

// If x is present in left one-third

if (arr[mid1] > x) return Search(arr, l, mid1-1, x);

// If x is present in right one-third

if (arr[mid2] < x) return Search(arr, mid2+1, r, x);

// If x is present in middle one-third

return Search(arr, mid1+1, mid2-1, x);
}
// We reach here when element is not present in array return -1;
Dept. of Comp. Sc. And Engg.,ITER, S'O'A University
}
a. Explain the approach followed in the above code for searching?
b. Find out its time complexity.
c. Compare the above logic with binary search algorithm.

Q12. Given a sorted array in which all elements appear twice (one after one)
and one element appears only once. Find the element that appears once in
O(log n) complexity.
Example:
Input: arr[] = {1, 1, 3, 3, 4, 5, 5, 7, 7, 8, 8}

Output: 4

Input: arr[] = {1, 1, 3, 3, 4, 4, 5, 5, 7, 7, 8}

Output: 8

(Hint: We can use Binary Search)

Q13. Given an array of 1s and 0s which has all 1s first followed by all 0s.
Find the number of 0s. Count the number of zeroes in the given array.

Examples:
Input: arr[] = {1, 1, 1, 1, 0, 0}

Output: 2

Input: arr[] = {1, 0, 0, 0, 0}

Output: 4

Input: arr[] = {0, 0, 0}

Output: 3

Input: arr[] = {1, 1, 1, 1}

Output: 0

(Hint: we can use Binary Search to find the first occurrence of 0)

Q14. Given an array of integers. Find a peak element in it. An array element
is peak if it is NOT smaller than its neighbors. For corner elements, we need
to consider only one neighbor. For example, for input array {5, 10, 20, 15},
20 is the only peak element. For input array {10, 20, 15, 2, 23, 90, 67},
there are two peak elements: 20 and 90. Note that we need to return any one
peak element.
Following corner cases give better idea about the problem.
1) If input array is sorted in strictly increasing order, the last element is
always a peak element. For example, 50 is peak element in {10, 20, 30, 40,
50}.
2) If input array is sorted in strictly decreasing order, the first element
is always a peak element. 100 is the peak element in {100, 80, 60, 50, 20}.
3) If all elements of input array are same, every element is a peak element.
It is clear from above examples that there is always a peak element in input
Dept. of Comp. Sc. And Engg.,ITER, S'O'A University
array in any input array.
A simple solution is to do a linear scan of array and as soon as we find a
peak element, we return it. The worst case time complexity of this method
would be O(n).
Can we find a peak element in worst time complexity better than O(n)?
We can use Divide and Conquer to find a peak in O(Logn) time. The idea is
Binary Search based, we compare middle element with its neighbors. If middle
element is not smaller than any of its neighbors, then we return it. If the
middle element is smaller than the its left neighbor, then there is always a
peak in left half (Why? take few examples). If the middle element is smaller
than the its right neighbor, then there is always a peak in right half (due
to same reason as left half).
Q15. Given an n x n matrix, where every row and column is sorted in non-
decreasing order. Print all elements of matrix in sorted order.
Example:
Input: mat[][] = { {10, 20, 30, 40},

{15, 25, 35, 45},

{27, 29, 37, 48},

{32, 33, 39, 50},

};

Output:

Elements of matrix in sorted order

10 15 20 25 27 29 30 32 33 35 37 39 40 45 48 50

Q16. Given k sorted arrays of size n each, merge them and print the sorted
output.

Example:
Input:

k = 3, n = 4

arr[][] = { {1, 3, 5, 7},

{2, 4, 6, 8},

{0, 9, 10, 11}} ;

Output: 0 1 2 3 4 5 6 7 8 9 10 11

Q17. Find a Mother Vertex in a Graph.

What is a Mother Vertex?

A mother vertex in a graph G = (V,E) is a vertex v such that all other
vertices in G can be reached by a path from v.
Example :
Dept. of Comp. Sc. And Engg.,ITER, S'O'A University
Input : Below Graph

Output : 5

There can be more than one mother vertices in a graph. We need to output
anyone of them. For example, in the below graph, vertices 0, 1 and 2 are
mother vertices.

We strongly recommend you to minimize your browser and try this yourself
first.
How to find mother vertex?

 Case 1:- Undirected Connected Graph : In this case, all the vertices are
mother vertices as we can reach to all the other nodes in the graph.
 Case 2:- Undirected/Directed Disconnected Graph : In this case, there is
no mother vertices as we cannot reach to all the other nodes in the
graph.
 Case 3:- Directed Connected Graph : In this case, we have to find a
vertex -v in the graph such that we can reach to all the other nodes in
the graph through a directed path.
A Naive approach :
Dept. of Comp. Sc. And Engg.,ITER, S'O'A University
A trivial approach will be to perform a DFS/BFS on all the vertices and find
whether we can reach all the vertices from that vertex. This approach takes
O(V(E+V)) time, which is very inefficient for large graphs.
Can we do better?
We can find a mother vertex in O(V+E) time. The idea is based on Kosaraju’s
Strongly Connected Component Algorithm. In a graph of strongly connected
components, mother verices are always vertices of source component in
component graph. The idea is based on below fact.
If there exist mother vertex (or vertices), then one of the mother vertices
is the last finished vertex in DFS. (Or a mother vertex has the maximum
finish time in DFS traversal).
A vertex is said to be finished in DFS if a recursive call for its DFS is
over, i.e., all descendants of the vertex have been visited.
How does the above idea work?
Let the last finished vertex be v. Basically, we need to prove that there
cannot be an edge from another vertex u to v if u is not another mother
vertex (Or there cannot exist a non-mother vertex u such that u-→v is an
edge). There can be two possibilities.
1.Recursive DFS call is made for u before v. If an edge u-→v exists, then
v must have finished before u because v is reachable through u and a
vertex finishes after all its descendants.
2.Recursive DFS call is made for v before u. In this case also, if an edge
u-→v exists, then either v must finish before u (which contradicts our
assumption that v is finished at the end) OR u should be reachable from
v (which means u is another mother vertex).
Algorithm :
1.Do DFS traversal of the given graph. While doing traversal keep track of
last finished vertex ‘v’. This step takes O(V+E) time.
2.If there exist mother vertex (or vetices), then v must be one (or one of
them). Check if v is a mother vertex by doing DFS/BFS from v. This step
also takes O(V+E) time.

Q18. (a) Describe and Implement Quick sort and show each steps in sorting
the list of numbers. 32, 25, 67, 21, 89, 20,05,89, 82, 99
(b) Discuss the time complexity of the above algorithm in average
case.
(c) Give an efficient algorithm in to find the 2 nd largest key among
the n keys.
Q19. (a) Consider the following two lists : 5,8,12,20,25,28 and
7,9,13,30,35,48 . Exactly how many key comparisons are executed
in order to merge these two lists in sorted order using the
procedure MergeList of the Merge Sort .
(b) Analyze the procedure MergeList used above and find it’s time
complexity.

(c) Suppose the array of n elements is divided into two halves n/3
and 2n/3 at each iteration .Find the time complexity for the
merge sort in the above scenario .
Dept. of Comp. Sc. And Engg.,ITER, S'O'A University

Q20. (a) Let L be the list of n integers, write a algorithm which uses
divide-and-conquer technique to find the smallest and largest
elements in the list.
(b)
Analyze the above algorithm and find the recurrence relation
which gives the time complexity of the above algorithm.
(c)
Solve the above recurrence relation using Master Theorem.
Q21. (a) Use the partitioning idea of quick sort and write an algorithm
that finds the median element of an array of n integers.
(b) Find the time complexity of the above designed algorithm.

(c) Write an algorithm to build a heap in O(n) time.

Q22. (a) Is the path between two vertices in a minimum spanning tree
necessarily a shortest path between the two vertices in the full
graph. Give a proof or a counterexample.
(b) Can Prim’s and Kruskal’s algorithm yield different minimum
spanning trees? Explain why or why not.
(c) The single-destination shortest path problem for a directed graph
requires the shortest path from every vertex to a specified
vertex v . Give an efficient algorithm to solve the single-
destination shortest path problem.

Q23. (a) Give an example of a weighted connected graph G=<V,E> and a

vertex v, such that the minimum spanning tree of G is the same as
the shortest path spanning tree rooted at v.
(b) Give an example of a weighted connected directed graph G=<V,E>
and a vertex v, such that the minimum-cost spanning tree of G is
very different from the shortest path spanning tree rooted at v.
(c) Can the above two trees be completely disjoint?

Q24. (a) Give an algorithm that finds the connected component of a graph.

(b) Implement the above algorithm in the following graph.

(c) Analyze and find the time complexity of the above algorithm.

Q25. (a) Define different data structure used to represent a graph.

(b) Write the adjacency matrix for the following graph

Dept. of Comp. Sc. And Engg.,ITER, S'O'A University
(c) Trace the execution of Dijkstra’s shortest path algorithm to find
the length of shortest path from vertex 1 to vertex 5 in the
above graph.

Q26. You were told that x × y means adding x a total of y times, so

5×4 = 5 + 5 + 5 + 5 = 20.Assume that single addition or
multiplication takes O(1) time.
(a) Write a function to multiply two integers using repeated addition
method.
(b) Prove the function you stated in Q26.(a) is correct.

(c) What is the time complexity of multiplying two numbers

using the repeated addition method, as a function of x or y.

Q27. Suppose you were given the job to write a hash function where the
key is a linked list of positive integers. Assume that the hash
table of any size.
(a) Design a hash function to handle this problem efficiently

(b) Show that the hash function will handle the case of equal key
values in the list without any collision.

(c) Write a procedure corresponding to the hash function you have

stated in Q27.(a).
Q28. (a) Suppose you are given an array of n integers and the elements of
the array are within the range of [1….m], where n > m. Design a
linear time algorithm to find the frequency of each element of
the array.[ Auxiliary space may be taken]

(b) Prove that the algorithm you proposed in Q28.(a) is correct.

(c) Illustrate the operation of the proposed algorithm for the array
of integers [ 1,2, 4,2,1,4,5,4,2,3,3,1,2,5,2,1], where m=5.

Q29. (a) Prove that building max heap from an array of integers will take
O(n) time.

(b) Illustrate the operation of HEAP -EXTRACT -MAX on the heap

A = < 15, 13, 9, 5,12, 8, 7, 4, 0, 6, 2, 1 >.

(c) Illustrate the operation of MAX-HEAP-INSERT( A, 10) on the heap A

= < 15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1 >

Q30. (a) State the control abstraction of divide and conquer strategy.

(b) Design the general recursive equation of the divide and conquer
strategy.

(c) Suppose in the binary search algorithm, the array elements will
be divided into two groups with 1/3 elements in one group and 2/3
elements in other group. Find the time complexity of the binary
search in the above situation.

Q31. The transpose of a directed graph G = (V,E) is the graph G T = (V,ET),

where ET = {(v,u)Є VxV}:(u,v)Є E }. Thus, G T is G with all its edges reversed.
Dept. of Comp. Sc. And Engg.,ITER, S'O'A University
Describe an efficient algorithm for computing GT from G, for both ajjacency
list and adjacency matrix representations of G. Analyze the running time of
your algorithm.

Q32. Consider the algorithm given below:

BFS(G,s)

1 for each vertex u Є V[G] – {s} do

2 dist[u] = infinite

3 pred[u] = NIL

4 dist[s] = 0

5 pred[s] = NIL

6 Q = ɸ

7 QUEUE_INSERT(Q,s)

8 while Q ǂ ɸ

9 u = QUEUE_DELETE(Q)

10 for each v Є adjacency[u] do

11 if dist[u] == infinite then

12 dist[v] = dist[u] + 1

13 pred[v] = u

14 QUEUE_INSERT(Q,v)

a. What are elementary data structures used in the above algorithm? Briefly
mention their uses.

b. Which step in the above pseudocode is used for checking the state of a
vertex (i.e. whether undiscovered or not)?

c. What is the time complexity of step no.11?