• To appreciate the role of algorithms in problem solving and software design, recognizing that a given problem might be solved with a variety of algorithms.
• To be capable of selecting among competing algorithms and justifying their selection based on efficiency.
• To be capable of selecting and utilizing appropriate data structures in implementing algorithms as computer programs.
• To develop programs using different problem-solving approaches (divide-and-conquer, backtracking, dynamic programming), and be able to recognize when one approach is a better fit for a given problem.
• To design and implement programs to model real-world systems, and subsequently analyze their behavior.

Object-oriented programming review
  design goals: highly cohesive, loosely coupled
  OO concepts: class vs. object, interfaces, inheritance, polymorphism
  data structures: List, Set, Map, Stack, Queue, Graph, ...
  algorithm analysis: big-Oh, rate-of-growth, analyzing algorithms, recursion
  
Algorithmic design
  brute force algorithms
    straightforward, one-time approach
    example: hoops stats (HW1)
    exhaustive search: string matching
    generate-and-test: N-queens, Traveling Salesman, Knapsack
  decrease-and-conquer
    reduce problem to single, smaller instance
    by-constant: sequential search, insertion sort, topological sort
    by-constant-factor: binary search, fake coin problem
    by-variable-amount: BST search, selection problem, dishonest hangman (HW2)
  divide-and-conquer algorithms
    reduce problem to multiple smaller instances
    examples: merge sort, quick sort, closest points, multiplication
    tree recursion: numNodes, numWords, k-ary trees (HW3)
    Master Theorem
  transform-and-conquer: 
    transform problem into a different, more easily solved problem
    examples: presorting, balanced BST algorithms, Horner's Rule
    problem reduction: lcm --> gcd  
  greedy 
    solve by making a sequence of choices/actions, select locally optimal
    examples: minimal change, job scheduling, greedy image filtering (HW4)
    minimal spanning tree: Prim's algorithm
    shortest path: modified BFS,  Dijkstra's algorithm
    data compression: Huffman codes
  backtracking
    solve by making a sequence of choices/actions, back up and retry if fail
    examples: N-queens, blob count, Boggle, 3-in-a-row puzzle (HW5)
    stable matching problem (Gale-Shapley algorithm)
    branch-and-bound: job assignment
    game search: game trees, minimax search, alpha-beta pruning
  dynamic: 
    bottom-up alternative to divide-and-conquer, avoids redundancy
    examples: binomial coefficient, World Series puzzle, gminimal edit distance (HW6)
    all-pairs shortest path: Floyd's algorithm
    top-down with caching: change maker
    
Algorithm analysis
  recursion
    analysis via recurrence relation, Master Theorem
  space vs. time tradeoffs
    examples: heap sort, hash tables, BinaryTree
    string matching: Horspool's algorithm, Boyer-Moore algorithm
  complexity theory
    lower bounds on problems
      brute force, info-theoretic, adversary argument, reduction
      decision trees: searching, sorting
    tractable vs. intractable vs. undecidable (Halting Problem)
    P vs. NP, Turing machine vs. non-deterministic Turing machine
      NP-complete problems (e.g., SAT), reductions (e.g., SAT --> CLIQUE) 
    approximation algorithms, genetic algorithms