Skip to content

Latest commit

 

History

History
37 lines (28 loc) · 1.22 KB

13.md

File metadata and controls

37 lines (28 loc) · 1.22 KB
title
Midterm 2

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!