Design And Analysis Of Algorithm 2017 – BSc Computer Science Part 3

Paper code: 13524
1524
B.Sc. (Computer Science) (Part 3)
Examination, 2017
Paper No. 2.3
DESIGN AND ANALYSIS OF ALGORITHM

Time: Three Hours] [Maximum Marks: 50

 

Note: Attempt all the five questions. All questions carry equal marks.

1. Attempt any two parts of the following:

(a) Explain the various asymptotic notations used in algorithm design.

(b) Explain Randomized algorithms and their advantages.

(c) Explain binary search with their order traversal with example.

 

2. Attempt any two parts of the following:

(a) Differentiate merge sort with quick sort with example.

(b) How divide and conquer techniques applied to binary trees?

(c) Explain worse case optimal algorithm.

 

3. Attempt any two parts of the following:

(a) Explain about the knapsack problem using back-tracking with example.

(b) Explain Kruskal’s algorithm with proper example.

(c) Write a note on connected components and spanning trees.

 

4. Attempt any two parts of the following:

(a) Explain 8 Queens problem with an example.

(b) Explain Breadth First Search and Traversal with example.

(c) Write down and explain the algorithm to solve all pair’s shortest path problems.

 

5. Explain any two of the following:

(a) LC branch-and-bound algorithm.

(b) Dynamic programming

(c) Multistage graphs

(d) Explain graph coloring with following graph:

………………END………………