VU Midterm Past Papers
198 solved midterm 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 midterm handout.
Q1. Due to left complete nature of binary tree, the heap can be stored in
Q2. What type of instructions Random Access Machine (RAM) can execute?
Q3. For Chain Matrix Multiplication we can not use divide and conquer approach because,
Q4. What is the total time to heapify?
Q5. Random access machine or RAM is a/an
Q6. _______________ is a graphical representation of an algorithm
Q7. A RAM is an idealized machine with ______________ random-access memory.
Q8. What will be the total number of max comparisons if we run brute-force maxima algorithm with n elements?
Q9. What is the solution to the recurrence T(n) = T(n/2)+n .
Q10. Consider the following code: For(j=1; j<n;j++) For(k=1; k<15;k++) For(l=5; l<n; l++) { Do_something_constant(); } What is the order of execution for this code.
Q11. Consider the following Algorithm: Factorial (n){ if (n=1) return 1 else return (n * Factorial(n-1)) } Recurrence for the following algorithm is:
Q12. When we call heapify then at each level the comparison performed takes time
Q13. In Quick sort, we don't have the control over the sizes of recursive calls
Q14. If there are Θ (n^2) entries in edit distance matrix then the total running time is
Q15. The Knapsack problem belongs to the domain of _______________ problems.
Q16. 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
Q17. For the Sieve Technique we take time
Q18. Sieve Technique applies to problems where we are interested in finding a single item from a larger set of _____________
Q19. Total time for heapify is:
Q20. If an algorithm has a complexity of log2 n + nlog2 n + n. we could say that it has complexity
Q21. In RAM model instructions are executed
Q22. Due to left-complete nature of binary tree, heaps can be stored in
Q23. The time assumed for each basic operation to execute on RAM model of computation is-----
Q24. In 2d-space a point is said to be ________if it is not dominated by any other point in that space.
Q25. F (n) and g (n) are asymptotically equivalent. This means that they have essentially the same __________ for large n.
Q26. 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.
Q27. 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.
Q28. Asymptotic growth rate of the function is taken over_________ case running time.
Q29. In analysis of f (n) =n (n/5) +n-10 log n, f (n) is asymptotically equivalent to ________.
Q30. Algorithm is concerned with.......issues.
Q31. In addition to passing in the array itself to Merge Sort algorithm, we will pass in _________other arguments which are indices.
Q32. Consider the following Algorithm: Fun(n){ if (n=1) return 1 else return (n * Fun(n-1)) } Recurrence for the above algorithm is:
Q33. Efficient algorithm requires less computational.......
Q34. The O-notation is used to state only the asymptotic ________bounds.
Q35. 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.
Q36. Before sweeping a vertical line in plane sweep approach, in start sorting of the points is done in increasing order of their _______coordinates.
Q37. Brute-force algorithm for 2D-Maxima is operated by comparing ________ pairs of points.
Q38. 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.
Q39. The definition of Theta-notation relies on proving ___________asymptotic bound.
Q40. 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.
Q41. The number of nodes in a complete binary tree of height h is
Q42. The analysis of Selection algorithm shows the total running time is indeed ________in n,
Q43. A (an) _________ is a left-complete binary tree that conforms to the heap order
Q44. Analysis of Selection algorithm ends up with,
Q45. For the sieve technique we solve the problem,
Q46. A heap is a left-complete binary tree that conforms to the ___________
Q47. In which order we can sort?
Q48. Divide-and-conquer as breaking the problem into a small number of
Q49. For the heap sort we store the tree nodes in
Q50. The sieve technique works in ___________ as follows
Q51. We do sorting to,
Q52. Heaps can be stored in arrays without using any pointers; this is due to the ____________ nature of the binary tree,
Q53. In the analysis of Selection algorithm, we eliminate a constant fraction of the array with each phase; we get the convergent _______________ series in the analysis,
Q54. For the heap sort, access to nodes involves simple _______________ operations.
Q55. In the analysis of Selection algorithm, we make a number of passes, in fact it could be as many as,
Q56. The sieve technique is a special case, where the number of sub problems is just
Q57. How many elements do we eliminate in each time for the Analysis of Selection algorithm?
Q58. One of the clever aspects of heaps is that they can be stored in arrays without using any _______________.
Q59. How much time merge sort takes for an array of numbers?
Q60. The reason for introducing Sieve Technique algorithm is that it illustrates a very important special case of,
Q61. Memoization is?
Q62. Which sorting algorithm is faster
Q63. Quick sort is
Q64. One example of in place but not stable algorithm is
Q65. Cont sort is suitable to sort the elements in range 1 to k
Q66. In place stable sorting algorithm.
Q67. Which may be a stable sort?
Q68. An in place sorting algorithm is one that uses ___ arrays for storage
Q69. Sorting is one of the few problems where provable ________ bonds exits on how fast we can sort,
Q70. Counting sort has time complexity:
Q71. The running time of quick sort depends heavily on the selection of
Q72. One Example of in place but not stable sort is
Q73. In Quick Sort Constants hidden in T(n log n) are
Q74. Quick sort is based on divide and conquer paradigm; we divide the problem on base of pivot element and:
Q75. A point p in 2-dimensional space is usually given by its integer coordinate(s)____________
Q76. In ____________ we have to find rank of an element from given input.
Q77. In Heap Sort algorithm, if heap property is violated _________
Q78. Upper bound requires that there exist positive constants c2 and n0 such that f(n) ____ c2n for all n <= n0
Q79. _________ is one of the few problems, where provable lower bounds exist on how fast we can sort.
Q80. In Heap Sort algorithm, the maximum levels an element can move upward is _________
Q81. In Heap Sort algorithm, the total running time for Heapify procedure is ____________
Q82. While Sorting, the ordered domain means for any two input elements x and y _________ satisfies only.
Q83. Sorting can be in _________
Q84. While solving Selection problem, in Sieve technique we partition input data __________
Q85. The sieve technique works where we have to find _________ item(s) from a large input.
Q86. If the indices passed to merge sort algorithm are ________,then this means that there is only one element to sort.
Q87. The only way to convert an empty string into a string of j characters is by doing j insertions , represented as
Q88. In Selection problem , the Sieve technique works in ------------
Q89. Algorithm is a sequence of computational steps that --------- the input into output.
Q90. In max heap (for Heap Sort algorithm), when every time maximum element is removed from top we replace it with ---------- in the leaf tree.
Q91. If pj dominates pi and pi dominates ph then pj also dominates ph. It means dominance relation is
Q92. In the following code the statement “cout<<j;” executes ------------ times For(j=1;j<=5;j=j+2) Cout<<j;
Q93. For average-case time analysis of Quick sort algorithm, Pivot selection is on average basis from --------------.
Q94. In the statement, “output P[i].x,P[i].y”, the number of times elements of P are accessed is -------------.
Q95. Identify the TRUE statement.
Q96. Matrix multiplication is a(n) ------------ operation.
Q97. In merge sort algorithm, we split the array around the ------------ index q.
Q98. In the analysis of Selection algorithm, we get the convergent ------------ series.
Q99. In Selection problem, the Sieve technique -----------.
Q100. If matrix A of dimension p x q is multiply with matrix B of dimension q x r, then each entry in resultant matrix takes ---------- time.
Q101. Pseudo code of algorithm are to be read by --------------.
Q102. In Dynamic Programming based solution of Knapsack Problem, if we decide to take an object ‘i’, then we gain -------------.
Q103. The worst case running time of Quick sort algorithm --------------.
Q104. The only way to convert a string of i characters into the empty string is with i deletions , represented as
Q105. In Selection problem, the rank of an element will be its ------------ position if we sort the input data.
Q106. Which one is not passed as parameter in Quick sort algorithm?
Q107. Which of the following is calculated with Big O notation?
Q108. For solving Selection problem, we introduced Sieve technique due to ---------
Q109. The worst-case running time of merge sort is ----------- in order to sort an array of n elements.
Q110. While analyzing Selection algorithm, we make a number of passes , in fact it could be as many as -----------.
Q111. Approach for solving geometric problems by sweeping a line across the plane is called ------------- sweep.
Q112. ----------- time is the maximum running time over all legal inputs.
Q113. The asymptotic growth of n(n+1)/2 is:
Q114. One of the limitation in 0/1 Knapsack is that an item can either be ------------ in the bag or not.
Q115. Selection algorithm takes theta ------------.
Q116. The Sieve technique is a special case, where the numbers of sub-problems is just -----.
Q117. Following is not the application of Edit Distance problem
Q118. We can use the optimal substructure property to devise a ---------- formulation of the edit distance problem.
Q119. In plane sweep approach, a vertical line is swept across the 2d-plane form ------------
Q120. In 3-Dimensional space, a point P has ----------- coordinate(s).
Showing the first 120 of 198 MCQs.