Important Questions

Subject:- Design and Analysis of Algorithm

Unit-1

1. The recurrence T(n) = 7T(n/2) + n 2 describe the running time of an algorithm A. A

competing algorithm A has a running time T(n) = aT (n/4) + n 2. What is the largest
integer value for a A is asymptotically faster than A?
2.
i. Solve the recurrence T (n) = 2T(n/2) + n 2 + 2n + 1
ii. Prove that worst case running time of any comparison sort is  (n log n).
3. Use a recursion tree to give an asymptotically tight solution to the recurrence T(n) =
T(n) + T((1 – )n) + cn, where  is a constant in the range 0 <  0 is also a constant.
4. Explain the concepts of quick sort method and analyze its complexity with suitable
example.
5. Explain HEAP SORT on the array. Illustrate the operation HEAP SORT on the array A = {6,
14, 3, 25, 2, 10, 20, 7, 6}
6. What is the time complexity of counting sort? Illustrate the operation of counting sort
on array A = {1, 6, 3, 3, 4, 5, 6, 3, 4, 5}.
 Unit-2

1. Insert the following element in an initially empty RB-Tree. 12, 9, 81, 76, 23, 43, 65, 88, 76,
32, 54. Now delete 23 and 81.
2. Using minimum degree ‘t’ as 3, insert following sequence of integers 10, 25, 20, 35, 30,
55, 40, 45, 50, 55, 60, 75, 70, 65, 80, 85 and 90 in an initially empty B-Tree. Give the
number of nodes splitting operations that take place.
3. What is a binomial heap? Describe the union of binomial heap.
OR
Explain the different conditions of getting union of two existing binomial heaps. Also
write algorithm for union of two binomial heaps. What is its complexity?
4. What is Fibonacci heap? Explain CONSOLIDATE operation with suitable example for
Fibonacci heap.
5. Write a Short note on:
a. Trie
b. Skip List
 Unit-3

1. Discuss convex hull. Give Graham-Scan algorithm to compute convex hull.

OR
What do you mean by convex hull? Describe an algorithm that solves the convex hull
problem. Find the time complexity of the algorithm.
2. Explain “greedy algorithm” Write its pseudo code to prove that fractional Knapsack
problem has a greedy-choice property. Consider the weight and values of item listed
below. Note that there is only one unit of each item. The task is to pick a subset of these
items such that their total weight is no more than 11 kgs and their total value is
maximized. Moreover, no item may be split. The total value of items picked by an optimal
algorithm is denoted by Vopt. A greedy algorithm sorts the items by their value-to-weight
rations in descending order and packs them greedily, starting from the first item in the
ordered list. The total value of items picked by the greedy algorithm is denoted by Vgreedy.
Find the value of Vopt – Vgreedy.
Item I1 I2 I3 I4
W 10 7 4 2
V 60 28 20 24
3. Define minimum spanning tree (MST). Write Prim’s algorithm to generate an MST for any
given weighted graph. Generate MST for the following graph using the Prim’s
algorithm.

4. Explain Greedy programming in brief. Find the shortest path in the below graph from
the source vertex 1 to all other vertices by using Dijkstra’s algorithm.

5. Write down the Bellman Ford algorithm to solve the single source shortest path problem
also write its time complexity.
 Unit-4

1. Discuss knapsack problem with respect to dynamic programming approach. Find the
optimal solution for given problem, w (weight set) = {5, 10, 15, 20} and W (Knapsack size)
= 25 and v = {50, 60, 120, 100}.

2. What do you understand by Dynamic Programming? Give Floyd-Warshall algorithm to

find the shortest path for all pairs of vertices in a graph. Give the complexity of the
algorithm. Apply the same on following graph.

3. What is the sum of subsets problem? Let w={5,7,10,12,15,18,20} and m=35. Find all
possible subsets of w that sum to m using recursive backtracking algorithm for it. Draw
the portion of the state-space tree that is generated.

4. Explain Branch and Bound method in brief. What is travelling salesman problem (TSP)?
Find the solution of following TSP using Branch & Bound method

5. What is backtracking? Explain the method of finding Hamiltonian cycles in a graph using
backtracking method with suitable example.
 Unit-5

1. Explain and Write the Naïve-String string matching algorithm: Suppose the given pattern
p= aab and given text T = a c a a b c. Apply Naïve-String Matching algorithm on above
Pattern (P) and Text (T) to find the number of occurrences of P in T.

2. What is string matching algorithm? Explain Rabin-Karp method with examples.

3. Write KMP algorithm for string matching? Perform the KMP algorithm to search the
occurrences of the pattern abaab in the text string abbabaabaabab.

4. Explain approximation algorithm. Explore set cover problem using approximation

algorithm.

5. Write a short note on following:

i. Randomized Algorithm
ii. NP-Complete and NP Hard
Important questions Daa
algorithm.
Also write down the characteristics of
a. Define the term ALGORITHM.
with dynamic programming.
b. Compare divide and conquer algorithm
linear time complexity.
C Discuss any one sorting algorithm having
d. Write the algorithm of Heapify.
e. Explain asymptotic notations.
bucket sort.
f Explain bucket sort .Also write algorithm for
matrix chain product whose sequence of path
g. Find an optimal parenthesization of a
dimension is (5,10,3, 12,5, 50, 6).
Write the pseudo code of counting sort.
DOG,GIG,BIG, TAG,TUB,BUG,HIT,AIM,TIN. Also
b. Sort the dictionary words using radix sort
write algorithm of radix sort.
programming.
C Compare greedy method with dynamic algorithm:A=(20,35,18,8,14,41,3,39)
the elements of the given array A using shell sort
d. Sort
algorithm:
e. Describe the following sorting techniques with
Mergesort
Heapsort
Master Method:
f Solve the following recurrence using
T(n)=4T(n/3)+n'
T(n)=8T(n/2)+3n
T(n)=4T(n/3)+n²
T(n)=4T(n/2)+n

