Math3825A/Math3855A/Comp3805A

Discrete Structures and Applications

 
Course Outline

TA: Goldwyn Miller.

Topics covered in the class

  • Jan. 7: Introduction & Addition principle, Pigeonhole principle.
  • Jan. 12: Generalized pigeonhole principle, counting pairs, multiplication rule.
  • Jan. 14: Euler's Theorem, ordered selections with repetition, ordered selections without repetitions, permutations
  • Jan. 19: binomial numbers, properties of binomial numbers, unordered selection with repetition.
  • Jan. 21: count the number of integer solutions, sieve principle.
  • Jan. 26: derrangements, compute Euler function.
  • Jan. 28: designs
  • Feb. 2: t-designs, Partition of a set,
  • Feb. 4: distributions, multinomial coefficients.
  • Feb. 9: Multinomial thoerem, partition of integers, power series
  • Feb. 11: Partial fractions.
  • Feb. 15-19: reading week.
  • Feb. 23: Binomial Theorem for negative exponent. generating functions and linear recursion.
  • Feb. 25: Midterm
  • Mar. 1: Homogenous linear recursiion.
  • Mar. 3: Nonhomogenous linear recursion, partitions of integers and conjugate partitions
  • Mar. 8: generating function of partitions of a positive integer.
  • Mar. 10: restricted partitions
  • Mar. 15: graphs, degree sequences, Halmitonian cycles and Eulerian walks.
  • Mar. 17: Eulerian walks, trees, vertex coloring,
  • Mar. 22: planar graphs
  • Mar. 27: planar graphs, introduction to coding theory.
  • Mar. 29: linear codes basics, a game.
  • Mar. 31: Hamming codes;
  • Apr. 5: Decoding 1 error; Cyclic codes.
  • Apr. 7: Reviews.
  •  
    Tutorials, Assignments, Solutions They can be found in CULearn.