Guru Nanak Dev University 2007-5th Sem B.E Computer Science DESIGN AND ANALYSIS OF ALGORITHMS (CS-307) (-2k7)_ - Question Paper

2117

B.Tech (Comp. Sc. & Engg.)/M.Tech (Computer Science and Engineering) 5th Semester

DESIGN AND ANALYSIS OF ALGORITHM

Paper - CS-307

Time Allowed - 3 Hours
Maximum Marks : 100

Note : Attempt any 5 ques.. All ques. carry equal marks.

1. (a) obtain a comparison tree for sorting 6 elements that has all external nodes on levels 10 and 11 using lower bound. (15)
(b) elaborate the important properties of a good algorithm. (5)

2. (a) explain the time and space complexity under both logarithmic and uniform cast criteria for function f(n) = n (raised to power n) . (10)
(b) elaborate non-deterministic polynomial time algorithms? discuss. (10)

3. (a) With the help of examples explain the best and worst cases of Merge sort algorithm. (10)
(b) explain the all pairs shortest path issue using dynamic programming. (10)

4. (a) Write a backtracking algorithm for the knapsack issue using dynamic state space tree. (10)
(b) explain the breadth 1st search algorithm with an example.

5. (a) Illustrate the HeapSort Algorithm to organize the subsequent elements in an ascending order :- (15)
42, 34, 75, 23, 18, 100, 10, 72.
(b) Write an algorithm that multiplies 2 nxn matrices using O(n3) operations.

6. (a) When does a binary search decreases to sequential search using a binary search tree ? provide example and discuss also. (10)
(b) provide an algorithm for overloading the operations + and * in the case of polynomials. (10)

7. (a) Analyze the subsequent statement :-
"An Approximation Scheme whose computing time is a polynomial both in the issue size and in 1/e is a fully polynomial time approximation scheme". (12)
(b) elaborate the issues with combinatorial algorithms ? (8)

8. Write short notes on the subsequent :-
(a) NP Complete issues
(b) N-Queen issue
(c) lowest Cost Search
(d) FIFO bound (20)

Earning:   Approval pending.