# VU CS502- Fundamentals Of Algorithms FinalTerm Solved Unsolved Past Papers Fall 2008

**FINALTERM EXAMINATION**

**Fall 2008**

**CS502- Fundamentals of Algorithms (Session – 1)**

**Question No: 1 ( Marks: 1 ) – Please choose one**

_______________ is a graphical representation of an algorithm

- notation
- Flowchart
- Asymptotic notation
- notation

**Question No: 2 ( Marks: 1 ) – Please choose one**

Which of the following is calculated with **bigo notation**?

- Lower bounds
- Upper bounds
- Both upper and lower bound
- Medium bounds

**Question No: 3 ( Marks: 1 ) – Please choose one**

Merge sort makes two recursive calls. Which statement is true after these recursive calls

finish, but before the merge step?

- The array elements form a heap
- Elements in each half of the array are sorted amongst themselves
- Elements in the first half of the array are less than or equal to elements in the second half of the array
- None of the above

**Question No: 4 ( Marks: 1 ) – Please choose one**

Who invented Quick sort procedure?

- Hoare
- Sedgewick
- Mellroy
- Coreman

**Question No: 5 ( Marks: 1 ) – Please choose one**

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

*O*(log*n*)*O*(*n*)*O*(*n*log*n*)*O*(2*n*)

**Question No: 6 ( Marks: 1 ) – Please choose one**

Consider the following Huffman Tree

The binary code for the string **TEA **is

- 10 00 010
- 011 00 010
- 10 00 110
- 11 10 110

**Question No: 7 ( Marks: 1 ) – Please choose one**

If a graph has v vertices and e edges then to obtain a spanning tree we have to delete v edges.

- v
- e + 5 edges
- v + e edges.
- None of these

**Question No: 8 ( Marks: 1 ) – Please choose one**

Can an adjacency matrix for a directed graph ever not be square in shape?

- Yes
- No

**Question No: 9 ( Marks: 1 ) – Please choose one**

One of the clever aspects of heaps is that they can be stored in arrays without using any

_______________.

