# VTU Previous Exam Papers BE CS 4th Sem Analysis and Design of Algorithms February 2005

# VTU Previous Exam Papers BE CS 4th Semester

# Analysis and Design of Algorithms February 2005

**Note: 1. Answer any FIVE full questions. 2. Algorithms should be accompanied by sufficient explanations.**

1. (a) With the help of a flow chart explain the various stages of algorithm design and sis process.

(b) Distinguish between the two common ways to represent a graph. Given the representation of an undirected graph, explain how the following can be ascertained by the representation

i) The graph is complete

ii) The graph has a loop

iii) The graph has an isolated vertex

answer for each of the representations separately.

2. (a) Explain the concept of asymptotic notations/ indicating the normally used nota tions.

(b) Suggest a general plan for analysing the efficiency of non recursive algorithms. Suggest an algorithm to find whether the elements in an array are unique. Analyse it’s efficiency using the method suggested by you.

3. (a) What is a ^{/}bruteforce^{/} method? Under what conditions does the method become desirable?

(b) Discuss whether the travelling sales person problem can be solved by exhaustive search methods.

(c) State the merge sort algorithm and analyse its complexity.

4. (a) Suggest an algorithm based on divide and conquer methodology to multiply two large integers and analyze its performance.

(b) Suggest an algorithm for generating combinational objects based on decrease and conquer methodology.

5. (a) Explain the concept of 2-3 tree. How can keys be inserted into it? Comment on the efficiency of search operations on a 2-3 tree.

(b) With the help of necessary algorithms, explain the bottom up heap sort method of sorting.

6. (a) Explain the concept of hashing as a method of implementing dictionaries. What are the two main methods of resolving collisions? Briefly explain them. (10 Marks)

(b) With help of a Pseudocode, explain Warshall’s algorithm to find the transitive closure of a directed graph. Apply it to the following graph

a | b | c | d |

0 | 1 | 0 | 0 |

0 | 0 | 0 | 1 |

0 | 0 | 0 | 0 |

1 | 0 | 1 | 0 |

7. (a) State and explain Dijkstra’s algorithm to find single source shortest paths.

(b) What is a Huffman tree? Explain an algorithm to construct the Huffman tree.

8. (a) Explain the concept of decision trees for sorting algorithms.

(b) What is backtracking? Explain it’s usefulness with the help of an algorithm. What are the specific areas of its applications?