COL7004: Mathematical Foundations of Computer Science



Course Information

Instructor: Keerti Choudhary

Lecture Timing: Mon, Thurs   8:00-9:30 AM   (LH 613)

Tutorial Timing: Tues, Fri   1:00-2:00 PM   (Block IV, LT 1)

Reference Books:
1. Mathematics for Computer Science, by E. Lehman, F.T. Leighton. A. R. Meyer
2. Effective Theories in Programming Practice, by Jayadev Misra
3. Design and Analysis of Algorithms: A Contemporary Perspective, by Sandeep Sen and Amit Kumar (online version a https://www.cse.iitd.ac.in/~ssen/col702/root.pdf)
4. Linear Algebra and Its Applications, by Gilbert Strang

TAs: Serene Rasheed (csz258234@cse.iitd.ac.in), Sukriti Gupta (csz258469@cse.iitd.ac.in), Haleel Sada N P (mcs252741@cse.iitd.ac.in).

Logistics

Evaluation: The course evaluation policy is:

  • Exams - 35% + 40%
  • Surprise quizzes (best n-1 out of n) - 15%
  • Attendance - 6% (Lectures) + 4% (Tutorials)

Passing criteria: 30% in course total

Audit-pass criteria: 45% in course total

Acadmic Honesty: Cheating or allowing anyone to copy would lead to a penalty of one grade per quiz / exam.

Policy on missed evaluations: There will be no re-test for minor-exam and quizzes. If the minor exam is missed due to a valid medical reason, marks will be scaled from the major exam (subject to submission of IIT Delhi medical certificate).

Course Content


Module 1: Discrete Structures & Logic (~ 6 Lectures)
Sets, Set Identities, Functions, Relations, Equivalence Classes, Logic (Propositional & Predicate)

Module 2: Proof Techniques & Graph Algorithms (~ 7 Lectures)
Proof by Contradiction, Well Ordering Principle, Induction, Pigeon Hole Principle, Counting arguments, Inclusion-Exclusion, Diagonalization, Graph Algorithms (DFS, BFS, TopSort, Loop Invariants)

Module 3: Probability & Hashing (~ 6 Lectures)
Probability, Distributions, Random Variables, Linerity of Expectation, Concentration Bounds, Hashing

Module 4: Algebraic Structures (~ 3 Lectures)
Groups, Rings, Fields

Module 5: Linear Algebra & Vector Spaces (~ 6 Lectures)
Vector Spaces, Basis, Dimension, Linear Transformations, Inner Products, Orthonormality, Eigen values, SVD