CS 809 Fall 2018 Course Log Date Number Topics Sources Week 1 Wed Lecture 1: 9/5 Finding the Max PB 3.7.1, 6.3.1 Record Values Jim Margulus, The evolution of the White Sox single-season home run record, 2012 (online). Fri Lecture 2: 9/7 Binomial coeffs GK 1.1, PB 3.2, Knuth ACP I 1.2.6 Binomial distribution Feller I, pp. 147 ff. Week 2 Mon Lecture 3: 9/10 Lattice path counting PB 3.5, GK 1.2 Discrete uniform dist. Chained hashing PB 3.3.1 Wed Lecture 4: 9/12 Occupancy Feller I, II.5, IV.2 David & Barton, Combinatorial Chance, pp. 70-71 Fri Lecture 5: K. Mehlhorn, Data Structures and Algorithms, v. 1 9/14 Maximum occupancy Gonnet, JACM 1981 Geometric wait time Feller I, pp. 234, 239. Week 3 Mon Lecture 6: Mosteller, 50 Challenging Problems..., p. 10. 9/17 Hypergeom. wait time PB 3.2.4 Wed Lecture 7 9/19 Combinatorial sums PB 3.8 and hypergeometric R. Roy, AMM 1987 functions Fri Lecture 8 9/21 Random permutations Inversions Feller I, pp. 256-257. Adjacent-swap sorting Baase, Computer Algorithms, 2nd ed. 2.2.5 Feller I, IX.6 (for Chebyshev inequality) Week 4 Mon Lecture 9 9/24 Cycles in permutations Feller I, pp. 257-258 Stirling numbers PB 3.7 Wed Lecture 10 9/26 Formal power series Lang, Algebra, VI.3 Generating functions I. Niven, AMM 1969 Fibonacci numbers Fri Lecture 11 9/28 Snake oil Wilf, The snake oil method for proving Bucket sorting combinatorial identities (1989) Week 5 Mon Lecture 12 10/1 Const coeff linear PB 5.4.1-2, GK 2.1.1 recurrences Ruin probabilities Feller I, XIV.2 Ladder networks Nodine, Fib. Quart. 1990 Wed Lecture 13 10/3 Inhomogeneous recurrences PB 5.4, GK 2.1.1 Mean time to ruin Feller I, XIV.3 Variance of same Bach, Stat. Prob. Lett., 1997. Fri Lecture 14 10/5 Linear recurrences with variable coefficients Explicit solution for PB 5.2 (intro) first-order case Divide and conquer PB 5.2.2 Parking Bach, A Discrete Parking Problem Week 6 Mon Lecture 15 10/8 Order > 1 linear rec's 3-way quicksort GK 2.1.2.2 Solns to homog. eqn Wed Lecture 16 10/10 3-way quicksort GK 2.1.2.2 Explicit solution Fri Lecture 17 10/12 Nonlinear recurrences GK 2.2.3, Aho and Sloane, Fib. Quart. 1973 Tate height function Bach, talk slides Week 7 Mon Lecture 18 10/15 Comparison relations GK 4.1.1, PB 4.2 Bootstrapping GK 4.1.2, PB 4.7 Asympotic series PB 4.2.3 Wed Lecture 19 10/17 Stieltjes integrals GK 4.2, Protter and Morrey 12.2 Sieve of Eratosthenes GK pp. 60-61 Euler's summation PB 4.5.1, GK 4.2.2 formula Fri Lecture 20 10/19 Euler-Maclaurin GK 4.2.2 Sums of powers Stirling's formula PB 4.5.5 Week 8 Mon Lecture 21 10/22 Sums vs. integrals PB 4.4 Asympotic integration Hardy, Orders of Infinity Dieudonne, Infinitesimal Calculus, Ch. III Wed Lecture 22 10/24 Complex analysis intro PB A.2 Power series Buck, Advanced Calculus, Appendix V Residue theorem Churchill, Complex Variables and Applications Fri Lecture 23 10/26 Darboux's method GK 4.3.1 3-way comparison sort Knuth ACP III, 5.3.1, ex. 3 Parking cont'd. Bach, op. cit. Week 9 Mon Lecture 24 10/29 Rational and algebraic functions Regular and context- Flajolet and Sedgewick, Chap. 7 free counting problems Wed Lecture 25 10/31 Darboux for algebraic GK 4.3.1 singularities Right-handed binary trees Fri Lecture 26 11/2 Quantum random walks Ambainis et al., STOC 2001 Week 10 Mon Lecture 27 11/5 Entire generating fns GK 4.3.2 Involutions Wilf, Generatingfunctionology, 5.4 Wed Lecture 28 11/7 Laplace approximation GK 4.3.3 Combinatorial sums Birthday problem Arnold, AMM Nov. 1971, 1022 ff. Fri Lecture 29 11/9 Random trees PB 7.1.1 Internal path length Knuth ACP I, 2.3.4.5 ex. 5 Week 11 Mon Lecture 30 11/12 General trees Knuth ACP I, 2.3.4.4 Random walks Louchard, BIT 26, 1986, pp. 17-34 Brownian motion Karlin and Taylor, Chapter 7 Wed Lecture 31 11/14 Donsker invariance Louchard, op. cit. principle Pairing heuristic for Karp, CS 292 notes, 1982 bin packing Expected IPL for general trees Fri Lecture 32 11/16 Random graph models Erdos and Renyi, 1960 Phase transition for isolated vertices Week 12 Mon Lecture 33 11/19 Greedy min spanning Kruskal, Proc. AMS 1956 tree algorithm Mean number of edges Course notes considered Expected total cost Wed Lecture 34 11/21 Coupon collection Feller I, pp. 224-225 Nobleman's algorithm Angluin and Valiant, JCSS 1979 for bipartite matching Fri T-day break -- no class 11/23 Week 13 Mon Lecture 35 11/26 Stochastic ordering Large deviation bounds Chernoff, Ann. Math. Stat., 1952 Nobleman's algorithm Angluin and Valiant, op. cit. on random bipartite graphs Wed Lecture 36 11/28 Martingales Grimmett and Stirzaker, 12.1 Probabilistic counting Rosenkrantz, Stochastics, 1987 Fri Lecture 37 11/30 Optional stopping Williams, 10.10 Monopolist game Bach, IPL 2007 Week 14 Mon Lecture 38 12/3 Doob martingale Grimmett and Stirzaker, p. 456 Azuma-Hoeffding ibid., 12.2 bound Geometric TSP Wed Lecture 39 12/5 Branching processes Harris, The Theory of Branching Processes Karp-Pearl search model Karp and Pearl, Art. Intell. 1983 Fri Lecture 40 12/7 Branching random walk Devroye, in Habib et al., pp. 249-314. Bounded lookahead McDiarmid and Provan, Proc. IJCAI 1991 search Week 15 Mon Lecture 41 12/10 Markov Chains Feller I, XV.1-XV.7 Metropolis Algorithm Randall, Proc. 2003 IEEE FOCS Diaconis, Bull. AMS 2009 Wed Lecture 42 12/12 Mixing Times Randall, op. cit. Coupling Diaconis, op. cit.