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.
  • References
  • Evaluation
  • Assignments and exam papers
  • Lectures

    • Announcements

    1. Quiz 1 on August 31st, in class
    2. Quiz 2 on October 31st, in class

    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.

    Assignment 1 (Due September 7th, in class)
    Assignment 2 (Due dates: Any 6 problems on each Wednesday, starting from Oct. 17th)
    Assignment 3 Submit 6 problems each Wednesday, from either of the two assignments.
    Problem set on probability Linear algebra problem set

    Lectures

    Module 1: Graph theory

    Ref: Introduction to graph theory by D. B. West
    1. Aug 10: Graph theory: Introduction, simple results related to connectivity, characterization of bipartite graphs
    2. Aug 17: Bipartite graphs continued, degree-sum formula, Mantel's theorem, trees
    3. Aug 24: Eulerian graphs: characterization, directed graphs, tournaments
    4. Aug 29: Matchings: Definition, Maximum vs. maximal matching, augmenting path, Berge's theorem
    5. Aug 31: Bipartite matching, Hall's theorem
    6. Sept 5: König-Egerváry theorem, planar graphs: definition, Euler's formula
    7. Sept 7: Characterization of planar graphs, 6-coloring, Tutte's theorem for perfect matching

      8. Module 2: Combinatorics

      Ref: Applied combinatorics by Roberts, Tesman
      An introduction to combinatorics by David Guichard

    8. Sept 12: Pigeonhole principle: applications including Chinese remainder theorem and Erdös-Szekeres theorem, permutations and combinations, counting with and without repetitions (Ref: Sections 1.1-1.3, 1.5, 1.6 of this book)
    9. Sept 18: Principle of inclusion-exclusion: Derangements, Euler's phi function, applications to counting
    10. Sept 19: Generating functions, partitions, recurrences: Fibonacci recurrence
    11. Sept 21: Regions in plane, Exponential generating functions: application to derangements
    12. Oct 3: Midsem discussion, linear recurrences with constant coefficients
    13. Oct 5: Linear recurrences continued, Catalan numbers, combinatorics of sets: largest pairwise non-intersecting family
    14. Oct 10: Sperner's theorem, Dilworth's theorem

      15. Module 3: Algebra

      Ref: Topics in Algebra by Herstein
      Algebra by Artin
    15. Oct 11: Groups: Definition, examples, basic properties, subgroups, cosets, Lagrange's theorem
    16. Oct 12: Cyclic groups, generating sets, permutation groups, Cayley's theorem, Permutations: cycle structure and sign of a permutation
    17. Oct 17: Permutations continued, normal subgroups, quotient groups, homomorphism
    18. Oct 24: Sylow's theorem (without proof), direct products and fundamental theorem of finite abelian groups (without proof), rings, integral domains, fields: definitions and examples
    19. Oct 26: Properties of finite fields, construction of finite fields from polynomial rings, vector spaces: definition, dimension, linear independence, basis
    20. Oct 30: Linear transformations, rank-nullity theorem
    21. Nov 2: Change of basis, elementary matrices, row echelon form, system of linear equations, determinant, inner product, Cauchy-Schwartz inequality (proof left as exercise), orthgonality, eigenvalues and eigenvectors, characteristic polynomial, eigenvalues and eigenvectors of real symmetric matrices

      22. Module 4: Probability

      Ref: A first course in probability by Sheldon Ross, Randomized algorithms by Motwani, Raghavan

    22. Nov 7: Basic concepts, conditional probability and independence, Bayes' formula, random variables and expectation, linearity of expectation
    23. Nov 9: Discrete random variables: Bernoulli, binomial, negative binomial, geometric, poisson; variance
    24. Nov 13: Coupon collector's problem, Tail inequalities: Markov's and Chebyshev's inequalities, Probabilistic method: Lower bound on the maximum number of Hamiltonian paths in a tournament
    25. Nov 14: Chernoff bound, maximum likelihood estimate, continuous random variables: probability density function, uniform and normal random variables

      26. Module 5: Applications

    26. Nov 16: Entropy and error correcting codes: Entropy, noiseless coding theorem, rate of a code, noisy coding theorem for binary symmetric channel, simple examples: error correction by repetition, error detection using parity bits
    27. Nov 19: Error correcting codes continued: [7,4] Hamming codes: encoding and parity check matrices, distance, rate, linear codes, Singleton bound, Reed-Solomon codes
      Group actions: Burnside's lemma, application to counting 2-colorings of a chessboard (Ref)
    28. Nov 20: Markov chains: Definition, irreducibility, aperiodicity, stationary distribution, Fundamental theorem of Markov chains (without proof), Example: Random walks on regular, undirected graphs (Ref)