**Pointers (p #40)**- constants
- variables
- functions

**Question No: 10 ( Marks: 1 ) – Please choose one**

Merge sort requires extra array storage,

**True p #54)**- False

*Mergesort is a stable algorithm but not an in-place algorithm. It requires extra array storage.*

**Question No: 11 ( Marks: 1 ) – Please choose one**

Non-optimal or greedy algorithm for money change takes____________

**O(k) (p#99)**- O(kN)
- O(2k)
- O(N)

**Question No: 12 ( Marks: 1 ) – Please choose one**

The Huffman codes provide a method of encoding data **inefficiently **when coded using

ASCII standard.

- True
**Falase (p# 99**

*The Huffman codes provide a method of encoding data efficiently.*

**Question No: 13 ( Marks: 1 ) – Please choose one**

Using ASCII standard the string abacdaacac will be encoded with __________ bits.

**80 (p# 99**- 160
- 320
- 100

*Consider the string “ abacdaacac”. if the string is coded with ASCII codes, the message length would be10 × 8 = 80 bits.*

**Question No: 14 ( Marks: 1 ) – Please choose one**

Using ASCII standard the string abacdaacac will be encoded with 160 bits.

- True

**False (p# 99)**

**Question No: 15 ( Marks: 1 ) – Please choose one**

Using ASCII standard the string abacdaacac will be encoded with 320 bits.

- True
**False (p# 99)**

**Question No: 16 ( Marks: 1 ) – Please choose one**

Using ASCII standard the string abacdaacac will be encoded with 100 bits.

- True
**False (p# 99)**

**Question No: 17 ( Marks: 1 ) – Please choose one**

Using ASCII standard the string abacdaacac will be encoded with 32 bytes

- True
**False (p# 99)**

**Question No: 18 ( Marks: 1 ) – Please choose one**

The greedy part of the Huffman encoding algorithm is to first find two nodes with

**smallest **frequency.

**True (p# 100)**- False

**Question No: 19 ( Marks: 1 ) – Please choose one**

The greedy part of the Huffman encoding algorithm is to first find two nodes with

**character **frequency

- True

**False (p# 100)**

**Question No: 20 ( Marks: 1 ) – Please choose one**

Huffman algorithm uses a greedy approach to generate an antefix code T that minimizes

the expected length B (T) of the encoded string.

**True (p# 102)**- False

**Question No: 21 ( Marks: 1 ) – Please choose one**

Depth first search is shortest path algorithm that works on un-weighted graphs.

- True

**False (p# 153)**

*The breadth-first-search algorithm we discussed earlier is a shortest-path algorithm that works on un-weighted graphs*

**Question No: 22 ( Marks: 1 ) – Please choose one**

Dijkestra s single source shortest path algorithm works if all edges weights are nonnegative and there are no negative cost cycles.

**True (p# 159)**- False

**Question No: 23 ( Marks: 1 ) – Please choose one**

Dijkestra s single source shortest path algorithm works if all edges weights are negative

and there are no negative cost cycles.

**True (p# 159)**- False

**Question No: 24 ( Marks: 1 ) – Please choose one**

Floyd-Warshall algorithm is a dynamic programming algorithm; the genius of the

algorithm is in the clever recursive formulation of the shortest path problem.

**True (p# 162)**- Flase

**Question No: 25 ( Marks: 1 ) – Please choose one**

Floyd-Warshall algorithm, as in the case with DP algorithms, we avoid recursive

evaluation by generating a table for

*k**ij d*- True
- Flase

the case with DP algorithms, we will avoid recursive evaluation by generating a table **for d(k)ij**

**Question No: 26 ( Marks: 1 ) – Please choose one**

The term coloring came form the original application which was in map drawing.

**True (p# 173)**- False

**Question No: 27 ( Marks: 1 ) – Please choose one**

In the clique cover problem, for two vertices to be in the same group, they must be_______________each other.

- Apart from
- Far from
- Near to
**Adjacent to ( P# 176)**

**Question No: 28 ( Marks: 1 ) – Please choose one**

In the clique cover problem, for two vertices to be in the same group, they must be apart

from each other.

- True
**False ( P# 176)**

**Question No: 29 ( Marks: 1 ) – Please choose one**

The difference between Prims algorithm and Dijkstra s algorithm is that Dijkstra s

algorithm uses a different key.

**True ( P # 156) not sure**- False

**Question No: 30 ( Marks: 1 ) – Please choose one**

The difference between Prim s algorithm and Dijkstra s algorithm is that Dijkstra s

algorithm uses a same key.

- True
**False ( P # 156) not sure**

**Question No: 31 ( Marks: 1 )**

Do you think greedy algorithm gives an optimal solution to the activity scheduling

problem?

**Question No: 32 ( Marks: 1 )**

Define Forward edge

**Question No: 33 ( Marks: 2 )**

Is there any relationship between number of back edges and number of cycles in DFS?

**Question No: 34 ( Marks: 2 )**

What is the common problem in communications networks and circuit designing?

**Question No: 35 ( Marks: 3 )**

Let the adjacency list representation of an undirected graph is given below.

Explain what general property of the list indicates that the graph has an isolated

vertex.

**Question No: 36 ( Marks: 3 )**

Describe Minimum Spanning Trees Problem with examples.

**Question No: 37 ( Marks: 3 )**

Explain the following two basic cases according to Floyd-Warshall Algorithm,

1. Don t go through vertex k at all.

2. Do go through vertex k.

**Question No: 38 ( Marks: 5 )**

Show the result of time stamped DFS algorithm on the following graph. Take node E as a

starting node.

**Question No: 39 ( Marks: 5 )**

Why we need reduction?

**Question No: 40 ( Marks: 10 )**

Run DFS sweep and topological sort on the directed graph defined by the following

adjacency matrix.

**Question No: 41 ( Marks: 10 )**

Consider the ** digraph **on eight nodes, labeled 1 through 8, with eleven directed edges

1 2, 1 4, 2 4, 3 2, 4 5, 5 3 ,5 6, 7 8, 7 1, 2 7,8 7

List the ** strongly connected components **of this digraph.