Midterm Prep

Table of Contents

• Part 1: Looking back at HW6 and HW7
• Part 2: Guerrilla Section Worksheet
• Part 3a: Sorting Implementations
• Part 3b: Sorting Timing Tests
• Part 4: Balanced Search Trees

HW6 and HW7 Solutions

Compare your answers to HW6 and HW7 to the reference solutions. Look for places where your code is overly complex relative to the reference.

Direct links for convenience:

• BSTStringSet
• ECHashStringSet

Guerrilla Section Worksheet

Work through the Guerrilla Section worksheet (link to be posted at 2 PM Sunday).

Sorting Algorithm Implementations and Timing

Sorting Algorithms: Big Ideas

To test your understanding of the mechanics of sorting algorithms, answer the questions given in this slide.

Implementing Sorting Algorithms

Starter files for this assignment are available here. They will not be available via hw init.

MySortingAlgorithms.java provides a skeleton for implementing the various sorting algorithms from 61B. SortingAlgorithms.java provides solutions.

If you'd like, try implementing the sorting algorithms. If you're optimizing your study time, I'd recommend against doing any of the moderate (or harder) sorts. While you'll certainly gain a very deep understanding of these algorithms by implementing them, we don't expect you to understand various second-order issues (like auxiliary arrays, resizing for heapsort, bit hacking for LSD and MSD sort, etc) for 61B.

They are ranked in implementation difficulty below:

• Selection sort: Fairly Easy
• Insertion sort: Fairly Easy
• Merge sort: Moderate
• Distribution sort: Moderate
• Heapsort: Hard (if you implement the heap from scratch). Using a MaxPQ it's very easy.
• Quicksort: Hard
• LSD sort: Very Hard
• MSD sort: Very Hard

You can use MySortingAlgorithmsTest to test your implementations.

Alternately, simply copy and paste from SortingAlgorithms.java to MySortingAlgorithms.java. Be warned that the code for SortingAlgorithms is a bit messy.

Timing Sorting Algorithms

The RunBenchmarks class runs timing tests on our various sorts. Currently, it is configured to perform two timing tests:

• Compare (y)our implementation against Arrays.sort (which uses Quicksort for ints).
• Time insertion sort for almost sorted arrays.

Run the code, and you should see results that are in line with things we've learned in class.

Other interesting tests you might try:

• How do LSD and MSD compare with Quicksort and Mergesort? How large must N be before they become faster?
• Find a case where LSD is faster than MSD.
• For what N is insertion sort faster than Quicksort?
• How do selection sort and insertion sort compare?

Feel free to post interesting tests and/or observations in the HW8 thread.

Balanced Search Trees

1. Give a formula for the exact height of a binary search tree (as you implemented in homework 6) as a function of N if we insert N values in increasing order.
2. Give a formula for the exact height of a 2-3-4 tree in terms of N if we insert N values in increasing order.
3. Test your understanding of the isometry between 2-3-4 trees and red-black trees by completing this exercise.