CSS.102.1 Mathematical Foundations for Computer Science

print

Instructor: 

Arkadev Chattopadhyay
Jaikumar Radhakrishnan

Semester: 

  • 2021 Autumn/Monsoon (Aug - Dec)
  • 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;