Fundamentals of Algorithms (CS502)

1. The Huffman algorithm finds a(n) ________ solution.

   1. Optimal
   2. Non-optimal
   3. Exponential
   4. Polynomial

2. Which is true statement.

   1. Breadth first search is shortest path algorithm that works on un-weighted graphs
   2. Depth first search is shortest path algorithm that works on un-weighted graphs.
   3. Both of above are true.
   4. None of the given

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

   1. True
   2. False

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

   1. True
   2. False

5. You have an adjacency list for G, what is the time compexity to compute Graph transpose G^T?

   1. (V+E)
   2. V.E
   3. V
   4. E

6. Strongly connected components are not affected by reversal of all edges in terms of vertices reachability.

   1. True
   2. False

7. Dynamic Programming is a problem-solving approach in which ________.

   1. Problem is solved in Zero time
   2. Solution is developed only at final stage
   3. Both are correct
   4. Both are incorrect

8. The Huffman algorithm finds an exponential solution

   1. True
   2. False

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

   1. True
   2. False

10. Kruskal's algorithm (choose best non-cycle edge) is better than Prim's (choose best free edge) when the gaph has relatively few edges.

    1. True
    2. False

11. Chain matrix multiplication problem can be solved through ________ strategy.

    1. Dynamic programming
    2. Greedy
    3. Divide and conquer
    4. Sorting

12. Consider three matrices X, Y, Z of dimensions 1 × 2, 2 × 3, 3 × 4 respectively. The number of multiplications of X(YZ) is:

    1. 16
    2. 23
    3. 26
    4. 32

13. The Huffman algorithm finds a polynomial solution.

    1. True
    2. False

14. Heap sort is a/an ________ and ________ sorting algorithm.

    1. Not in-place, not stable one
    2. In-place, stable one
    3. In-place, not stable one
    4. Not in-place, stable one

15. In strong components algorithm, first of all DFS is run for computing finish times of vertices.

    1. True
    2. False

16. Counting sort assumes that the numbers to be sorted are in the range ________.

    1. k to n where n is large
    2. 1 to k where k is small
    3. k to n where k is small
    4. k to n where n is small

17. We can use the optimal substructure property to devise a ________ formulation of the edit distance problem.

    1. Selective
    2. Optimum
    3. Iterative
    4. Recursive

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

    1. True
    2. False

19. If there are Θ (n²) entries in edit distance matrix then each entry E (i, j) takes ________ time to compute.

    1. Θ (n)
    2. Θ (n²)
    3. Θ (1)
    4. Θ (n log n)

20. In kruskal's algorithm, the next edge is added to viable set A, if its adding does not induce a cycle.

    1. True
    2. False

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

    1. True
    2. False
    3. Unknown

22. Radix sort is not a non-comparative integer sorting algorithm.

    1. True
    2. False

23. Dijkstra’s algorithm is operated by maintaining a subset of vertices.

    1. True
    2. False

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

    1. True
    2. False

25. We say that two vertices u and v are mutually ________ if u can reach v and vice versa.

    1. Crossed
    2. Forward
    3. Reachable
    4. Nor Reachable

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

    1. Lists require less space than matrices but take longer to find the weight of an edge (v1,v2)
    2. Lists require less space than matrices and they are faster to find the weight of an edge (v1,v2)
    3. Lists require more space than matrices and they take longer to find the weight of an edge (v1,v2)
    4. Lists require more space than matrices but are faster to find the weight of an edge (v1,v2)

27. Adding an edge to a free tree creates.

    1. A cycle
    2. A complete MST
    3. A partial MST
    4. A shortest path

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

    1. True
    2. False

29. We say that two vertices u and v are mutually not reachable if u can reach v and vice versa.

    1. True
    2. False

30. Diagraphs are not used in communication and transportation networks.

    1. True
    2. False

31. Maximum number of vertices in a Directed Graph may be |V2|

    1. True
    2. False

32. In strong components algorithm, first of all DFS is run for getting ________ times of vertices.

    1. Start
    2. Finish
    3. Both start & finish
    4. None of the given

