DESIGN AND ANALYSIS OF ALGORITHMS (DAA)

FEBRUARY 2007

CLASS TEST I

 

Note:- a) Answer all questions in Part A. Each question carries one mark,

           b) Answer any two questions in Part B. Each question carries seven marks.

 

PART A

 

Q1. Let T(n) = 45n4-5n2+4n-456. Show T(n)= O(T1(n))=q(T1(n))=W(T1(n)) where T1(n)=n4. Obtain G1(n) and G2(n) where T(n)=o(G1(n))=w(G2(n)).

 

http://www.gateguru.org/algorithms/order_notation.pdf

 

 

Q2. Consider a set S={1,2,3,4,5,6} where Si={i} for   1<=i<=6. We want to perform a series of Union (U) and  Find (F) operations: U(1,3),U(4,5),F(2),U(1,2),U(1,6),F(5),U(1,4). Discuss an efficient way of doing these operations and mention the time complexity of your algorithm.

 

Q3. Consider a scheduling problem where the 6 jobs have a profit of (10,34,67,45,23,99) and corresponding deadlines (2,3,1,4,5,3). Obtain the optimum schedule. What is the time complexity of your algorithm? Can you improve it?

 

Q4. We want to store files of lengths (in MB) {12,34,56,73,24,11,34,56,78,91,34,91,45} on three tapes. How should we store them on the three tapes so that the mean retrieval time is minimized?

http://www.gateguru.org/algorithms/optimal_storage_on_tapes.pdf

 

 

Q5. We want to merge some sorted files where the number of records are {12,34,56,73,24,11,34,56,78,91,34,91,45}. What is the optimal way to merge them?

 

Q6. Consider a complete graph of 4 nodes, where the vertices are vi for i between 1 and 4 and the weight of an edge (vi,vj) is i+j. Obtain a minimum spanning tree for the graph. What is the time complexity of your algorithm? Discuss.

 

PART B

 

Q7. Consider a set of elements {12,34,56,73,24,11,34,56,78,91,34,91,45}. Sketch the heapsort algorithm and use it to sort this set. Obtain a derivation for the time complexity of heapsort, both the worst case and average case behaviour.

 

Q8. Consider a set of elements {12,34,56,73,24,11,34,56,78,91,34,91,45}. Sketch the quicksort algorithm and use it to sort this set. Obtain a derivation for the time complexity of quicksort, both the worst case and average case behaviour. How does it compare with mergesort?

http://www.gateguru.org/algorithms/quicksort.pdf

 

Q9. Consider a complete graph of 4 nodes, where the vertices are vi for i between 1 and 4 and the weight of an edge (vi,vj) is 2i+j. Obtain shortest paths from node 1 to all the other nodes using Dijkstra’s single source shortest path algorithm. What is the time complexity of your algorithm? Discuss. What happens when some of the weights of the edges are negative?