FINALTERM  EXAMINATION
Spring 2010
CS502- Fundamentals of Algorithms (Session - 4)

 
Time: 90 min
M - 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 - 2 )
 Give a detailed example for 2-d maxima problem.
   
CS502 Question No: 28    ( M - 2 )
 Differentiate between back edge and forward edge.
   
CS502 Question No: 29    ( M - 2 )
 How the generic greedy algorithm operates in minimum spanning tree
   
CS502 Question No: 30    ( M - 2 )
 What are two cases for computing  assuming we already have the previous matrix  using Floyed-Warshall algorithm
   
CS502 Question No: 31    ( M - 3 )
 Describe Minimum Spanning Trees Problem with examples.
   
CS502 Question No: 32    ( M - 3 )
 What is decision problem, also explain with example
   
CS502 Question No: 33    ( M - 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 - 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 - 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 - 5 )
 What is the cost of the following graph

Views: 458

Replies to This Discussion

Thanks

RSS

Discussion Forum

cs502 gdb

Started by +s@m@n j@nn@t+ Aug 6. 0 Replies

CS502 GDB Last Date: 7th Aug, 2018

Started by + caмe4ѕтυdιeѕ.
Last reply
by +s@m@n j@nn@t+ Aug 6. 1 Reply

CS502 Assign # 3 Due Date: 27th July, 2018

Started by + caмe4ѕтυdιeѕ.
Last reply
by Cute S@mra Jul 22. 2 Replies

cs502 assignment no 2 2018

Started by Muhammad Hasan.
Last reply
by +.ïɳnόϲϵᴎԎ ɖόІІ.+ May 30. 1 Reply

SPONSORED LINKS

© 2018   Created by Muhammad Anwar Tahseen.   Powered by

Badges  |  Report an Issue  |  Terms of Service