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

Page one of 4
Fourth Semester B.E Degree exam
(Common to CS and IS)
Model ques. Paper I
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. With the help of a flowchart, discuss the different stages of algorithm design
process. (08 marks)
b. discuss any 3 fundamental issue kinds. (06 marks)
c. Let A be the adjacency matrix of an undirected graph. discuss 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. discuss the worst-case , best-case and avg. case efficiencies of an algorithm
with help of an example. (08 marks)
b. discuss the general plan for analyzing the efficiency of a recursive algorithm.
(08 marks)
c. Solve the subsequent recurrence relations.
i. x(n) = x(n-1) + five 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. discuss how the Divide-and-Conquer strategy is used to multiply large integers.
Apply the identical to calculate 2101 * 1130. (10 marks)
b. discuss the Johnson Trotter algorithm for generating permutations.
Generate the permutations for the provided 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. discuss Transform-and-Conquer technique. elaborate the major variations of this
technique. (06 marks)
b. discuss the various 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 five (b) above. (04 marks)
Page two of 4
6. a. discuss the various kinds 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. elaborate memory functions? discuss how they are used to solve the knapsack
issue . Solve the instance of the knapsack issue beneath. Capacity W= 5
Item Weight Value
1 two $12
2 one $10
3 three $20
4 two $15
(12 marks)
7. a. i. Construct a Huffman code for the subsequent data
Character A B C D -
Probability 0.4 0.1 0.2 0.15 0.15

Earning:   Approval pending.