Math 416, Fall 2004: Expanded Cumulative Syllabus

Sept 8--10:

Overview (informal): Problems, algorithms, correctness, efficiency, approximation, correctness on most inputs, correctness on most runs, data structures (for sequences of inputs), reduction of one problem to another, presumed hardness of NP-hard problems. Multiplication of integers as example.

Loop invariants: initialization, maintenance, termination. Best case and worst case runtimes. Insertion sort as example. (CLRS Chapter 2.)

Sept 13--17:

Theta notation (informally defined, for polynomials only), mergesort, runtime analysis of mergesort as a divide and conquer algorithm.

Calculus useful for bounding and evaluating summations: comparisons with integrals, geometric and harmonic sums, linearity and dominance. (CLRS Appendix A.)

Big-O, little-o, Big-Omega, little-omega notation. Related alternation of quantifiers and limit formulations. (CLRS Chapter 3.)

Sept 20--24

More calculus: logs, polynomials (i.e., powers), exponentials, polylogs, factorial, and asymptotic comparison. (CLRS Chapter 3.)

Recurrences, especially the type that arise in divide and conquer algorithms: T(n) = aT(n/b) + n^c. Manipulations of recurrences. The master theorem, giving a solution by inspection to that recurrence for all constant values of a,b, and c: Cost by level in the recursion tree is a geometric series; the behavior differs according to whether the ratio is less than, equal to, or greater than 1. An aside using Delta notation to state recurrences in difference equation form, in parallel with differential equations. (CLRS Chapter 4.)

Sept 27--Oct 1

Heap data structure: Supports INSERT, EXTRACT_MAX, and other operations in time O(log(n)) per operation. Processing a sequence of insertions is useful at user/application level to implement a priority queue and useful in the innards of sorting algorithms to process input items.

Review of probability: Counting sequences, strings, combinations, etc. Axioms of probability. Conditional probability and independence. Random variables, expectation, and variance. Importance of low variance in showing that a random variable is close to its mean with high probability. Inequalities such as Jensen's and Markov's.

Oct 4--Oct 8

More on probability: Inequalities of: Using these inequalities to bound tails of the binomial distribution and to show that a random variable is close to its mean with high probability. For example, runtime is non-negative. If an algorithm has runtime T with expectation mu, then, by Markov, Pr( T > 4mu) < (1/4).

Average-case and randomized algorithms. Usefulness of algorithms that make no assumption about input distribution. Usefulness of destroying structure in input to avoid bad inputs. Birthday paradox.

Quicksort: Variant in which we find a good pivot before proceeding. Expected runtime of quicksort is Theta( n log(n)). Inputs on which quicksort takes Omega(n^2) time.

Oct 11--15

Randomized and deterministic selection in linear time (finding the k'th largest element in an array).

Lower bound for deterministic comparsion sorting algorithms.

Probabilistic counting (CLRS problem 5-1.)

Oct 20--22

Midterm; Amortized analysis.

Oct 25--29

Hashing. Hash tables as a data structure supporting insert(record), delete(record), search(key) in constant (expected) time. Loosely speaking, a good hash function minimizes collisions.

2-universal hashing: A random hash function from a 2-universal family gives the correct distribution on all pairs of items. View of k-universal hashing as k-wise independent random variables.

Construction of a k-universal hash family as the set of all degree k-1 polynomials over a field; e.g., for k=2, h(i) = ai+b where a and b are random elements of a field. Hashing from a universe to [m] by mapping U to itself randomly followed by an arbitrary map g from U to [m]; average case analysis of g applies. For k=2, better collision properties in the hash from U to [m] if a is non-zero in h(i)=ai+b.

Nov 1--5

Additional Hash constructions. First, h_x(m), for long string m and short random x mod p, is m evaluated at x mod p, where the entries in m are regarded coefficients of a polynomial, and that polynomial is evaluated at a random x. The punchline is that h_x(m) = h_x(m') iff the polynomial m - m' has random x as a root; polynomials of degree d have at most d roots. If degree(m) = length(m) = n, then this probability is at most n/p < 1/2 if p > 2n. Next, a 2-universal construction from Z_2^n (bit strings of length n) to Z_2, given by h_(a,b)(k) = a.k + b, where a is a random string over Z_2^n, b is a random element in Z_2, and the dot indicates dot product mod 2. Here, the point is, if k and k' are different, they differ in some bit, i. Conditioned on the settings of the other bits in a, k and k' hash to t and t' iff the following matrix equation holds: 
   (1   k_i)  ( b )  =  (t)
   (1  k'_i)  (a_i)     (t')
Since the determinant is nonzero, there is exactly one setting (out of four) for b and a_i that makes the thing true. In each case, the probability of collision can be improved through parallel repetition: For example, define H_{x,y,z}(m) to be the triple (h_x(m),h_y(m),h_z(m)); then H_{x,y,z}(m) = H_{x,y,z}(m') iff h_x(m) = h_x(m') AND h_y(m) = h_y(m') AND h_z(m) = h_z(m').

Dynamic programming. Optimal substructure property, independence of subproblems, overlapping subsubproblems. Examples: Matrix-chain multiplication and Longest Common Subsequence.

Nov 8--12

Greedy algorithms as local search: Given an arrangement, generate "neighbor" arrangments, and go to the neighbor arrangement that optimizes some criterion. Also, a greedy algorithm as an approach to recursion, more efficient than dynamic programming. For example, given the recurrence c(i,j) = min_k c(i,k) + c(k,j) + 1, a greedy algorithm may tell us that some particular k will always realize the minimum.

Example: Huffman codes. We defined a prefix code for compression of a file with known character frequencies. Huffman's algorithm generates an optimal prefix code.

Linear Programming. Examples, standard form.

Nov 15--19

Linear programming dual form, formally, and with examples. Weak duality, with proof. Formulation of graph problems as linear programs. Using both the LP constraints and the LP objective function to express intuitive constraints. Importance of the size of the linear program in terms of the original problem size.

Nov 22--26

Midterm, start of FFT, Thanksgiving

Nov 29--Dec 3

FFT algorithm, focusing on a quick way to convolve two sequences, with applications to multiplying polynomials and finding the score of all possible occurrences of a pattern in text. Coefficient v. point-value representation of polynomials. Fast (time n*log(n)) transform between the two transforms if the polynomials are evaluated at the roots of unity. Similarity between the forward and reverse transforms. Padding of polynomials with zero coefficients to get a length that is a power of 2.

Number-theoretic algorithms. Background. We want numerical alorithms that run in time polynomial in the number of bits in the input, not in the number of integers in the input (and not in the integer inputs themselves). Euclidean algorithm for gcd( a, b), based ond gcd( a, b) = gcd( b, a mod b).

Dec 6--10

Extended Euclidean algorithm, to find (x,y) from (a,b) such that ax + by = gcd(a,b). Chinese remainder theorem and algorithmic statement: how to compute mod 35 by computing separately mod 5 and mod 7. Generally, given n1, n2, n3, ... relatively prime, we need a basis c1, c2, c3,..., where ci mod nj is 1 if i=j and 0 otherwise.

Euler's phi-function phi(n) = the number of positive integers relatively prime to n, so that phi( prime p) = p - 1. Euler's theorem a^phi(n) = 1 mod (n) (without proof).

RSA cryptosystem: Encryption and Signatures. Equivalence of factoring and recovering secret key, when public key e = 3.