FINALTERM EXAMINATION
Spring 2010
CS502- Fundamentals of Algorithms (Session - 4)
Time: 90 min
M a r k s: 58
CS502 Question No: 1
An optimization problem is one in which you want to find,
Not a solution
An algorithm
Good solution
The best solution
CS502 Question No: 2
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
CS502 Question No: 3
If a problem is in NP, it must also be in P.
True
False
unknown
CS502 Question No: 4
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)
CS502 Question No: 5
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
CS502 Question No: 6
Maximum number of vertices in a Directed Graph may be |V2|
True
False
CS502 Question No: 7
The Huffman algorithm finds a (n) _____________ solution.
Optimal
Non-optimal
Exponential
Polynomial
CS502 Question No: 8
The Huffman algorithm finds an exponential solution
True
False
CS502 Question No: 9
The Huffman algorithm finds a polynomial solution
True
False
CS502 Question No: 10
The greedy part of the Huffman encoding algorithm is to first find two nodes with larger frequency.
True
False
CS502 Question No: 11
The codeword assigned to characters by the Huffman algorithm have the property that no codeword is the postfix of any other.
True
False
CS502 Question No: 12
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
CS502 Question No: 13
Shortest path problems can be solved efficiently by modeling the road map as a graph.
True
False
CS502 Question No: 14
Dijkestra’s single source shortest path algorithm works if all edges weights are non-negative and there are negative cost cycles.
True
False
CS502 Question No: 15
Bellman-Ford allows negative weights edges and negative cost cycles.
True
False
CS502 Question No: 16
The term “coloring” came form the original application which was in architectural design.
True
False
CS502 Question No: 17
In the clique cover problem, for two vertices to be in the same group, they must be adjacent to each other.
True
False
CS502 Question No: 18
Dijkstra’s algorithm is operates by maintaining a subset of vertices
True
False
CS502 Question No: 19
The difference between Prim’s algorithm and Dijkstra’s algorithm is that Dijkstra’s algorithm uses a different key.
True
False
CS502 Question No: 20
Consider the following adjacency list:
Which of the following graph(s) describe(s) the above adjacency list
CS502 Question No: 21
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
CS502 Question No: 22
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
CS502 Question No: 23
Merge sort is stable sort, but not an in-place algorithm
True
False
CS502 Question No: 24
In counting sort, once we know the ranks, we simply _________ numbers to their final positions in an output array.
Delete
copy
Mark
arrange
CS502 Question No: 25
Dynamic programming algorithms need to store the results of intermediate sub-problems.
True
False
CS502 Question No: 26
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)
O (1)
O (n2)
O (n3)
CS502 Question No: 27 ( M a r k s: 2 )
Give a detailed example for 2-d maxima problem.
CS502 Question No: 28 ( M a r k s: 2 )
Differentiate between back edge and forward edge.
CS502 Question No: 29 ( M a r k s: 2 )
How the generic greedy algorithm operates in minimum spanning tree
CS502 Question No: 30 ( M a r k s: 2 )
What are two cases for computing assuming we already have the previous matrix
using Floyed-Warshall algorithm
CS502 Question No: 31 ( M a r k s: 3 )
Describe Minimum Spanning Trees Problem with examples.
CS502 Question No: 32 ( M a r k s: 3 )
What is decision problem, also explain with example
CS502 Question No: 33 ( M a r k s: 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.
CS502 Question No: 34 ( M a r k s: 5 )
Suppose you could reduce an NP-complete problem to a polynomial time problem in polynomial time. What would be the consequence
CS502 Question No: 35 ( M a r k s: 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]
CS502 Question No: 36 ( M a r k s: 5 )
What is the cost of the following graph
Spring 2010
CS502- Fundamentals of Algorithms (Session - 4)
Time: 90 min
M a r k s: 58
CS502 Question No: 1
An optimization problem is one in which you want to find,
Not a solution
An algorithm
Good solution
The best solution
CS502 Question No: 2
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
CS502 Question No: 3
If a problem is in NP, it must also be in P.
True
False
unknown
CS502 Question No: 4
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)
CS502 Question No: 5
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
CS502 Question No: 6
Maximum number of vertices in a Directed Graph may be |V2|
True
False
CS502 Question No: 7
The Huffman algorithm finds a (n) _____________ solution.
Optimal
Non-optimal
Exponential
Polynomial
CS502 Question No: 8
The Huffman algorithm finds an exponential solution
True
False
CS502 Question No: 9
The Huffman algorithm finds a polynomial solution
True
False
CS502 Question No: 10
The greedy part of the Huffman encoding algorithm is to first find two nodes with larger frequency.
True
False
CS502 Question No: 11
The codeword assigned to characters by the Huffman algorithm have the property that no codeword is the postfix of any other.
True
False
CS502 Question No: 12
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
CS502 Question No: 13
Shortest path problems can be solved efficiently by modeling the road map as a graph.
True
False
CS502 Question No: 14
Dijkestra’s single source shortest path algorithm works if all edges weights are non-negative and there are negative cost cycles.
True
False
CS502 Question No: 15
Bellman-Ford allows negative weights edges and negative cost cycles.
True
False
CS502 Question No: 16
The term “coloring” came form the original application which was in architectural design.
True
False
CS502 Question No: 17
In the clique cover problem, for two vertices to be in the same group, they must be adjacent to each other.
True
False
CS502 Question No: 18
Dijkstra’s algorithm is operates by maintaining a subset of vertices
True
False
CS502 Question No: 19
The difference between Prim’s algorithm and Dijkstra’s algorithm is that Dijkstra’s algorithm uses a different key.
True
False
CS502 Question No: 20
Consider the following adjacency list:
Which of the following graph(s) describe(s) the above adjacency list
CS502 Question No: 21
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
CS502 Question No: 22
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
CS502 Question No: 23
Merge sort is stable sort, but not an in-place algorithm
True
False
CS502 Question No: 24
In counting sort, once we know the ranks, we simply _________ numbers to their final positions in an output array.
Delete
copy
Mark
arrange
CS502 Question No: 25
Dynamic programming algorithms need to store the results of intermediate sub-problems.
True
False
CS502 Question No: 26
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)
O (1)
O (n2)
O (n3)
CS502 Question No: 27 ( M a r k s: 2 )
Give a detailed example for 2-d maxima problem.
CS502 Question No: 28 ( M a r k s: 2 )
Differentiate between back edge and forward edge.
CS502 Question No: 29 ( M a r k s: 2 )
How the generic greedy algorithm operates in minimum spanning tree
CS502 Question No: 30 ( M a r k s: 2 )
What are two cases for computing assuming we already have the previous matrix
using Floyed-Warshall algorithmCS502 Question No: 31 ( M a r k s: 3 )
Describe Minimum Spanning Trees Problem with examples.
CS502 Question No: 32 ( M a r k s: 3 )
What is decision problem, also explain with example
CS502 Question No: 33 ( M a r k s: 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.
CS502 Question No: 34 ( M a r k s: 5 )
Suppose you could reduce an NP-complete problem to a polynomial time problem in polynomial time. What would be the consequence
CS502 Question No: 35 ( M a r k s: 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]
CS502 Question No: 36 ( M a r k s: 5 )
What is the cost of the following graph
