Topics to Cover

• Asymptotic Notation:
  • manual exact hand calculations
  • O, theta, omega, notation
  • examples?
• Divide and Conquer
  • Recursion Tree Method
  • Master Theorem
  • Merge Sort
  • Quicksort
  • Maximum Subarray
  • Closest Points
  • Convex Hull
• Greedy
  • Exchange Arguments
  • Greedy stays ahead
  • fractional knapsack
  • activity selection
  • interval scheduling
  • huffman encoding
• Dynamic Programming
  • 01 knapsack
  • Longest Common Sequence
  • Matrix Chain Multiplication
• Trees
  • Elementary Data Structures
    • Stacks and Queues
    • [Rooted Trees](#rooted\ trees)
  • Binary Trees
    • [Full Binary Tree](#full\ binary\ tree)
    • [Complete Binary Tree](#complete\ binary\ tree)
    • [Perfect Binary Tree](#perfect\ binary\ tree)
    • Traversal
      • Pre-order
      • in-order
      • post-order
      • level-order (BFS)
  • Binary Search Trees
    • Search()
    • Insert()
    • Print()
    • Max()/Min()
    • Delete()
      • Lazy
      • Actual
    • Contains()
    • Complexity Analysis
  • Balanced Binary Search Trees
    • AVL Trees
      • Rebalancing
    • Red-Black Trees
      • Recoloring
    • Splay Trees
  • B trees
• Priority Queues and Heaps
  • Array representation
  • Operations
    • Heapify
    • Making a Heap
    • Insertion
    • Deletion
    • ExtractMax/ExtractMin
    • Heapsort
  • Common Problem Patterns
    • Top K elements
    • Merge K sorted arrays
    • Two Heaps
    • Minimum Number
• Hashing
• Graphs

Tests

• Class Test 2