University of Delhi 2009-2nd Year B.Sc Computer Science (Hons)/ III sem /s / NS -301 ALGORITHMS (NEW COARSE) - Question Paper
This question paper contains 4+2 printed pages]
fr OW I / Your Roll No..L......I.!..6358
B.Sc. (Hons.) / III Sem. / II Yr. / NS H
COMPUTER SCIENCE Paper 301 - ALGORITHMS (New Course)
(Admissions of 2001 and onwards)
Time : 3 Hours Maximum Marks ; 75
(Write your Roll No. on the top immediately on receipt of this question paper.) All questions are compulsory.
. Write the answers of all the _arts of a question together.
Ijgjf During the running of the procedure RAND OMIZED-QUICKSORT, how many calls are made to the random-number generator function in the worst case ? Discuss the best case also. 3
L(ti) Show that there are at most |"n/2A + 1j nodes of height h in any n-element heap. 3
fyj' In a hypothetical situation, suppose that you have coins of denomination (in Rupees) 1, 5 and 8.
The problem is that you have to collect an amount of Rs. 10 using minimum number of coins.
Give a greedy algorithm for solving this problem. 3
___Discuss the optimality of the your greedy
solution for this problem. 2
(b) A sequence of n operations is performed on a data structure. The ith operation costs i if i is an exact power of 2 and 1 otherwise. Use aggregate analysis to determine the amortized cost per operation. 5
3. (a) Use Prims algorithm to find the minimum cost spanning tree of the following graph : 5
(,b) Multiply the following two matrices using Strasson s /
algorithm : 5
"l 6" 4 2
2 3 1 5
4. f{a)J Show that the quicksorts best case running time is 2 (n !g n). When does it occur ? 4
What is the running time of heapsort on an array A of length n that is already sorted in increasing order ? What about decreasing order ? 2
5. (a) Prove that counting sort is stable (you can prove
with the help of an example). 5
/fV Analyze the worst case running time of
L.y
RANDOMIZED-SELECT algorithm. 4
6. 'af What is the maximum number of times rotation
can be performed in a Red-Black tree while inserting a node ? 1
laving value (27) i Red-Black tree (color of the nodes are given adjacent to the nodes, Rfor red color. Bfor black color). 3
tc) Write the pseudocode for RIGHT-ROTATE in a Red-Black tree. . ' 4
Jf>) Insert the node having value {lj in the following
7. Find an optimal parenthesitation of a matrix chain
product whose sequence of dimensions is <20, 10, 50, 5, 30>. 5
Give an optimal Huffman code for the following set of frequencies : 4
Write a non-recursive version of OS-SELECT (x, i.) algorithm, which finds an clement with the ith smallest key in the .subtree rooted at node x. 5
If x is a non-root node in a binomial tree within ,/a binomial heap, how is the degree of a node x compared with its parent ? 2
(a)
v''
Insert a node having value in the binomial heap given below : 2
t/ (c)
head [H]-30)
(d) Delete a node having minimum key from the binomial heap given below : 3
 |
|
P.T.O. |
Show the stepwise running of Breadth First Search on the following graph using vertex E as the sourcc vertex : 5
600
6
6358
|
Attachment: |
| Earning: Approval pending. |
