TEST 1 MATERIAL

Data Structures
  Set & Map interfaces
    TreeSet & TreeMap: underlying balanced binary search trees
    HashSet & HashMap: underlying hash tables
  trees
    tree terminology: node, root, leaf, path, height, weight
    tree applications: file structure in OS, du command
    binary tree implementation
      pointer manipulation, tree recursion
      divide & conquer algorithms
    binary search tree
      if roughly balanced, O(log N) search/insert/remove
      if unbalanced, O(N) search/insert/remove
      SimpleTreeSet implementation, tree iterator
    balanced binary search trees
      AVL trees, red-black trees
      add additional properties on BST, insert/remove must maintain properties
      ensure O(log N) tree height --> O(log N) search/insert/remove
  hash tables
    key-value mapping, hash function  
      if table size & hash function "reasonable", O(1) search/insert/remove
      if not, O(N) search/insert/remove
    collision handling
      linear probing, lazy deletion, primary clustering, rehashing
      quadratic probing, chaining
      
Algorithmic Approaches
  divide & conquer
    idea: divide into subproblems, solve (usually recursively), then combine
    when: any application that can be divided into independent parts
    e.g.: binary search, merge sort, GCD, tree traversal
  generate & test
    idea: generate all potential solutions in sequence & test each
    when: solution is a sequence of actions, no problem-specific knowledge
    examples: inefficient N-queens, NP-hard problems (later)
  greedy
    idea: make a sequence of choices, each of which looks best at the moment
    when: solution is a sequence of actions & perfect knowledge is available
    e.g.: job scheduling, U.S. optimal change
  backtracking (a.k.a. smart generate & test, tentative greedy)
    idea: make next choice, test if still ok & unwind if dead end
    when: choices are dependent, earlier choices constrain later ones
    e.g.: N-queens, Boggle search, blob count, Sudoku solver