## 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

9. 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)
10. Sept 18: Principle of inclusion-exclusion: Derangements, Euler's phi function, applications to counting
11. Sept 19: Generating functions, partitions, recurrences: Fibonacci recurrence
12. Sept 21: Regions in plane, Exponential generating functions: application to derangements
13. Oct 3: Midsem discussion, linear recurrences with constant coefficients
14. Oct 5: Linear recurrences continued, Catalan numbers, combinatorics of sets: largest pairwise non-intersecting family
15. Oct 10: Sperner's theorem, Dilworth's theorem
16. #### Module 3: Algebra

Ref: Topics in Algebra by Herstein
Algebra by Artin
17. Oct 11: Groups: Definition, examples, basic properties, subgroups, cosets, Lagrange's theorem
18. Oct 12: Cyclic groups, generating sets, permutation groups, Cayley's theorem, Permutations: cycle structure and sign of a permutation
19. Oct 17: Permutations continued, normal subgroups, quotient groups, homomorphism
20. 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
21. Oct 26: Properties of finite fields, construction of finite fields from polynomial rings, vector spaces: definition, dimension, linear independence, basis
22. Oct 30: Linear transformations, rank-nullity theorem
23. 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
24. #### Module 4: Probability

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

25. Nov 7: Basic concepts, conditional probability and independence, Bayes' formula, random variables and expectation, linearity of expectation
26. Nov 9: Discrete random variables: Bernoulli, binomial, negative binomial, geometric, poisson; variance
27. 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
28. Nov 14: Chernoff bound, maximum likelihood estimate, continuous random variables: probability density function, uniform and normal random variables
29. #### Module 5: Applications

30. 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
31. 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)
32. Nov 20: Markov chains: Definition, irreducibility, aperiodicity, stationary distribution, Fundamental theorem of Markov chains (without proof), Example: Random walks on regular, undirected graphs (Ref)