Homework 2 (assigned April 8; due April 15)

Reading for week 3: CLRS chapter 6.

Written assignment: Solve the following "Do" exercises and assigned problems. Turn in only the problem solutions. Please note: You are responsible for the material covered in both "Do" exercises and problems.

"Do" Exercises (not to be handed in):

1. Use the iteration method to solve the recurrence T(n) = 2T(n/3) + n, T(1) = 1. Assume that n is a power of 3.
2. Use the substitution method to prove that the recurrence T(n) = T(n/10) + T(9n/10) + O(n) has the solution T(n) = O(n lg n), as claimed in class.
3. Exercise 4.1-1 on CLRS page 67.
4. Exercise 4.1-2 on CLRS page 67.
5. Exercise 4.1-3 on CLRS page 67.
6. Exercise 4.1-5 on CLRS page 67.
7. Exercise 4.1-6 on CLRS page 67.

Problems (to be handed in):

1. Basic sorting
   Using the pseudocode on CLRS page 146, show how quicksort sorts the array A = [13, 19, 9, 5, 12, 8, 7, 4, 11]. Use Figure 7.1 on CLRS page 147 as a model for the operation of the Partition subprocedure. (5 points)

2. Mergesort
   Problem 2-1, parts a, b, c, on CLRS pages 37-38. (15 points)

3. Quicksort
   
   1. Exercise 7.4-5 on CLRS page 159. (10 points)
   2. Given an array A[p.. r], with r - p > 1, let q = floor[(p + r)/2] and choose as the pivot element the median of A[p], A[q], A[r], i.e., the value that would be in the middle if A[p], A[q], A[r] were sorted. Median-of-3 partitioning uses as the pivot element the median of A[p], A[q], A[r]. Note that these three elements are not randomly picked.
      1. Consider modifying the Partition procedure on CLRS page 146 by using median-of-3 partitioning. Show how this modified Partition procedure partitions the array A = [13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21]. (5 points)
      2. Write pseudocode for the median-of-3 partitioning procedure. (10 points)
      3. What is the running time for a version of quicksort that uses median-of-3 partitioning if the input is a sorted array? (5 points)
      4. Write a recurrence for the worst-case running time of quicksort using median-of-3 partitioning on an array of size n. What is the worst-case running time? Support your answer. (10 points)
   3. Problem 7-1, parts a-e, on CLRS pages 159-160. (20 points)

4. Recurrences
   Problem 4-3, parts a and b, CLRS pages 85-86. (20 points)

5. Algorithm design
   Let A[1..n] be an array of n distinct integers in sorted order. We say that an array has a fixed point if there is an index i for which A[i] = i. Give a divide-and-conquer algorithm that determines if the array A described above has a fixed point. Your algorithm should run in time O(log n). Briefly justify its running time. (20 points)
   Note: You may either write pseudocode for your algorithm or give a very clear and concise description of the steps of your algorithm in English. Points will be taken off for code that is not clear or for descriptions that are not concise and complete.

   ---

   Gerry Brady
   Wednesday 09:53:54 CDT 2008