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

Wednesday, 03 July 2013 08:20Web

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.**

**(**elaborate binomial heaps?Explain with example.

**a)****(**discuss the optimal polygon triangulation techniqu

**b)****e.**[marks:10+10

**4.**

**(**What is dynamic programming? discuss its use in issue solving.

**a)****(**define Huffman's code in brie

**b)****f.**[marks:10+10

UNIT-III

**5.**

**(**discuss the topological sort with example.

**a)****(**discuss the Johnson's algorithm for shortest path. [marks:10+10

**b)****6.**Write Prims algorithm for finding minimum spanning tree.Analyse its time complexity. Compare it with Krushkal's algorithm. [marks:20

UNIT IV

**7.**

**(**elaborate flow networks? discuss their use in brief.

**a)****(**discuss the bitnic sorting network. [marks:10+10

**b)****8.**Write short notes on:

**(**Comparision network

**a)****(**Merging network [marks:10+10

**b)**Earning: Approval pending. |