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

Q1.
Let T(n) = 45n^{4}-5n^{2}+4n-456. Show T(n)= O(T1(n))=q(T1(n))=W(T1(n)) where T1(n)=n^{4. }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 S_{i}={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 v_{i} for
i between 1 and 4 and the weight of an edge (v_{i},v_{j}) is
i+j. Obtain a minimum spanning tree for the graph. What is the time complexity
of your algorithm? Discuss.

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 v_{i} for
i between 1 and 4 and the weight of an edge (v_{i},v_{j}) 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?