Notes

COMP 314: Algorithms and Complexity
Kathmandu University

Compiled by:
Manoj Shakya
26th July 2015



1. Consider an algorithm for solving activity selection problem. Assume that there are 6 activities with following start time and finish time.
s = {1, 3, 0, 5, 8, 5}
f = {2, 4, 6, 7, 9, 9}
Which of the following statements is TRUE?
a) 1st activity is not in solution set.
b) 3rd activity is in solution set.
c) 6th activity is in solution set. *
d) 4th activity is not in solution set.

2. Which of the following statements is TRUE about Activity Selection Problem?
a) This problem can be solved using Greedy Algorithm.
b) This problem can be solved using Dynamic Programming Technique
c) It's a problem of scheduling a resource amoung several sompleting activities.
d) All of the above. *

3. What is the time copmlexity of Greedy based solution of Activity Selection Problem?
a) O(log n)
b) O(n)
c) O(n log n) *
d) O(n^2)

4. A networking company uses a compression technique to encode the message before transmitting over the network. Suppose the message contains the following characters with their frequency:
a:5 b:9 c:12 d:13 e:16 f:45
If the compression technique used is Huffman Coding, how many bits will be saved in the message?
a) 224
b) 800
c) 576 *
d) 324

5.What is the time complexity of Huffman Coding?
a) O(n)
b) O(n log n) *
c) O(n (logn)^2)
d) O(n^2)

6. Let the alphabet Gamma be ('A', 'B', 'C', 'D', 'E'). Let the occurrence probability be P('A') = 0.1, P('B') = 0.14, P('C') = 0.51, P('D') = 0.1, and P('E') = 0.15.
What is the huffman code for 'D'?
a) 000
b) 010
c) 001 *
d) 011

7. Which of the following standard algorithms is not a Greedy algorithm?
a) Dijkstra's Shortest Path Algorithm
b) Kruskal's Algorithm
c) Huffman Coding
d) Binary Search Algorithm *

8. Let the sequence of matrices be A1, A2, A3 and A4 whose dimensions are given by a set p. And p = {30, 1, 40, 10, 25}. If you use parentheses like $ (A1 . A2).(A3 . A4) $, what is the total number of multiplications required?
a) 40,200
b) 41,200 *
c) 1,400
d) None of the above

9. Consider a matrix chain multiplication problem. If a dynamic programming gives a s-table as follows, what is the Optimal parenthesisation?
s|1 2 3 4
1| 1 1 1
2| 2 3
3| 3
4|

a) $ A_1.( (A_2 . A_3) . A_4) $ *
b) $ (A_1 . A_2) . (A_3 . A_4) $
c) $ A_1. (A_2 . (A_3 . A_4) ) $
d) $ ((A_1. A_2) . A_3) . A_4 $

10. What is the time complexity of a standard algorithm (Dynamic Programming) of solving Matrix Chain Multiplication?
a) O(n^2)
b) O(n log n)
c) O(n^3) *
d) O(n!)

11. Consider follwoing string sequences:
S1 = "SRINAGAR"
S2 = "BIRATNAGAR"
Which of the following is NOT the common subsequence of S1 and S2?
a) "NAGAR"
b) "INAR"
c) "RNAR"
d) "IRNAR" *

12. What is the time complexity of a standard algorithm (Dynamic Programming) of solving Longest Common Subsequence? Assume that the length of each string is n.
a) O(n^3)
b) O(n!)
c) O(n log n)
d) none of the above

13. Consder two strings X= <B,D,C,A,B,A> and Y=<A,B,C,D,A,B>. Generate a table for solving a longest common subsequenec problem. Assume that the table[0,...] = 0 and table[..., 0] = 0, what is the value of table[6, 3]?
a) 1
b) 2 *
c) 3
d) 4

14. Which of the following statements is TRUE about Kruskal's algorithm?
a) It is an inefficient algorithm, and it never give the minimum spanning tree.
b) It is an efficient algorithm, and it always gives the minimum spanning tree. *
c) It is an efficient algorithm, but it doesn't always give the minimum spanning tree.
d) It is an inefficient algorithm, but it always gives the minimum spanning tree.

15. Which of the following is TRUE about Dijkstra's Algorithm?
a) It may not terminate if the graph contains negative-weight edges.
b) The time-complexity is O(|V|) where |V| is the number of nodes.
c) It may produce different shortest path trees but always of same weight *
d) none of the above.