Covers

Chapters: 4, 5, 6

Important Concepts

1. Divide and Conquer
   • Master Theorem of General Divide-and-Conquer (lets us solve recurrence quickly, to get time efficiency)
   • Know Mergesort and Quicksort (and their efficiency!)
2. Transform and Conquer:
   • Know presorting.
   • Balanced search trees (know how to construct!)
     • Binary Search Tree (AVL, red-black)
     • Multi weight (2-3, and friends heap/heapsort)
3. Space-for-time Tradeoffs:
   • Know: Input enhancement and prestructuring.
   • Know sorting by counting.
   • Know (especially) string searching by preprocessing (Horspool’s and Boyer-Moore)
   • Hashing (open hashing, closed hashing, linear probing)

More on AVL:

• Be familiar with how to calculate balance factor (height of left subtree - height of right subtree; -1 if empty)
• Know all four AVL tree rotations! Professor stresses that you split the double rotations into two single rotations if you aren’t confident.

More on 2-3:

• Know how to construct!

More on Heap and Heapsort:

• Know the definition. Key at each node is >= its children (thus, root is max)
• Can construct bottom-up or top-down.
• Know how to heapsort!