# VU CS502- Fundamentals Of Algorithms (Session – 4) FinalTerm Solved Unsolved Past Papers Spring 2010

**FINALTERM EXAMINATION**

**Spring 2010**

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

**Time: 90 min**

**Marks: 58**

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

** **An optimization problem is one in which you want to find,

► Not a solution

► An algorithm

► Good solution

** ► The best solution**

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

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

** ► True**

► False

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

** **If a problem is in NP, it must also be in P.

** ► True**

► False

► unknown

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

** **What is generally true of Adjacency List and Adjacency Matrix representations of graphs?

► *Lists *require less space than *matrices *but take longer to find the weight of an edge (v1,v2)

** ► Lists require less space than matrices and they are faster to find the weight of an edge (v1,v2)**

► *Lists *require more space than *matrices *and they take longer to find the weight of an edge (v1,v2)

► *Lists *require more space than *matrices *but are faster to find the weight of an edge (v1,v2)

**Question No: 5 ( 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: 6 ( Marks: 1 ) – Please choose one**

** **Maximum number of vertices in a Directed Graph may be |V^{2}|

** ► True**

► False

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

** **The Huffman algorithm finds a (n) _____________ solution.

** ► Optimal**

► Non-optimal

► Exponential

► Polynomial

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

** **The Huffman algorithm finds an exponential solution

► True

** ► False**

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

** **The Huffman algorithm finds a polynomial solution

► True

** ► False**

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

** **The greedy part of the Huffman encoding algorithm is to first find two nodes with **larger** frequency.

► True

** ► False**

** **

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

** **The codeword assigned to characters by the Huffman algorithm have the property that no codeword is the postfix of any other.

► True

** ► False**

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

** **Huffman algorithm uses a greedy approach to generate a postfix code T that minimizes the expected length B (T) of the encoded string.

► True

** ► False**

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

** **Shortest path problems can be solved efficiently by modeling the road map as a graph.

** ► True**

► False

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

** **Dijkestra’s single source shortest path algorithm works if all edges weights are non-negative and there are negative cost cycles.

► True

** ► False**

** **

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

** **Bellman-Ford allows negative weights edges and negative cost cycles.

► True

** ► False**

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

** **The term “coloring” came form the original application which was in architectural design.

** ► True**

► False

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

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

** ► True**

► False

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

** **Dijkstra’s algorithm is operates by maintaining a subset of vertices

** ► True**

► False

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

** **The difference between Prim’s algorithm and Dijkstra’s algorithm is that Dijkstra’s algorithm uses a different key.

** ► True**

► False

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

** **Consider the following adjacency list:

Which of the following graph(s) describe(s) the above adjacency list?

** ► **

►

►

►

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

** **We do sorting to,

► keep elements in random positions

► keep the algorithm run in linear order

► keep the algorithm run in (log n) order

** ► keep elements in increasing or decreasing order**

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

** **After partitioning array in Quick sort, pivot is placed in a position such that

** ► Values smaller than pivot are on left and larger than pivot are on right**

► Values larger than pivot are on left and smaller than pivot are on right

** ► Pivot is the first element of array**

► Pivot is the last element of array

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

** **Merge sort is stable sort, but not an in-place algorithm

** ► True (p#54)**

► False

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

** **In counting sort, once we know the ranks, we simply _________ numbers to their final positions in an output array.

► Delete

** ► copy (p#57)**

► Mark

► arrange

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

** **Dynamic programming algorithms need to store the results of intermediate sub-problems.

** ► True p#75)**

** **

► False

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

** **A p × q matrix A can be multiplied with a q × r matrix B. The result will be a p × r matrix C. There are (p **.** r) total entries in C and each takes _________ to compute.

** ► O (q) (p= 84)**

► O (1)

► O (n^{2})

► O (n^{3})

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

** **Give a detailed example for 2-d maxima problem.

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

** **Differentiate between back edge and forward edge.

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

** **How the generic greedy algorithm operates in minimum spanning tree?

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

** **What are two cases for computing assuming we already have the previous matrix using Floyed-Warshall algorithm?

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

** **Describe Minimum Spanning Trees Problem with examples.

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

** **What is decision problem, also explain with example?

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

** **Prove that the generic TRAVERSE (S) marks every vertex in any connected graph exactly once and the set of edges (v, parent (v)) with parent (v) ¹F form a spanning tree of the graph.

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

** **Suppose you could reduce an NP-complete problem to a polynomial time problem in polynomial time. What would be the consequence?

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

** **Prove the following lemma,

**Lemma: **Given a digraph G = (V, E), consider any DFS forest of G and consider any edge (u, v) ∈ E. If this edge is a tree, forward or cross edge, then f[u] > f[v]. If this edge is a back edge, then f[u] ≤ f[v]

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

** **What is the cost of the following graph?