33. In ________ algorithm, at any time, the subset of edges A forms a single tree.

    1. Kruskal's
    2. Prim's
    3. Both Kruskal's and Prim's
    4. None of the given

34. You have an adjacency list for G, what is the time compexity to compute Graph transpose G^T.?

    1. ? (V + E)
    2. ? (V E)
    3. ?(V)
    4. ?(v^2)

35. The ________ given by DFS allow us to determine whether the graph contains any cycles.

    1. Order
    2. Time stamps
    3. BFS traversing
    4. Topological sort

36. In Dynamic Programming, our approach is to ________.

    1. Develop the solution in a top-down fashion
    2. Express the problem non-recursively
    3. Build the solution in a bottom-up fashion
    4. Input several sub-problems simultaneously

37. By breaking any edge on cycle created in free tree, the free ________ is restored.

    1. Edge
    2. Tree
    3. Cycle
    4. Vertex

38. A free tree with n vertices have exactly n+1 edges.

    1. True
    2. False

39. Networks are ________ in the sense that is possible from any location in the network to reach any other location in the digraph.

    1. Complete
    2. Incomplete
    3. Not graphs
    4. Transportation

40. In Prim's algorithm, we start with the root vertex r; it can be any vertex.

    1. True
    2. False

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

    1. Not a solution
    2. An algorithm
    3. Good solution
    4. The best solution

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

    1. True
    2. False

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

    1. True
    2. False

44. Consider the following adjacency list:
    
    Which of the following graph(s) describe(s) the above adjacency list?

    1. 
    2. 
    3. 
    4. 

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

    1. v edges.
    2. v – e + 5 edges
    3. v + e edges.
    4. None of the given

46. A graph may contain ________.

    1. Exactly one MST
    2. Maximum one MST
    3. NO MST
    4. More than one MST

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

    1. True
    2. False

48. According to parenthesis lemma. vertex u is a descendent of v vertex if and only if,

    1. [d[u], f[u]] ⊆ [d[v], f[v]]
    2. [d[u], f[u]] ⊇ [d[v], f[v]]
    3. Unrelated
    4. Disjoint

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

    1. True
    2. False

50. In Dynamic Programming approach, we do not store the solution to each sub-problem in case if it reappears.

    1. True
    2. False

Select a course code for Objective Questions:

ACC311 ACC501 BIF101 BIF401 BIF501 BIO101 BIO201 BIO202 BIO203 BIO204 BIO301 BIO302 BIO303 BIO401 BIO503 BNK603 BT101 BT201 BT301 BT302 BT401 BT402 BT403 BT404 BT405 BT406 BT501 BT504 BT505 BT604 CHE201 CHE301 CS001 CS101 CS201 CS202 CS204 CS301 CS302 CS304 CS311 CS401 CS402 CS403 CS408 CS501 CS502 CS504 CS506 CS508 CS601 CS602 CS604 CS605 CS607 CS609 CS610 CS614 CS707 CS710 ECO401 ECO402 ECO403 ECO404 EDU302 EDU401 EDU402 EDU501 EDU601 ENG101 ENG201 ENG301 ENG501 FIN611 FIN624 FIN625 ISL201 IT430 MCM101 MCM301 MGMT623 MGT101 MGT211 MGT301 MGT401 MGT402 MGT501 MGT502 MGT503 MGT510 MGT601 MGT603 MKT501 MKT610 MKT630 MTH101 MTH202 MTH302 MTH501 MTH601 MTH634 PAK301 PHY101 PHY301 PSY101 PSY403 PSY502 PSY512 SOC101 SOC301 SOC401 STA301 STA630 STA641 ZOO102 ZOO401 ZOO501 ZOO502 ZOO503 ZOO504 ZOO505 ZOO506 ZOO510 ZOO630

Select a course code for Subjective Questions:

ACC311 CS001 CS101 CS201 CS301 CS607 CS701 CS702 CS703 CS704 CS707 CS708 CS710 CS711 CS718 CS721 CS724 ECO401 ECO403 ENG101 ENG301 MGT703 MTH501 STA301