Topics outline -- I still might have missed some, but here's the list as of Dec 7.

• Complexity
  • understand (and be able to explain) the purpose of using order notation when reviewing algorithms
  • understand (and be able to explain) the need for defining input size and elementary operations
  • be able to identify the complexity of basic code/algorithm constructs
  • know the heirarchy of common orders (constant, log, linear, polynomials, etc)
  • be able to prove that f(n) ∈ O(g(n) or f(n) ∈ Ω(g(n)) or f(n) ∈ Θ(g(n)) for given f(n) and g(n), using the definitions, and using the rules.
  • Master Theorem -- usage for analyzing certain Divide and Conquer recurrence relations
  • Analyze a given Divide and Conquer pseudocode algorithm inot a recurrence relation
  • Understand MergeSort

• Union-Find
  • algorithms using forest Data Structure
  • path compression and union by rank
    • path compression and union-by-rank: know how to do it on an example forest, and know how to write the pseudocode for relevant subroutines

• Binary search trees
  • basic pointer-based implementation
  • inserts, removes, searches
  • recursive traversals
  • optimal versus worst case tree structure, and impact on operations -- running time implications

• AVL trees
  • implementations as an extension to binary search trees
  • inserts, searches, deletes, traversals, and efficiency
  • left and right rotations, and tree balancing by performing single or double rotations

• Heaps
  • implementations as a modified form of binary tree
  • suitability for sorting and priority queues
  • unsuitability for searching
  • insert, remove, MakeHeap (of an array), Heapify (at an element)

• Graphs
  • adjacency matrix and adjacency list implementations (implementation details, efficiency issues)
  • breadth-first and depth-first searches; connectivity testing
  • minimum spanning tree: Prim's and Kruskal's algorithms
  • shortest path computations (Dijkstra's algorithm)

• Greed
  • Prim's, Kruskal's and Unit Task Scheduling

• Hash tables
  • hash functions
  • collision resolution
  • open hashing: collision resolution, expected performance as function of α
  • closed hashing: linear probing; clustering; double hashing

• Divide and Conquer
  • Devise divide and conquer solutions to problems
  • determine a recurrence for the running time

• Dynamic Programming
  • Longest Common Subsequence, Longest Increasing Subsequence algorithms
  • Devise dynamic programming solution to a problem
  • determine the running time

• B-trees
  • Insert -- know how the tree changes if an insert is executed.