Theoretical Foundations of Computer Science

The goal of the course is to brush up and build basic concepts and background required for other theoretical courses, with an emphasis on writing clear, precise proofs of mathematical statements. There are four modules: Graph theory, Combinatorics, Algebra, Probability with some possible overlap of topics across modules.

Announcement:

Quiz in class on September 1st

References

There is no single textbook for the course. I will post references for each topic. Most of the references will be available online. Top

Evaluation

There will be assignments, two quizzes, a mid-semester exam, an end-semester exam, The weightage is 10% for assignments, 20% for two quizzes, 30% for midsem, 40% for endsem.

Top

Assignments

Note that copying in assignment will lead to a fail grade, irrespective of your performance in exams. No discussions or online references are encouraged. If at all you do consult someone or something, mention his/her/its name in your assignment submission alongwith the relevant question number.

Lectures

Module 1: Graph theory

  1. Aug 8: Graph theory: Introduction, simple results related to connectivity, degrees of vertices (Ref: Chapter 1 of D.B. West's book)
  2. Aug 11: Trees, Bipartite graphs, Mantel's theorem, Eulerian circuits, Directed graphs
  3. Aug 18: Tournaments, Matchings: Augmenting paths, Berge's theorem (Chapter 3 of D B West's book)
  4. Aug 22: Hall's theorem, König-Egerváry theorem (Chapter 3 from D B West's book)
  5. Aug 29: Planar graphs: Introduction, Euler's formula, characterization, coloring (Ref: Relevant topics from Chapter 6 of D B West's book)
  6. Sept 11: Tutte's theorem (Ref: D B West's book)

    7. Module 2: Combinatorics

  7. Sept 5: Pigeonhole principle, counting: permutations combinations, cardinalities of sets (Ref: These notes and Sections 1.1-1.3, 1.5, 1.6 of this book)
  8. Sept 8: Erdös-Szekeres theorem, Principle of inclusion-exclusion
  9. Sept 12: Derangementes, Generating functions: partitions (Ref: Roberts, Tesman book)
  10. Sept 15: Recurrence relations: Regions in plane, generalized binomial coefficients, solving linear recurrence relations with constant coefficients, derangements using exponential generating functions (Ref: Roberts-Tesman book)
  11. Sept 19: Catalan numbers (number of simple, ordered, rooted trees), Combinatorics of sets: Sperner's theorem (Ref: Robert-Tesman book, Anderson's book)
  12. Sept 22: Posets, Dilworth's theorem (Ref: Anderson's book)

    Module 3: Algebra (Ref: Topics in Algebra by Herstein)

    Sept 22: Groups: Definition, basic properties, subgroups, cosets, Lagrange's theorem, Fermat's little theorem, cyclic groups
  13. Oct 3: Homomorphisms, normal subgroups, quotient groups
  14. Oct 6: Permutation groups, Cayley's theorem, cycle structure and sign of permutations, uniqueness of sign, Sylow's theorem (without proof), Direct product and fundamental theorem on finite abelian groups (without proof)
  15. Oct 9: Rings and Fields: Definition and examples, integral domain, ideals, properties of finite fields, polynomial rings, construction of finite fields from polynomial rings
  16. Oct 13: Construction of finite fields continued, Vector spaces: definition, dimension, linear independence and basis
  17. Oct 24: Vector spaces, inner product, Cauchy-Schwartz inequality, linear transformations, rank-nullity theorem, orthogonality (Ref: Artin's book)
  18. Oct 27: Linear algebra continued: Matrices and system of linear equations, determinant, characteristic polynomial, eigenvalues and eigenvectors

    19. Module 4: Probability (Ref: A first course in probability by Sheldon Ross [SR], Randomized algorithms by Motwani, Raghavan [MR])

  19. Nov 4: Definitions and basic formulae: Sample space, events, conditional probability, examples [SR]
  20. Nov 6: Independent events, random variables and expectation, discrete random variables: Bernoulli, Binomial, Introduction to probabilistic method: 2-edge-coloring of an n-clique with no monochromatic k-clique [SR]
  21. Nov 7: Discrete random variables: Poisson, Geometric, Negative binomial, Applications: Coupon collector's problem [MR], probabilistic method: maximum number of Hamiltonian paths in a tournament, Maximum likelihood estimate [SR]
  22. Nov 10: Continuous random variables: uniform, Gaussian, exponential. Probability density function and cumulative distribution function, expectation, variance.
  23. Nov 13: Joint distribution, independence, Markov's inequality
  24. Nov 14: Covariance, Chebyshev's inequality [SR], Chernoff bounds (Ref). Example: Hat matching

    25. Module 5: Applications

  25. Nov 4: Group action, orbit-stabilizer theorem, Burnside's lemma, examples: colorings of chessboard, colorings of faces of a cube (Ref: Alon-Slomson's book)
  26. Nov 17: Markov chains: Irreducibility, aperiodicity, stationary distribution. Example: Random walks in regular, undirected graphs (Ref)
  27. Nov 20: Random walks continued, Introduction to coding theory: Entropy, prefix-codes
  28. Nov 21: Introduction to coding theory continued: Noiseless coding theorem, Noisy coding theorem, Huffman codes, Hamming codes, Reed-Solomon codes