# VU CS502- Fundamentals Of Algorithms FinalTerm Solved Unsolved Past Papers FALL 2004

FINALTERM EXAMINATION

SEMESTER FALL 2004

CS502-FUNDAMENTALS OF ALGORITHM-3

Please read the following instructions carefully before attempting any of the questions:

1. Attempt all questions. All Questions carry Equal Marks.

2. Do not ask any questions about the contents of this examination from anyone.

a. If you think that there is something wrong with any of the questions, attempt it to the best of your understanding.

b. If you believe that some essential piece of information is missing, make an appropriate assumption and use it to solve the problem.

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

For Teacher’s use only

Question

Q1

Q2

Q3

Q4

Q5

Q6

Q7

Total

Marks

Some results you may need: Σ=+=ninni12)1( , Σ=++=ninnni1232632 , Σ=−−=+nixxxni111)1(

Question No: 1

Marks: 20

Indicate whether true or false. Beware of guessing: correct answer +5pts, no answer 0pts

(a) In Prim’s algorithm, the additional information maintained by the algorithm is the length of

the shortest edge from vertex v to points already in the tree.

A) TRUE

B) FALSE

C) UNKNOWN

(b) Although it requires more complicated data structures, Prim’s algorithm for a

minimum spanning tree is better than Kruskal’s when the graph has a large number of

vertices.

A) TRUE.

B) FALSE

C: UNKNOWN

(c) If a problem is NP-complete, it must also be in NP.

A) TRUE.

B) FALSE

C) UNKNOWN

(d) What is the worst-case runtime complexity of the following C function

int function(int n){

int i, j, k;

k = n;

for(i=-100; i<10*log(n);i++){

k = k/2;

}

for(j=i; j> n; j–){

k=j/2;

}

return k;

}

What order is the execution of this code

a) O(log n)

b) O(n)

c) O(n log n)

d) O(n2)

e) O(n2 log n)

Question No: 4

Marks: 5

Suppose Prim’s algorithm is applied to the weighted graph shown here starting at vertex a to find a minimum cost spanning tree. State the edges that would be added to the tree in the order that they are added. Name an edge using its endpoints, in alphabetical order. For example, the edge joining vertices p and q should be called {p, q}, not {q, p}. Given a choice of edges at any point, choose the one that would be first alphabetically. For example, given the possibility of choosing either {x, z} or {w, y}, you should choose {w, y} (because w proceeds x).

Question No: 5

Marks: 10

Consider the digraph on five nodes, labeled 0 through 4, with six directed edges

0→1, 1→4, 4→0, 0→2, 2→3, 3→2

List the strongly connected components of this digraph.

Question No: 2

Marks: 5

What is the solution to the recurrence T(n) = 2T(n/2)+1, T(1) = 1

T(n) =

Question No: 3

Marks: 5

The first diagram shown below is a tree which is a heap. The items in the heap are now to be sorted using heapsort. The following diagram shows the tree after all items have been sorted. Show the contents of the tree as it would appear after each of the first six passes of heapsort.

Question No: 6

Marks: 10

Consider the following 21 character message that consists of 3 a’s, 7 c’s, 6 t’s, and 5 g’s:

a a c c c c a c t t g g g t t t t c c g g

Are the following 43 bits a possible Huffman encoding of the message above?

0000001111000101010010010010101010111001001

Justify your answer as concisely and rigorously as possible.

Question No: 7

Marks: 20

In the following graph, edges are labeled with upper case letters. Edge weights are given as numbers next to edges.

Recall that Dijkstra’s algorithm finds the shortest path from v1 to all other vertices by adding edges that make shortest paths. For the graph shown above, each edge is bidirectional; that is, you can travel on either direction on it for the same cost. List the edges in the order chosen by Dijkstra’s algorithm.