Prelim 2 Topics
Entire semester through last lecture, but emphasis since prelim 1
- Higher order functions.
- Balanced binary trees.
Red-Black balancing scheme.
- 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).
- 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.
- 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.
- 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.
- 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.
- 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)
- Amortized analysis.
Aggregate method, banker's method and physicist's method.
Doubling tables example.
- Directed graphs.
representations: arrays, lists (running time consequences), circular data structures
traversal (DFS/BFS);
weakly and strongly connected components;
topological ordering.
- 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.