Visvesvaraya Technological University (VTU) 2010-4th Sem B.E Computer Science Analysis and Design of Algorithms CS - Question Paper

4th Semester B.E Degree exam

(Common to CS and IS)


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)

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= five
Item Weight Value
one two $12
two one $10
three three $20
four 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
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)

Earning:   Approval pending.