CS502 Final Term Past Paper 5

FINALTERM EXAMINATION

SPRING 2007 CS502 - FUNDAMENTALS OF ALGORITHMS (Session -5) Marks: 50

Time: 150min

Student Name: ______________________________

Center Name/Code: ______________________________

Exam Date: Thursday, July 05, 2007

INSTRUCTIONS

2. Paste the bitmap image for the tables, diagrams etc while solving your questions
3. This examination is closed book, closed notes, closed neighbors.
4. Some of the examination consists of multiple-choice questions. Choose only one choice as your answer.
5. Use of cell phone during the examination is strictly prohibited, otherwise strict disciplinary action will be taken as per university rules

**WARNING: Please note that Virtual University takes serious action against unfair means. Anyone found involved in cheating will get an `F` grade in this course.

Question Marks Total

Q1. ( Marks: 1 )

T (n)

Is 22n O�2n�?

The recurrence relation of Tower of Hanoi is given below 1 if n1 2T (n�1) 1 if n1 In order to move a tower of 6 rings from one peg to another, how many moves are required?

1. 15
2. 7
3. 63
4. 32

Q2. ( Marks: 1 )

Edge (u, v) is a forward edge if

1. u is a proper descendant of v in the tree
2. v is a proper descendant of u in the tree
3. None of these

Q3. ( Marks: 1 )

1. Yes it is possible
2. No it is not possible
3. None of these

Q4. ( Marks: 1 )

If, in a DFS forest of digraph G = (V, E), f[u] ≤ f[v] for an edge (u, v) Є E then the edge is called

1. Back edge
2. Forward edge
3. Cross Edge
4. Tree Edge
5. None of these

Q5. ( Marks: 1 )

K · K · K · K · k

How can the number of strongly connected components of a graph change if a new edge is added?

1. The number of strongly connected components can be increased.
2. The number of strongly connected components can be reduced.
3. No change will occur.
4. None of these.

Q6. ( Marks: 10 )

Complete the following instance of the optimal matrix multiplication ordering problem. Also give the optimal multiplication order.

p[0]=5 p[1]=4 p[2]=3 p[3]=4 p[4]=5 p[5]=6

Q7. ( Marks: 10 )

For the following given comparison, what are the tradeoffs between adjacency lists and adjacency matrices?

Comparison Faster to test if (x, y) exists. Faster to find vertex degree? Less memory on small graphs? Less memory on big graphs? Edge insertion or deletion? Faster to traverse the graph? Better for most problems? Winner