DESIGN ANALYSIS OF ALGORITHMS B. TECH SEM V (2012 -13) (utu previous year question paper)

DESIGN ANALYSIS OF ALGORITHMS B. TECH

 SEM V (2012 -13)

UTTARKHAND TECHNICAL UNIVERSITY

Time : 3 Hours 

Total Marks : 100

SECTION - 1

Attempt any four

1. Is         =O(2n) ? Is 2     O(2 ) ?
2. Arrange the following in order of best to worst efficiency : O(n log n ), O(n ), O(n ), O(n log   ).
3. Give an analysis of worst case running time of quicksort . When does it occur ?
4. Give an array of 8 element which is the worst case for Insertion Sort .
5. Define the asymptotic notations used for best case average case and worst case analysis of algorithms.
6. Show that the solution T(n) = T(           ) + 1 is O( lg n ) .

 SECTION - 2

Attempt any two 

1. (A) Insert the following values one at a time into an initially empty red-black tree 41, 38, 31, 12, 19, 8 (B) Show that, for arbitrarily large values of n , there are red - black tree with n nodes that have height 2 logn - O(1) .
2. Suppose that a node x is inserted into a red-black tree with RB-INSERT and then immediately deleted with RB-DELETED . Is the resulting red-black tree the same as the initial red -black tree ?
3. Insert the following nodes into an empty AVL tree . Show each step and what rotations are needed . Nodes to insert : 10, 40, 35, 25, 60, 30, 80, 50, 27, 28, 38

SECTION - 3 

Attempt any two    

 

1. (A) What is the difference between a pure recursive solution and a dynamic programming solution to a problem ?                                                                                                                                      (B) What do we understand by the "optimal substructure property" in a dynamic programming problem? 
2. Explain N-queens problem with an algorithm. Explain why backtracking is defined as a default procedure of last resort for solving problems .
3. (A) State if backtracking always produces optimal solution.                                                            (B) Describe how to implement a queue using two stacks and O(1) additional memory , so that the amortized time for any enqueue or dequeue operation is O(1) . The only access you have to the stacks is through the standard subroutines PUSH and POP .

SECTION - 4

Attempt any two 

1. Solve the following instance of the single - source shortage paths problem with vertex "v3" as the source .
2. Draw a (simple) directed weighted graph G with 10 vertices and 18 edges ,such that G contains a minimum-weight cycle with at least 4 edges . Show that the Bellman - Ford algorithm will find this cycle .
3. Show how to modify Dijkstra's algorithm for the case when the graph is directed and we want to compute shortage directed paths from the source vertex to all the other vertices . 

SECTION - 5

Attempt any two 

1. (A) How do we establish that a problem is NP-Complete ?                                                            (B)  Given a graph G and vertices s and t, does G contain a walk from s to t such each vertex of G is visited at a once and at most 100 times .
2. What happens when we use the Goemans-Williamson algorithm for MAX-CUT an a triangle ? Square ? Pentagon? Specifically , what can be inferred on the algorithm's ratio and on the integrality ratio of the relaxation ?
3. Show that the Next-Fit algorithm for BP (BIN-PACKING) achieves an asymptotic ratio of 2. Show that FF(1) < NF(1) .

.................................