master method: T(n)=4T(n/3)+n

Solve the following recurrence using :A=(20,35,18,8,14,41,3,39).
Sort the elements of the given array A using shell sort algorithm
b.
Define principle of optimality.
than merge sort?
d. Justifywhy quicksort is better
graph having n vertices.
e Find out Hamiltonian cycles in complete
f Describe convex hull problem. also write its time complexity.
that is most practically used and
g. Name the sorting algorithm
coloring.
h. What do you mean by graph
Describe n- queen problem.
Describe the properties of red black tree .

reverse
in a empty red black tree and delete in the
Insert the node 15,13,12,16,19,23,5,8
order of insertion.
P=1001 in the text
Show the comparisons the naive
string matcher makes for the pattern
time to find the first occurrence of a
T=0000100010010 and show that the worst case
pattern in atext is O(n-m+1)(m-1).
tree over binary search tree.
What are the advantages of red black
Write short notes on the following:
 Approximation algorithms
Fast Fourier Transformation
Randomized algorithms

a. Write the algorithm of Heapify.

sorting techniques:
b. Describe any one of the following
Selection sort

Merge sort
P=26.
T=3141592653589 793 find for pattern
a. Using the Rabin Karp algorthim for text
with modulo q= 11.
finding all pairs shortest paths.
b Describe the Warshalls and Floyd salgorithm for

tree:40,35,22,90,12,45,58,78,67,60 and
a. Insert the following key in a 2-3-4 b- CO3
then delete key 35 and 22 one after other. union
heap? Explain and write an algorithm for
b. What do you mean by binomial
of two binomial heaps.
product whose sequence of
C. Findan optimal parenthesization of a matrix chain
path dimension is (5,10,3,12,5,50,6).

{5,10, 12,13,15,18} and d=30.

(a)State the sum of subsetsproblem. Consider a set
Solve it for obtaining sum of subset.
frequencies:
(b) To build aHuffman tree and find Huffman code for set of
a:50,b:25,c:15,d:40,e:75.
and
Write an algorithm for LCS. Determine LCS for following (10010101)
(010110110).Also writes complexity of LCS.
algorithm and also
(a)What is string matching algorithm? Write KNUTH MORRIS PRATT
calculate the prefix function for the pattern P=ababaaca.
optimal
(b)What do you mean by knapsack problem? Define 0/1 knapsack problem. Find
solution for 0-1 knapsack problem n=3 (w1,w2, w3) =(2,3,3) and (p1,p2,p3)=(1,2,4) , m=6
capacity of k.
 23. 21.22. 20. 19. 18. 17. 16. 15. 14. 12.
13. 11. 10. 9. 8. 7. 6. 5. 4. 3. 2. 1.
Sort Sort Sort Write Array Array Sort running Sort Explain Given What
0.,0A=20, A=6,14,3,25,2,10,20,7,6.
1.75,1,00.2.0,32.5,18,8,14,41,3,39. 10,20,80,90,100,40,30,50. Define
24,55,13,67,88,36,17,61,24,76. algorithm.
Describe A=20,35,18,8,14,41,3,39
prim Describealgorithm Write Define
Write advantage Explain
SortWhatis Explain What What
the the the of of the the b.
the the is the do is
5 heap linked and the binary
elementselements elements elements 7 elements time.
following Huffman using
ii).Write and the elements
stack?Give merge
minimum you an
algorithm elements elements explain andpseudo and algorithm?
sort merge
list. compare
Dijkstra's purpose tree.Explain sort mean
of of of 38,57,62,3,31,65,72,46,16,92 of on the disadvantages
the the for list Alsotree?Create the code
the 11,15,2,13,6 the the
1,9,3,3,4,5,6,7,7,8 sort
algorithm 1. the
of thspanning
e with by
121,070,965,432,012, in breadth
given given giveninsertion given increasing array. explain and Sortfollowingalgorithm of of declaration asymptotic Write
Floyd the givenexample.
method.75,10,20,80,90,100,40,30,50 the
array array array a argue the tree. the
array llustrate for first Floyd of linear array
sort different Huffman following warshall characteristics
A A Asort. r sequentiat
A order the upon algorthims fosearch
warshall of notation?
using using using using using sort merge finding sequential A
the using all.
Explain 577, using types tree its algorithm. the
bucket shell selection bubble merge . using running list to
and
operation sort. in shortest representation selection
functions
683 quick of with depthalgorithm?
sort its the liked increasingdetermine representation of
sort complexity. sort. sort sort the Explain time. algorithm.
sort sort counting
of path first sort used
algorthimalgorthim using algorithm tist. following
Also
algorithm technique heapsort 38,57,62,3,31,65,72,46,16,92 its order the withsearch of algorithm in
radix sort. complexities. MST: writebinary of the
help graph
A=75, on numbers. using binary
A=20,35,18,8,14,41,3,39 sort. and Kruskal of time trees. implementation
the quick suitable
traversal
argue array Sort complexitytree.Writethe
sortalgorithm
upon the example.
algorithm.
technique
its following of of
and the stack.