CPSC 311-501 and CPSC 311-502: Analysis of Algorithms
Information and Review Questions for Exam I
Spring 2003

General Information

The first exam will be on Tuesday February 18. It will cover material from Chapters 1, 2, 3, 4, 6, 7, 8, and 9 in the text. It will be a closed book exam (no notes, books, or neighbors) except you will be allowed a one page, one side cheat sheet which must be turned in with the exam. There will be 5 questions, each worth 20 points, for a total of 100 points. Remember to show your work - partial credit will be given.

Material

All of the following are considered to be fair game:

Review Questions

Below are some suggested review exercises/problems for the exam. It is strongly recommended that you be able to do all of these problems. Solutions will not be handed out. Finally, be sure to check your email -- clarifications and/or explanations will be mailed to the class if needed.

  1. Study Homeworks #1, #2, #3, and #4, and Quizzes 1-5; variations of some of these questions will appear on the midterm.

  2. Know the space usage, and the best-case, average-case, and worst-case times of all the sorting and selection algorithms we've studied in class. Be able to answer questions of the following form - circle all asymptotic bounds that apply.

    1. What is the best-case time for insertion sort on n elements?
      Omega(1) Theta(1) O(1)
      Omega(n) Theta(n) O(n)
      Omega(nlogn) Theta(n log n) O(nlogn)
      Omega(n2) Theta(n2) O(n2)

    2. What is the average-case time for radix sort on n elements, each in the range [1,n7]?
      Omega(1) Theta(1) O(1)
      Omega(n) Theta(n) O(n)
      Omega(nlogn) Theta(n log n) O(nlogn)
      Omega(n2) Theta(n2) O(n2)

    3. The amount of extra space used by insertion sort is:
      Omega(1) Theta(1) O(1)
      Omega(n) Theta(n) O(n)
      Omega(nlogn) Theta(n log n) O(nlogn)
      Omega(n2) Theta(n2) O(n2)

  3. Consider the following comparison-based sorting algorithm.
    Fast-Sort(array L of integers) 
 if (L has less than 4 elements) 
   then sort L by brute-force and return L;
   else 
      L1 := Fast-Sort(1st quarter of L);    
      L2 := Fast-Sort(2nd quarter of L);  
      L3 := Fast-Sort(3rd quarter of L);   
      L4 := Fast-Sort(4th quarter of L);    
      L := 4-way-Merge(L1,L2,L3,L4); 
      return L; 
 endif 
end /*Fast-Sort*/

    Assume the complexity of 4-way-Merge(L1,L2,L3,L4) is O(n1 + n2 + n3 + n4), where ni is the number of elements in Li, i=1,2,3. Derive and solve the recurrence relation for the asymptotic running time of Fast-Sort; clearly state any assumptions you make.

  4. Design an algorithm based on the heap data structure for finding the kth largest element in a list of n elements. The only (non-trivial) operations your algorithm should perform are: Analyze the complexity of your algorithm.

  5. Suppose you are given a list of n integers to sort that contains only the values 1, 2, 3, and 4. Consider how the presence of duplicate elements affects the running time.

    1. Suppose you use insertion sort.
      What is the absolute number of comparisons (approximately) that will be done in the worst-case, and how does this compare to the situation in which all n elements are distinct?
      What is the order of the number of comparisons that will be done in the worst-case, and how does this compare to the situation in which all n elements are distinct?

    2. Is radix sort a good algorithm to use in this situation? Why or why not?

    3. Is there an in-place algorithm for this problem that runs in O(n) time? If not, explain why not. If so, give the algorithm.