CS502 Quiz by S Khan Academy

SOLVED BY SANAULLAH KHAN

1. The sieve technique works where we have to find ---------- item(s) from a large input. Single page 34

CS502 QUIZ FILE · Subject Enrolment · 1. Online classes are available (Mathematics) · 2. Solved graded activities · Assignment’s · Quizzes · GDB’s · 3. Solved quiz files · 4. Past papers · 5. Any info about virtual university of · Pakistan · Final project (MTH620) · Email: · Mr.khan.1431 · S KHAN ACADEMY

2. The only way to convert an empty string into a string of j characters is by doing j insertions, represented as

E(0 , j)=j page 78

3. In Selection problem, the Sieve technique works in ------------ Phases page 34
4. Algorithm is a sequence of computational steps that --------- the input into output. Transform page 7
5. In max heap (for Heap Sort algorithm), when every time maximum element is removed from top we replace it with ---------- in the leaf tree. Last page 41
6. If pj dominates pi and pi dominates ph then pj also dominates ph. It means dominance relation is Transitive
7. To find maximal points in brute-force algorithm, each point of space is compared against --------- of the

space. All other points page 13

8. In the following code the statement “cout<<j;” executes ------------ times

For(j=1;j<=5;j=j+2) Cout<<j; 3 times (conceptual)

9. For average-case time analysis of Quick sort algorithm, Pivot selection is on average basis from --------------.

All possible random values page 50

10. In the statement, “output P[i].x,P[i].y”, the number of times elements of P are accessed is -------------. 2
11. Identify the TRUE statement. The Knapsack problem belongs to the domain of optimization problems
12. Matrix multiplication is a(n) ------------ operation. Associative page 85
13. ------------ provides us more accurate result when input values are not closer to each other. Median page

34(conceptual)

14. In merge sort algorithm, we split the array around the ------------ index q. Mid page 28
15. In the analysis of Selection algorithm, we get the convergent ------------ series. Geometric page 37
16. In Selection problem, the Sieve technique -----------. Eliminate undesired data items each time page 35
17. If matrix A of dimension p x q is multiplied with matrix B of dimension q x r, then each entry in resultant matrix takes ---------- time. O(q) page 84
18. In Sorting the key value or attribute ---------- form an ordered domain. Not always page 39
19. In Heap Sort algorithm, the total running time for Heapify procedure is -------------. Theta (log n) page 43
20. Pseudo code of algorithm are to be read by --------------. People page 12
21. In Dynamic Programming based solution of Knapsack Problem, if we decide to take an object ‘i’, then we

gain -------------. Vi(value of object i)

22. The worst-case running time of Quick sort algorithm --------------. Is quadratic (google)
23. The only way to convert a string of i characters into the empty string is with i deletions, represented as

• E(i , 0)=i page 78

24. In Selection problem, the rank of an element will be its ------------ position if we sort the input data. Final
25. Which one is not passed as parameter in Quick sort algorithm? Array (containing input elements) (cs301)
26. While Sorting, the ordered domain means for any two input elements x and y --------- satisfies only. All of

the above page 39

27. Which of the following is calculated with Big O notation? Upper bounds page 25
28. For solving Selection problem, we introduced Sieve technique due to --------- Eliminating Rank of an

element page 35

29. The worst-case running time of merge sort is ----------- in order to sort an array of n elements. O(n log n)
30. Quick sort is a recursive algorithm. True page 49
31. While analyzing Selection algorithm, we make a number of passes, in fact it could be as many as -----------.