Visvesvaraya Technological University (VTU) 2006 B.E Computer Science 06CS43 Analysis and Design of Algorithms - Question Paper

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. elaborate decision trees? discuss the concept of decision trees for sorting algorithms.
(10 marks)
8. a. Distinguish ranging from P, NP and NP-complete issues. provide examples for every
category. (10 marks)
b. Apply backtracking to solve the subsequent instance of the subset sum issue
S={5,1,4,3} and d=11. (10 marks)
Page three of 4
Fourth Semester B.E Degree exam
(Common to CS and IS)
Model ques. Paper II
06CS43 Analysis and Design of Algorithms
Note: ans any 5 Full questions, selecting at lowest 2 ques. from every
PART
Time: three Hours Maximum marks : 100
PART -A
1. a) discuss the notion of algorithm and its important characteristics with the
help of an algorithm. (06 Marks)
b) Write an algorithm to check whether the provided number is an Armstrong
number or not.(Ex: 13+53+33=153) (06 Marks)
c) Briefly discuss the subsequent terms- (08 Marks)
i) Dictionary ii) Stable algorithm
iii) ADT iv) 1st child next sibling representation of trees
2. a) discuss the different asymptotic notations with examples. (08 Marks)
b) Use the informal definitions of O, O, ? to determine whether
the subsequent assertions are actual 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)
c) explain the algorithm for element uniqueness issue for its
efficiency. (06 Marks)
3. a) discuss selection sort algorithm and its efficiency. (08 Marks)
b) explain the merge sort algorithm with recursive tree and explain its
efficiency. Apply the identical algorithm to sort the list {4,6,1,3,9,5,2,7}.
(12 Marks)
4. a) Briefly discuss Strassen’s matrix multiplication. find its (12 Marks)
complexity. Apply the algorithm to multiply the provided two matrices.
1 two five 6
3 four X seven 8
b) Differentiate ranging from DFS and BFS tree traversals. Explain, with an example,
how DFS algorithm can be used to find the topological sorting
(08 Marks)
PART -B
5. a) Write and discuss 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)
b) discuss the Boyer-Moore algorithm for string matching with
an example. (10 Marks)
Page four of 4
6 a) 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)
b) State all-pairs shortest path algorithm. Using it, solve the (12 Marks)
following:
0 two eight one 8
6 0 three two 8
8 eight 0 four 8
8 eight two 0 3
3 eight 8 eight 0
7. a) What is Greedy technique? discuss how the various 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 subsequent graph: (10 Marks)
b) discuss the concept of Decision tree for searching the sorted
array. (10 Marks)
8. a) Distinguish ranging from P,NP and NP complete issues. provide examples
for every category. (10 Marks)
b) Solve the subsequent instance of Assignment issue using
Branch-Bound technique (10 Mraks)
Job1 Job2 Job3 Job4
9 two seven 8
6 four three 7
5 eight one 8
7 six nine 4
aa
da
ea
ca
ba
5 3
1
6
6 2
4

Earning:   Approval pending.