Discrete Math I Math 850 Fall 2012 Class Log

1. Aug 20, Mon. course overview and logistics; initial student survey; what is combinatorics? Sec 1.1: basic counting principles: sum, product, counting in two ways, bijection
2. Aug 22, Wed. ways to pick k objects from an n-set; permutations; combinations; binomial coefficients; binomial theorem; polynomial principle; multisets; stars and bars; compositions
3. Aug 24, Fri. Sec 1.2: basic identities for binomial coefficients; Pascal's identity; sums of binomial coefficients, sums of powers of integers; Vandermonde convolution; lattice paths; Delannoy paths and numbers
4. Aug 27, Mon. size of balls in the l1 metric; have the same cardinality; extended binomial coefficients; extended binomial theorem; multinomial coefficients; multinomial theorem; basic identities
5. Aug 29, Wed. Fermat's Little Theorem; Sec 1.3: Bertrand's ballot theorem; reflection principle; related counting of lattice paths
6. Aug 31, Fri. Catalan numbers; bijections with parenthesization, ordered rooted binary trees Sec 2.1: recurrences; counting subsets; Fibonacci numbers; induction proofs involving recurrences
Sep 3, Mon. Labor Day - no class
7. Sep 5, Wed. discussion of homework; bijection proof with Fibonacci numbers; derangements, 2 recurrences; showing that a collection is counted by a sequence by showing it satisfies the recurrence; Catalan example of triangulating polygons
8. Sep 7, Fri. recurrences of multiple parameters; recurrence for Delannoy paths and balls in Z^n with radius m in the l_1 metric; Sec 2.2: solving homogeneous linear recurrences of finite order with constant coefficients; solution sequences form a vector space of dimension k; roots of characteristic polynomial give exponential solutions; formula for Fibonacci numbers
9. Sep 10, Mon. general solution for repeated roots in the characteristic polynomial; example; method for inhomogoneous recurrences; form of solutions for recurrences with inhomogeneous parts that are polynomials times exponentials
10. Sep 12, Wed. method for inhomogoneous recurrences; regions in the plane determined by n lines; generating functions; Fibonacci example
11. Sep 14, Fri. relation of characteristic polynomial to form of generating function; partial fractions and repeated roots; generating function method for inhomogoneous recurrences; regions in the plane determined by n lines; power series for powers of 1/(1-cx); generating function for the Catalan numbers
12. Sep 17, Mon. finished generating function for the Catalan numbers; example of generating function for multiply indexed sequence; Sec 3.1: combinatorial constructions of generating functions; making change with coins problem
13. Sep 19, Wed. discussion of convolutions; generating function for choosing multisubsets; permutation statistics; counting permutations by number of inversions, and generating function; counting permutations by number of cycles: recurrence and generating function; counting permutations by number of runs: Eulerian numbers
14. Sep 21, Fri. No lecture.
15. Sep 24, Mon. Worpitzky's identity; formula for Eulerian numbers; Sec 3.2: relationship between operations on sequences and their generating functions; simple examples; convolutions
16. Sep 26, Wed. Snake Oil; examples involving Fibonacci numbers, Delannoy numbers, and number of permutations with given number of cycles Sec 3.3: exponential generating functions; binomial convolution; words over an alphabet
17. Sep 28, Fri. encoding restrictions on words over an alphabet; flags on flagpoles; ordered partitions; Stirling numbers of the second kind
18. Oct 1, Mon. Stirling numbers of the first and second kind; polynomial bases; solving linear recurrences with constant coefficients using exponential generating functions
Oct 2, Tues. Test #1
19. Oct 3, Wed. binomial inversion formula; formula for derangement numbers; counting labeled graphs; counting labeled connected graphs
20. Oct 5, Fri. the exponential formula; examples; recurrence for c_n
21. Oct 8, Mon. returned Test 1; Sec 3.4: Twelvefold Way; partition numbers; OGF; asymptotics for partitions when bound on the part size
22. Oct 10, Wed. bijections between different types of partitions; Ferrers diagrams; triangles with integer side lengths; Euler's identity; Sec 4.1: Principle of Inclusion-Exclusion; proof
23. Oct 12, Fri. examples of PIE: derangement numbers, Stirling numbers of the second kind, multisets with bounded repetition number; evaluating sums
Oct 15, Mon. Fall break, no class.
24. Oct 17, Wed. discussion of informal feedback survey; Eulerian numbers; restricted permutations; rook polynomials; seating men and women around a table
25. Oct 19, Fri. Sec 4.2: counting under the presence of symmetry; batons; counting orbits of colorings; stabilizers; Burnside's lemma
26. Oct 22, Mon. application to batons and 4-bead necklaces; cycle structure, cycle index, pattern inventory; applications to batons and 4-bead necklaces; counting isomorphism classes of graphs with fixed number of edges
27. Oct 24, Wed. counting isomorphism classes of graphs with fixed number of edges; coloring the cube; using the pattern inventory to enumerate by cost (Pólya-Redfield counting)
28. Oct 26, Fri. counting binary strings under cyclic rotation; introduction to coding theory; encoding/channel/decoding model; binary repetition code; binary symmetric channel (BSC) and q-ary symmetric channel; statement of negative part of Shannon's theorem
29. Oct 29, Mon. error of a decoder; calculation of binary repetition code on BSC; maximum likelihood decoder; maximum a posteriori decoder; conditional probability; equivalence of MLD and MAPD under the assumption that all codewords are equally likely; Hamming distance
30. Oct 31, Wed. nearest neighbor decoding; minimum distance d of a code; can correct floor((d-1)/2)) errors; can detect d-1 errors; parity check code; sphere packing bound; definition of perfect codes; binary repetition code with n odd is perfect
31. Nov 2, Fri. k=dimension of a code; Singleton bound; linear codes; parameters; generator matrix; generator matrix; in systematic form; minimum distance and minimum weight of a codeword; parity check matrix
32. Nov 5, Mon. forming the parity check matrix from a generator matrix in systematic form; examples; computing the min distance from the parity check matrix
33. Nov 7, Wed. standard array decoding; syndrome decoding; example
34. Nov 9, Fri. parameters of codes for CDs, DVDs, and digital television; binary Hamming codes; discussion of statement of Shannon's Theorem
35. Nov 12, Mon. review of discrete probability: probability spaces; real-valued random variables; expectation; linearity of expectation; variance; variance of sums of independent random variables; Markov's Inequality; Chebyshev's Inequality; examples of Bernoulli and binomial random variables
Nov 13, Tues. Test #2
36. Nov 14, Wed. entropy of a random variable; election example; average decoding failure; Shannon's theorem; first part of the proof
37. Nov 16, Fri. finished proof of Shannon's theorem
38. Nov 19, Mon. probability of decoding failure vs minimum distance; asymptotic bounds; asymptotic Singleton bound; asymptotic sphere-packing bound; Gilbert-Varshamov bound and asymptotic version
Nov 21, Wed. — Nov 23, Fri. Thanksgiving break, no class.
39. Nov 26, Mon. definition of generalized Reed-Solomon codes; parameters: length, dimension, minimum distance; generator matrix and Vandermonde determinant; Lagrange interpolation
40. Nov 28, Wed. dual code of a generalized Reed-Solomon code is a generalized Reed-Solomon code; parity check matrix; syndrome polynomial; error locator polynomial and error evaluator polynomial; Key Equation
41. Nov 30, Fri. No class.
42. Dec 3, Mon. solving the Key Equation for generalized Reed-Solomon codes; uniqueness of solutions
43. Dec 5, Wed. extended Euclidean algorithm approach to decoding Reed-Solomon codes; Reed-Muller codes and parameters
44. Dec 7, Fri. overview of modern coding theory; probabilty of decoding failure vs minimum distance; turbo codes; LDPC codes; iterative, soft decoding
Dec 13, Thurs, 10:00am-12:00pm. Final Exam

    Back This page last modified .