DAA TUTORIALS

UNIT – I

TUTORIAL - I

1. How can we modify almost any algorithm to have a good best case running time?
2. If f(n)=a0+a1n+a2n2+……………………………….+amnm is any polynomial of degree m then then
prove that f(n)=O(nm)
3. If f(n)=a0+a1n+a2n2+……………………………….+amnm is any polynomial of degree m then then
prove that f(n)=θ(nm)
4. For any two functions f(n) and g(n), f(n)=θ(g(n)) if f(n)=O(g(n)) and f(n)= Ω (g(n)).
5. Prove that Oθ (g(n))∩ω(g(n)) is empty set.
6. Prove that log n!= θ(n logn)
7. Prove that n!= O(nn)
8. Prove that Σni=1 log (i) is θ(n log n).

TUTORIAL - II

9. Prove that max (f(n)+g(n))= θ(f(n),g(n))

10. For the following program give a Big-O analysis of the running time in terms of n.
a. S=0;
for(i=0; i<n; i++) {
for(j=0; j<n; j++) {
for(k=0; k<n; k++) {
S++;
}
}
}

b. for(i=0; i<n; i++) {

while(i==n-5){
if (i==10);
i++;
}
}
11. Use mathematical induction to show that when n is an exact power of 2, the solution of
the recurrence

