CSS.102.1 Mathematical Foundations of Computer Science



  • 2020 Autumn/Monsoon (Sept - Jan)


"Set theory: axioms (at the level of Halmos's Naive Set Theory), functions, permutations, equivalence relations, partitions, orders, partial orders, preorders, quasi-orders, induction, cardinality, lattices, monotone functions, fixed points;

Combinatorial structures: set systems, graphs, hypergraphs;

Algebraic structures: groups, rings, fields, polynomials, matrices, vector spaces, Markov chains, codes;

Convexity: polytopes, duality, volumes; Counting: permutation, partitions, functions, inclusion-exclusion, Mobius inversion, Polya's counting theory;

Extremal combinatorics of the Boolean cube: chains, covers, intersecting families, covers, isoperimetric inequalities, correlation inequalities, designs;

Extremal graph theory:  girth versus density, Ramsey-like theorems, Turan-Like theorems, Knesser graph;

Methods: the probabilistic, method, the linear algebra/polynomial method, the entropy method;