VU Final Term Past Papers
286 solved final term past paper MCQs for CS502 (Fundamentals of Algorithms) at Virtual University, each with the correct answer marked. Use them to learn the VU question style and test your recall. An independent study tool — not affiliated with VU.
Prefer a summary first? Read the CS502 final term handout.
Q1. Fixed-length codes may not be efficient from the perspective of _______the total quantity of data.
Q2. An optimization problem is one in which you want to find,
Q3. 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.
Q4. If a problem is in NP, it must also be in P.
Q5. Maximum number of vertices in a Directed Graph may be |V2|
Q6. The Huffman algorithm finds a (n) _____________ solution.
Q7. The Huffman algorithm finds an exponential solution
Q8. The greedy part of the Huffman encoding algorithm is to first find two nodes with larger frequency.
Q9. The codeword assigned to characters by the Huffman algorithm have the property that no codeword is the postfix of any other.
Q10. Huffman algorithm uses a greedy approach to generate a postfix code T that minimizes the expected length B (T) of the encoded string.
Q11. Shortest path problems can be solved efficiently by modeling the road map as a graph.
Q12. Dijkestra’s single source shortest path algorithm works if all edges weights are non-negative and there are negative cost cycles.
Q13. Bellman-Ford allows negative weights edges and negative cost cycles.
Q14. The term “coloring” came form the original application which was in architectural design.
Q15. In the clique cover problem, for two vertices to be in the same group, they must be adjacent to each other.
Q16. Dijkstra’s algorithm is operates by maintaining a subset of vertices
Q17. The difference between Prim’s algorithm and Dijkstra’s algorithm is that Dijkstra’s algorithm uses a different key.
Q18. We do sorting to,
Q19. After partitioning array in Quick sort, pivot is placed in a position such that
Q20. Merge sort is stable sort, but not an in-place algorithm
Q21. In counting sort, once we know the ranks, we simply _________ numbers to their final positions in an output array.
Q22. Dynamic programming algorithms need to store the results of intermediate sub-problems.
Q23. 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.
Q24. Which of the following is calculated with big o notation?
Q25. Merge sort makes two recursive calls. Which statement is true after these recursive calls finish, but before the merge step?
Q26. Who invented Quick sort procedure?
Q27. What is the solution to the recurrence T(n) = T(n/2)+n, T(1) = 1
Q28. Consider the following Huffman Tree The binary code for the string TEA is
Q29. A greedy algorithm does not work in phases.
Q30. Can an adjacency matrix for a directed graph ever not be square in shape?
Q31. One of the clever aspects of heaps is that they can be stored in arrays without using any____________.
Q32. Merge sort requires extra array storage,
Q33. Non-optimal or greedy algorithm for money change takes____________
Q34. The Huffman codes provide a method of encoding data inefficiently when coded using ASCII standard.
Q35. Using ASCII standard the string abacdaacac will be encoded with __________ bits.
Q36. Using ASCII standard the string abacdaacac will be encoded with 160 bits.
Q37. Using ASCII standard the string abacdaacac will be encoded with 320 bits.
Q38. Using ASCII standard the string abacdaacac will be encoded with 100 bits.
Q39. Using ASCII standard the string abacdaacac will be encoded with 32 bytes
Q40. The greedy part of the Huffman encoding algorithm is to first find two nodes with smallest frequency.
Q41. The greedy part of the Huffman encoding algorithm is to first find two nodes with character frequency
Q42. Huffman algorithm uses a greedy approach to generate an antefix code T that minimizes the expected length B (T) of the encoded string.
Q43. Depth first search is shortest path algorithm that works on un-weighted graphs.
Q44. Dijkestra s single source shortest path algorithm works if all edges weights are non negative and there are no negative cost cycles.
Q45. Dijkestra s single source shortest path algorithm works if all edges weights are negative and there are no negative cost cycles.
Q46. Floyd-Warshall algorithm is a dynamic programming algorithm; the genius of the algorithm is in the clever recursive formulation of the shortest path problem.
Q47. Floyd-Warshall algorithm, as in the case with DP algorithms, we avoid recursive evaluation by generating a table for
Q48. The term coloring came from the original application which was in map drawing.
Q49. In the clique cover problem, for two vertices to be in the same group, they must be_______________each other.
Q50. In greedy algorithm, at each phase, you take the________ you can get right now, without regard for future consequences.
Q51. The difference between Prim s algorithm and Dijkstra s algorithm is that Dijkstra s algorithm uses a same key.
Q52. If a problem is in NP-complete, it must also be in NP.
Q53. If there are n items, there are _______ possible combinations of the items.
Q54. Using ASCII code, each character is represented by a fixed-length code word of bits per character.
Q55. In Knapsack Problem, the thief’s goal is to put items in the bag such that the ______ of the items does not exceed the limit of the bag.
Q56. The knapsack problem does not belong to the domain of optimization problems.
Q57. In Huffman encoding, for a given message string, the frequency of occurrence (relative probability) of each character in the message is determined last.
Q58. Fixed-length codes are known for easy break up of a string into its individual characters.
Q59. In ______ Knapsack Problem, limitation is that an item can either be put in the bag or not-fractional items are not allowed.
Q60. The term “coloring” came from the original application which was in architectural design.
Q61. In Knapsack Problem, value and weight both are to be under consideration.
Q62. Time complexity of DP based algorithm for computing the minimum cost of chain matrix Multiplication is ________ .
Q63. In DP based solution of knapsack problem, to compute entries of V we will imply a/an _______ approach.
Q64. A greedy algorithm sometimes works well for optimization problems.
Q65. In Huffman encoding, frequency of each character can be determined by parsing the message and __________ how many times each character (or symbol) appears.
Q66. Greedy algorithm can do very poorly for some problems.
Q67. The Huffman codes provide a method of _________ data efficiently.
Q68. In _______ based solution of knapsack problem, we consider 2 cases, Leave object Or Take object.
Q69. Those problems in which Greedy finds good, but not always best is called a greedy________.
Q70. In brute force based solution of knapsack problem, we consider 2 cases, Leave object Or Take object.
Q71. ________ problem, we want to find the best solution.
Q72. Using ASCII standard the string abacdaacac will be encoded with 10 bytes.
Q73. In _______ algorithm, you hope that by choosing a local optimum at each step, you will end up at a global optimum.
Q74. Due to left complete nature of binary tree, the heap can be stored in
Q75. What type of instructions Random Access Machine (RAM) can execute?
Q76. What is the total time to heapify?
Q77. Random access machine or RAM is a/an
Q78. A RAM is an idealized machine with ______________ random-access memory.
Q79. Is it possible to sort without making comparisons?
Q80. When we call heapify then at each level the comparison performed takes time
Q81. In Quick sort, we don’t have the control over the sizes of recursive calls
Q82. If there are Θ (n2) entries in edit distance matrix then the total running time is
Q83. For Chain Matrix Multiplication we can not use divide and conquer approach because,
Q84. The Knapsack problem belongs to the domain of _______________ problems.
Q85. Suppose we have three items as shown in the following table, and suppose the capacity of the knapsack is 50 i.e. W = 50. Item Value Weight 1 60 10 2 100 20 3 120 30 The optimal solution is to pick
Q86. Mergesort is a stable algorithm but not an in-place algorithm.
Q87. Counting sort the numbers to be sorted are in the range 1 to k where k is small.
Q88. In selection algorithm, because we eliminate a constant fraction of the array with each phase, we get the
Q89. In RAM model instructions are executed
Q90. Due to left-complete nature of binary tree, heaps can be stored in
Q91. The time assumed for each basic operation to execute on RAM model of computation is-----
Q92. If the indices passed to merge sort algorithm are not equal, the algorithm may return immediately.
Q93. Brute-force algorithm uses no intelligence in pruning out decisions.
Q94. In analysis, the Upper Bound means the function grows asymptotically no faster than its largest term.
Q95. For small values of n, any algorithm is fast enough. Running time does become an issue when n gets large.
Q96. In simple brute-force algorithm, we give no thought to efficiency.
Q97. The ancient Roman politicians understood an important principle of good algorithm design that is plan-sweep algorithm.
Q98. In 2d-space a point is said to be ________if it is not dominated by any other point in that space.
Q99. An algorithm is a mathematical entity that is dependent on a specific programming language.
Q100. The running time of an algorithm would not depend upon the optimization by the compiler but that of an implementation of the algorithm would depend on it.
Q101. F (n) and g (n) are asymptotically equivalent. This means that they have essentially the same __________ for large n.
Q102. 8n2 + 2n - 3 will eventually exceed c2*(n) no matter how large we make c2.
Q103. If we associate (x, y) integers pair to cars where x is the speed of the car and y is the negation of the price. High y value for a car means a ________ car.
Q104. The function f(n)= n(logn+1)/2 is asymptotically equivalent to n log n. Here Upper Bound means the function f(n) grows asymptotically ____________ faster than n log n.
Q105. After sorting in merge sort algorithm, merging process is invoked.
Q106. Asymptotic growth rate of the function is taken over_________ case running time.
Q107. In analysis of f (n) =n (n/5) +n-10 log n, f (n) is asymptotically equivalent to ________.
Q108. Algorithm is concerned with_____issues.
Q109. We cannot make any significant improvement in the running time which is better than that of brute-force algorithm.
Q110. In addition to passing in the array itself to Merge Sort algorithm, we will pass in _________other arguments which are indices.
Q111. In analysis, the Lower Bound means the function grows asymptotically at least as fast as its largest term.
Q112. Efficient algorithm requires less computational.
Q113. The O-notation is used to state only the asymptotic ________bounds.
Q114. For the worst-case running time analysis, the nested loop structure containing one “for” and one “while” loop, might be expressed as a pair of _________nested summations.
Q115. Before sweeping a vertical line in plane sweep approach, in start sorting of the points is done in increasing order of their _______coordinates.
Q116. Brute-force algorithm for 2D-Maxima is operated by comparing ________ pairs of points.
Q117. The function f(n)=n(logn+1)/2 is asymptotically equivalent to nlog n. Here Lower Bound means function f(n) grows asymptotically at ____________ as fast as nlog n.
Q118. In plane sweep approach, a vertical line is swept across the 2d-plane and _______structure is used for holding the maximal points lying to the left of the sweep line.
Q119. Algorithm analysts know for sure about efficient solutions for NP-complete problems.
Q120. The analysis of Selection algorithm shows the total running time is indeed ________in n,
Showing the first 120 of 286 MCQs.