Sometimes techniques already available in one branch of science wait to be rediscovered in some disguise in another. This is particularly true for mathematics and computer science.
This graduate course will cover topics in discrete mathematical methods and combinatorics with applications to the solution of problems in computer science. We will consider topics in classical combinatorial methods and algorithms for selected problems in Algorithmic graph theory, classes of trees, enumeration methods, Lagrange inversion, number theory and primality testing, dynamic and fractional programming, FFT, Markov chains and random generation.
The previous times this course was offered (2009, 2013, 2016), the following topics were covered:
Review of basics of counting: Formal languages, Dyck paths, Young tableaux, Catalan structures, injective words, increasing words, lower and upper factorial polynomials, Stirling numbers, permutations, cycle diagrams, permutation statistics, languages for permutations and set partitions
Chu-Vandermonde summation formula
Integer partitions, Ferrers' diagrams, combinatorial object manipulation, q-identities, Gaussian polynomials, q-binomial identity
Binary trees, generating functions and the Lagrange inversion theorem, planar trees, bijections
Cayley trees, Prüfer code, other tree codes, q-analogues, generalizations
Exponential structures and polynomials, exponential formula
Partially ordered sets, the Möbius inversion theorem, applications
Graph coloring, applications in register allocation, pattern matching
Primality testing, quadratic reciprocity, Legendre symbols
Arrow's theorem, public preference paradoxes, Borda, Condorcet voting rules
Additional possible topics are
· Classes of graphs: chordal, outerplanar, interval graphs, linear time planarity algorithm
· Dynamic and fractional programming
· MacMahon's Master theorem and applications
When / where: TR, 1:00-2:45 Phelps 3526.
Organizational meeting is on Tuesday, January 9, 2018.