Analysis of Algorithm Practice Exam Question Final Quiz Solution

Algorithm Design and Analysis Example Exam Analysis of Algorithm Practice Online Free Exam Question Algorithm Design, Analysis, and Complexity you can comments on this page for solution of these sample question.

1.   Search about the definition of stable sort and find and prove that which of the sorting algorithms we have studied so far are stable and which are not.
2.  Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.
3.    illustrate the operation of PARTITION on the array A = _13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21
4. What value of q does PARTITION return when all elements in the array A[p _ r] have the same value? Modify PARTITION so that q = (p+r)/2 when all elements in the array A[p _ r] have the same value.
5.  Give a brief argument that the running time of PARTITION on a subarray of size n is Θ(n). 
6.   How would you modify QUICKSORT to sort into nonincreasing order?
7.    Show that the running time of QUICKSORT Θ(n^2) when the array A contains distinct elements and is sorted in decreasing order. 
8. When RANDOMIZED-QUICKSORT runs, how many calls are made to the ran domnumber generator RANDOM in the worst case? How about in the best case?
9. Show a situation when bubble sort is faster than quick sort. 
10. Using Figure 8.2 as a model, illustrate the operation of COUNTING-SORT on the array A =_6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2_. 
11. Prove that COUNTING-SORT is stable.
12. Suppose that the for loop header in line 9 of the COUNTING-SORT procedure is rewritten as 9 for j ← 1 to length[A] Show that the algorithm still works properly. Is the modified algorithm stable?
13. Using Figure 8.3 as a model, illustrate the operation of RADIX-SORT on the following list of English words: COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX. 
14. Which of the following sorting algorithms are stable: insertion sort, merge sort and quicksort, counting sort, radix sort and bucket sort? Give a simple scheme that makes any sorting algorithm stable. How much additional time and space does your scheme entail?