# Analysis and Design of Algorithms Nov 2010

CS 703 Analysis And Design Of Algorithms

(2002 Scheme)

1. (a) What do you mean by analysis of algorithms? Explain various criteria for analyzing algorithms.

(b) Give the significance of asymptotic growth order of a function. Explain the notations used to represent the rate of growth of running time of algorithms.

OR

II.  (a) What do you mean by complexity of an algorithm? Explain worst case complexity and average case complexity.

(b) Explain the significance of recurrence equation. Solve the recurrence equation T{n) = \6T(y,) + n.

III. (a) Write short notes on hashing and hash functions.

(b) Write and explain an algorithm to search an item in array using divide and conquer strategy. Analyze the worst case and average case complexity.

OR

IV. (a) Define Red-Black tree.

(b) Write an algorithm for insertion sort. Analyze its worst case and average case complexity.

V. What do you mean by biconnected components of an undirected graph? With a suitable example, explain bicomponent algorithm and analyze its complexity.

OR

VI. (a) Define graph. Discuss various methods used to represent graphs.

(b) Explain the following with examples :

(i) articulation point

(ii) minimum spanning tree

VII. (a) Explain an algorithm for finding all pair shortest path in a graph.    (8) (b) What do you mean by transitive closure of a graph? Explain WarshalFs algorithm for finding transitive closure.

OR

VI. (a) What is dynamic programming? Illustrate with an example.

(b) Write and analyze an algorithm for constructing optimal binary search tree.

IX. (a) Distinguish between NP-hard and NP-complete problems.

(b) Explain the first fit decreasing strategy for bin packing. Compare it with other strategies.

OR

X.  (a) Explain different strategies applied for traveling sales person’s problem.

(b) Explain the significance of approximation algorithms.