Prelim 2 Topics

Entire semester through last lecture, but emphasis since prelim 1

  1. Higher order functions.
  2. Balanced binary trees. Red-Black balancing scheme.
  3. Disjoint set forest/union-find. set of n-ary trees represented using array which stores index of parent (self = root); find operation, finds root of tree for given node; union operation merges two trees, by finding both roots then making one child of other; union by rank (or size) guarantees log depth by making larger rank tree parent of smaller rank one; find with path compression improves over log time in amortized sense (but analysis hard).
  4. Specifying and implementing data structures (various classes) Need to be comfortable with data structures covered and simple variants of them, completing or correcting partial implementations, analyzing implementations that are given.
  5. Inductive correctness proofs. Prove that some piece of code meets a given specification, some property P(n) Induction over some aspect of the data (strong induction often useful as size not necessarily one smaller) Recursive functions, partial correctness, P(n) holds if terminates, total correctness, further show terminates.
  6. Concurrency. critical sections, mutexes, condition variables, minimizing code in critical sections; correct handling of locking/unlocking/signaling conditions exception handling; reader-writer lock pattern, starvation issues; producer-consumer pattern; thread pools, use of producer-consumer pattern; deadlocks, avoiding use of multiple locks.
  7. Recurrences: substitution and master methods. Substitution: guess an answer and prove it by induction (usually strong induction), recursion trees can be useful for good guess. Know the master method and its uses. Basic form will be given so don't need to memorize but if you don't know how to use it you will be lost.
  8. Hash tables. Array of lists of O(1) length. Rehashing when load factor too high (usually 2 for chaining and .75 for linear probing is considered good)
  9. Amortized analysis. Aggregate method, banker's method and physicist's method. Doubling tables example.
  10. Directed graphs. representations: arrays, lists (running time consequences), circular data structures traversal (DFS/BFS); weakly and strongly connected components; topological ordering.
  11. Memoization and dynamic programming. keeping track of and reusing intermediate results to reduce asymptotic complexity. Looked at fib, max weight independent set in tree, breaking text lines.

Possible Questions

Amortized analysis, perhaps including some implementation or un-amortized analysis, perhaps specific method of analysis (bankers or potential required, though others may get partial credit)

Representations of directed graphs and/or directed graph algorithms

Comparing appropriateness of different data structures for particular problem, including issues of asymptotic running time, amortized versus worst case, and locality

Implementation and/or analysis of mutable data structure

Correctness proof of some piece of code

Concurrency, possibly code with flaw(s) that need to be corrected or whose failing behavior needs to be concisely explained

Graph algorithm implementation and analysis

Recurrence to solve by induction and/or master methods

Comparing memoized and un-memoized versions of some function, or using memoization to improve running time of some function - nice place for higher-order function questions.