T(n)= { 2 if n=2
2T(n/2)+n if n=2k for k>1

is T(n) =n logn

12. How can you modify quick sort for searching an element in an array. Write pseudo code
and give its complexity.
13. What are the minimum and maximum numbers of elements in heap of height h ?
14. Show that an n-element heap has height Ɩlogn˩
15. Show that q2+(n-q-1)2 achieve a maximum over q=1,2,----------,n-1 when q=0 or q=n-1
16. Given n digit numbers in which each digit can take up to k possible values, Radix_SORT
correctly sorts these numbers in θ(d(n+k)) time.
17. Prove that the worst case running time of shell sort, using shell’s increments is θ(√2).

UNIT - II

1. Prove that a red black tree with n internal nodes has height at most 2log(n+1).
2. Write pseudo code for RIGHT-ROTATE.
3. Show the red black trees that result after successively inserting the keys
I,N,T,R,O,D,U,C,T,I,O,N,A,L,G,O and deleting the keys A,C,T,I,O,N
4. Consider a red black tree formed by inserting n nodes with RB-INSERT. Argue that if n>1,
the tree has at least one red node.
5. Give steps that how to augment a data structure.
6. If n>=1, then for any n-key B-Tree t of height h and minimum degree t>=2,
h<=logt(N+1)/2.
7. State and prove properties of binomial trees.
8. Write a recursive procedure OS-KEY-RANK(T,K) that takes as input an order statics tree
T and a key K and returns the rank of K in the dynamic set represented by T. Assume all
the keys of T are distinct.
9. Using accounting method find the amortized cost for Enqueue and Dequeue operation
in a queue.
10. Find the amortized cost of 8-bit binary counter using aggregate method.
 UNIT - III

TUTORIAL

1. You are given two sorted lists of size m and n. Give an O(logn+logn) time algorithm for
computing the kth smallest element in the union of two lists.
2. Design an algorithm that multiply two n-bit integers, in O(n2) time using divide and
conquer technique. Can we improve the algorithm given by you?
3. Multiply two matrix given below using Strassen’s method.

2 6 9 10 8 10 11
3 2 4 6 9 11 9
10 6 8
21 4 12

4. Prove that if we order the characters in an alphabet so that their frequencies are
monotonically decreasing, then there exists an optimal code whose code word length
are monotonically increasing?
5. Consider the following graph.

6 5 6
A B C D

1 2 2 5 4 5 7

E F G H
1 3 3

a. What is the cost of its minimum spanning tree?

b. How many minimum Spanning trees does it have?
c. Suppose Kruskal’s algorithm is run on this graph. In what order are the edges added
to the MST.
6.

1 2 3

4 8 6 6 2 1 4

5 1 1
a. Run Prim’s algorithm, whenever there is a choice of nodes, always use alphabetic
ordering (eg. Start node A) Draw a table showing the intermediate values of the cost
array.
b. Run Kruskal algorithm on the same graph. Show how the disjoint sets data structure
looks at every intermediate stage.

7. Let G=(V,E) be an undirected Graph. Prove that if all its edge weights are distinct, then it
has a unique minimum spanning tree.
8. Show how to find the maximum spanning tree of a graph that is, the spanning tree of
largest total weight.
9. Suppose Dijkstra’s algorithm is run on the following graph, starting node A. show final
shortest path tree.

1 2 1
A B C D

4 8 6 6 2 1 4

E F G H
5 1 1

10. Find the shortest path using Bellman Ford algorithm from 3 to 1 of the following graph.

a d
2 4 1 2

S C f
-2 -3

3 5 2 1
b e
 11. Find Shortest path from vertex 1 to 6 using graph shown below.

21
1 2
6 10

5 4 2 -3
6

5
3

a.Using Dijkstra Algorithm

b.Using Belman Ford Algorithm

UNIT – IV

TUTORIAL – IV

1. Find optimal solution to the 0/1 Knapsack instant n=7, W=15,

(P1, P2………………… P7)=(10, 5, 15, 7, 6, 18, 3) and
(W1, W2…………… W7)=(2, 3, 5, 7, 1, 4, 1)

2. Write an algorithm (Floyd Warshal) and explain it using following graph. You are also
required to find its complexity
 2 3 4
2 6

1
1 6
3 4 7 4

8 6 2
3 5

3. Find the Hamilton Circuit in the following graph using back tracking.
A B C D

I J
H
G F E
L
4. Give a dynamic programming solution for the subset sum problem. Analyze the
complexity of the algorithm.
5. Explain Dynamic programming. Apply it on Matrix –Chain multiplication. Analyze the
complexity of the algorithm. Find Matrix Multiplication for following two matrices

3 8 6 9 8 6 3
3 2 9 4 9 4 2
3 6 4 8 10 7 4
2 5 3

6. Run N-Queen algorithm for n=5. Tabulate the no of solutions.

7. Let W={5, 7, 10, 12, 15, 18, 20} and M=35. Find all possible subsets of w that sum to m.
Do this using Sum-of –subset algorithm. Draw the portion of state space tree that is
generated.
8. What do you mean by graph coloring. Explain the algorithm using following graph where
n=3.
 A
B E

C D

9. Distinguish Divide and Conquer and Dynamic programming approach. Explain assembly
line scheduling using following graph.

7 9 8 3

2 6
2 4 6

2 3 4 2
4

8 2 9 1

10. Find solution of TSP defined by the edge length Matrix X using Dynamic programming
method approach.

0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0

UNIT – IV
 TUTORIAL

1. Describe the generalization of the FFT procedure to the case in which n is a power of 3.
Give a recurrence for the running time, and solve the recurrence.
2. Show how to implement FFT algorithm with the bit reversal permutation occurring at
the end, rather than at the beginning, of the computation, (Hint-consider the inverse of
DFT
3. Construct the string matching automation for the pattern P=aabab and illustrate its
operation on the text string T=aaababaabaababaab
4. Draw a state transition diagram for a string matching automation for pattern
Ababbabbababbababbabb over the alphabets Σ={a,b}
5. Suppose that all characters in the pattern P are different. Show how to accelerate
NAÏVE-STRING-MATCHER to run in time O(n) on n character text T.
6. State and prove overlapping –Suffix lemma.
7. Working modulo q=11, how many spurious hits does the Rabin Karp matcher encounter
in the text T=3141592653589793 when .looking for a pattern P=26
8. Compute the prefix function π for the pattern ababbabbabbababbabb when the
alphabet is Σ={a,b}. Explain also KMP algorithm.
9. Explain Boyer’s Moore string matching algorithm using text T=010010101101 and
pattern P=01011.
10. Prove that the Traveling Salesman problem is NP complete.