Fourth Semester B.

E Degree Examination (Common to CS and IS) Model Question Paper I 06CS43 Analysis and Design of Algorithms Note: Answer any FIVE Full questions, selecting at least TWO Questions from each PART

Time: 3 Hours

Maximum marks : 100

PART -A 1. a. With the help of a flowchart, explain the various stages of algorithm design process. (08 marks) b. Explain any three fundamental problem types. (06 marks) c. Let A be the adjacency matrix of an undirected graph. Explain what properties of the matrix indicate that i. The graph is complete ii. The graph has a loop iii. The graph has an isolated vertex (06 marks) 2. a. Explain the worst-case , best-case and average case efficiencies of an algorithm with help of an example. (08 marks) b. Explain the general plan for analyzing the efficiency of a recursive algorithm. (08 marks) c. Solve the following recurrence relations. i. x(n) = x(n-1) + 5 for n >1 , x(1)=0 ii. x(n) = 3x(n-1) for n > 1, x(1) =4 (04 marks) 3. a. What is brute-force method? Write a brute-force string matching algorithm. Analyze its complexity. (08 marks) b. Write the quick sort algorithm. Analyze its efficiency. Apply the algorithm to sort the list { 4, 1, 6, 3, 9, 2, 7, 5}. (12 marks) 4. a. Explain how the Divide-and-Conquer strategy is used to multiply large integers. Apply the same to compute 2101 * 1130. (10 marks) b. Explain the Johnson Trotter algorithm for generating permutations. Generate the permutations for the given set {1, 2, 3, 4} by i. Bottom-up minimal change algorithm ii. The Johnson Trotter algorithm iii. The lexicographic order algorithm (10 marks) PART -B 5. a. Explain Transform-and-Conquer technique. What are the major variations of this technique. (06 marks) b. Explain the different rotations of AVL tree. Construct an AVL tree for the input sequence 3,6,5,1,2,4 (10 marks) c. Construct a 2-3 tree for the data of 5 (b) above. (04 marks)

Page 1 of 4

6. a. Explain the different types of hashing. For the input 30,20,56,75,31,19 and hash function h(K) = 2K mod 11 , construct the open hash table. (08 marks) b. What are memory functions? Explain how they are used to solve the knapsack problem . Solve the instance of the knapsack problem below. Capacity W= 5 Item Weight Value 1 2 $12 2 1 $10 3 3 $20 4 2 $15 (12 marks) 7. a. i. Construct a Huffman code for the following data Character A B C D Probability 0.4 0.1 0.2 0.15 0.15 ii. Encode the text ABACABAD using the code of (i) above. iii. Decode the text whose encoding is 10001011100101 with the code of (i) above. (10 marks) b. What are decision trees? Explain the concept of decision trees for sorting algorithms. (10 marks)

8. a. Distinguish between P, NP and NP-complete problems. Give examples for each category. (10 marks) b. Apply backtracking to solve the following instance of the subset sum problem S={5,1,4,3} and d=11. (10 marks)

Page 2 of 4

Fourth Semester B.E Degree Examination (Common to CS and IS) Model Question Paper II 06CS43 Analysis and Design of Algorithms Note: Answer any FIVE Full questions, selecting at least TWO Questions from each PART

Time: 3 Hours PART -A 1. a) b) c)

Maximum marks : 100

2.

a) b)

c) 3. a) b)

4.

a)

Explain the notion of algorithm and its important characteristics with the help of an algorithm. (06 Marks) Write an algorithm to check whether the given number is an Armstrong number or not.(Ex: 13+53+33=153) (06 Marks) Briefly explain the following terms(08 Marks) i) Dictionary ii) Stable algorithm iii) ADT iv) First child next sibling representation of trees Explain the various asymptotic notations with examples. (08 Marks) Use the informal definitions of O, O, ? to determine whether the following assertions are true or false. (06 Marks) i) n(n+1)/2 O(n3) ii)n(n+1)/2 O(n2) iii) n(n+1)/2 ? (n3) iv) n(n+1)/2 O (n) Discuss the algorithm for element uniqueness problem for its efficiency. (06 Marks) Explain selection sort algorithm and its efficiency. (08 Marks) Discuss the merge sort algorithm with recursive tree and discuss its efficiency. Apply the same algorithm to sort the list {4,6,1,3,9,5,2,7}. (12 Marks) Briefly explain Strassens matrix multiplication. Obtain its (12 Marks) complexity. Apply the algorithm to multiply the given 2 matrices. 1 3 2 4 5 7 6 8

b)

Differentiate between DFS and BFS tree traversals. Explain, with an example, how DFS algorithm can be used to obtain the topological sorting (08 Marks) PART -B Write and explain the Heap sort algorithm using top-down approach. Using this algorithm, sort the elements {M,O,R,N,I,N,G} in alphabetical order. (10 Marks) Explain the Boyer-Moore algorithm for string matching with an example. (10 Marks)

5.

a)

b)

Page 3 of 4

a) b)

Construct the open hash table and closed hash table for the input: 30,20,56,75,31,19 using the hash function h(k)=k mod 11. (08 Marks) State all-pairs shortest path algorithm. Using it, solve the (12 Marks) following: 0 6 8 8 3 2 0 8 8 8 8 3 0 2 8 1 2 4 0 8 8 8 8 3 0

7.

a)

What is Greedy technique? Explain how the different steps of this technique are taken care in generating a minimum spanning tree through a sequence of expanding sub trees. Apply this algorithm to the following graph: (10 Marks) b a 5 3 1 c a 4 6

a a

d a

e a

b) 8. a) b)

Explain the concept of Decision tree for searching the sorted array. (10 Marks) Distinguish between P,NP and NP complete problems. Give examples for each category. (10 Marks) Solve the following instance of Assignment problem using Branch-Bound technique (10 Mraks) Job1 9 6 5 7 Job2 2 4 8 6 Job3 7 3 1 9 Job4 8 7 8 4

Page 4 of 4