AP CS Assignments
Assignments by week:
Fall Term:
Winter Term:
Spring Term:
Monday, December 4
Description
Quadratic sorts
Homework
  • Read Section 13.12: Heapsort in DSA. Note: we're skipping over Quicksort, which we'll come back to next week. The book refers to other chapters that describe what a heap is, so you may need to jump around and read those. Alternately, the heap Wikipedia entry is good (just read the Operations and Implementation sections). If you still have questions, the Wikipedia heapsort entry may provide a different view with additional details.
  • Come to class prepared to describe what a heap is and to perform the agorithm by hand (for example, using playing cards or on the board).
Tuesday, December 5
Description
Mergesort
Homework

  • Complete your mergesort Java class (started during class today). Due at the start of next class.

    You may want to consider breaking the merge phase into its own method, like the one below. You can then call the merge method from your recursive sort method to handle this phase of the sort.

    /** * Given an array of integers, this method looks at two subarrays contained * within the array. Both subarrays should already be sorted. This method * merges the two subarrays together so that they contain all of the elements * from both subarrays in order. * * This method creates a temporary array that is the size of both subarrays. * It uses the temporary array to store the elements so they may be written * back to the original array in order, overwriting the elements that were * there previously. * * @param a The array to merge. The merged elements should be written * back to this array in order, overwriting what was there. * @param left The index of the first element in the left subarray to merge. * All other elements with index less than left are ignored. * @param middle The first index of the right subarray to merge (also, the * first element that is NOT part of the left subarray). This * is the dividing line between the two subarrays. * @param right The first index that is NOT part of the right subarray. All * elements with index greater than or equal to right are * not processed by this algorithm. * * Precondition: left is less than middle; middle is less than right; * right is less than or equal to the length of a * The elements from left to middle-1 are ordered; the elements * from middle to right-1 are ordered. * Postcondition: All elements from left to right-1 are ordered. */ public <T extends Comparable<? super T>> void merge(T[] a, int left, int middle, int right);

  • Hint: you cannot directly make an array of the generic type T (due to the type erasure system used by Java). In order to make a new generic array, I suggest using the Array utility method copyOfRange, like this:

    T[] duplicate = Arrays.copyOfRange(a, left, right);

    The line above would make a new generic array named duplicate that has the same type as a. It will contain all of the elements starting at left and up to (but not including) right (in other words, using the same range rules as your sort).

    You'll also need to add this line to the top of your class file (underneath the package declaration):

    import java.util.Arrays;

Thursday, December 7
Description
Heapsort
Homework

  • Write an implementation for heapsort by creating a class that implements the Sorter interface. You'll likely want to include the following method (or one that performs a similar function). Finished code is due at the beginning of class on Monday.

    /** * Given an array of integers, this method considers the array as a heap * with root element at index min. The heap extends until (but not including) * the element with index max. Starting at the root, this method swaps the * root with the larger of its two children until the heap is a max-heap. * * Recall that the child nodes of an element with index i are given by: * Left child: 2i + 1 * Right child: 2i + 2 * * This method may be written recursively or iteratively. * * @param a The array to treat as a heap * @param min The index of the element to use as the root of the heap. * All other elements with index less than min are ignored * @param max The first index of the array that is NOT part of the heap. * All elements with index greater than or equal to max are ignored. * * Precondition: min is less than max; max is less than or equal to the length of a * The heap is already a max-heap, except for the element * at index min. * Postcondition: All elements formed by the heap rooted at index min form * a valid max-heap. */ public <T extends Comparable<? super T>> void siftdown(T[] a, int min, int max);
Friday, December 8
Description
More Heapsort
Homework
  • Finish your heapsort implementation, due Monday.
  • Read Section 13.11: Quicksort in DSA. For added info, there's the quicksort wikipedia entry.
  • For next class, you should be able to explain everything in this video (well, maybe not everything, but you should be able to explain why the dancers move in the way that they do):