Kurukshetra University 2010 B.E Computer Science and Engineering Design and analysis of algorithm,cse 301E - Question Paper

DESIGN AND ANALYSIS OF ALGORITHM
PAPER CSE 301 E
TIME three HOURS [MAXIMUM MARKS:100]
Note : Attempt 5 ques. in all,selecting atleast onee ques. from every unit.

UNIT I
1. What is heap sort? Write an algorithm to sort elements using heapsort.Show the steps for
the subsequent list:
(40,80,35,90,45,50,70)
Analyse its time complexity and compare it with quick sort. [marks:20
2. What is binary search? Write an algorithm to search an element using binary search with suitable example.Analyse its time complexity and compare it with linear search.[marks:20
UNIT II
3. (a) elaborate binomial heaps?Explain with example.
(b) discuss the optimal polygon triangulation technique. [marks:10+10
4. (a) What is dynamic programming? discuss its use in issue solving.
(b) define Huffman's code in brief. [marks:10+10
UNIT-III
5. (a) discuss the topological sort with example.
(b) discuss the Johnson's algorithm for shortest path. [marks:10+10
6. Write Prims algorithm for finding minimum spanning tree.Analyse its time complexity. Compare it with Krushkal's algorithm. [marks:20
UNIT IV
7. (a) elaborate flow networks? discuss their use in brief.
(b) discuss the bitnic sorting network. [marks:10+10
8. Write short notes on:
(a) Comparision network
(b) Merging network [marks:10+10

Earning:   Approval pending.