COL 7004: Mathematical Foundations of Computer Science

Assignments

Lecture Topics

• Lecture 1: Introduction to the course, Sets, Functions ([1] Chapter 4, [2] Chapter 2)
  
• Lecture 2: Functions, Relations, Equivalence Classes ([1] Chapter 4, [2] Chapter 2)
  
• Lecture 3: Propositional Logic, deduction rules, Conjunctive Normal Form ([1] Chapter 3, [2] Chapter 2)
  
• Lecture 4: Predicate calculus, deduction rules, proof techniques. ([2] Chapter 2)
  
• Lecture 5: Proofs by contradiction, countable and uncountable sets. ([1] Chapter 1, Chapter 7)
  
• Lecture 6: Diagonalization, Pigeonhole Principle. ([1] Chapter 7, Chapter 14.8)
  
• Lecture 7: Mathematical Induction ([1] Chapter 5, [2] Chapter 3)
  
• Lecture 8: Program development using invariants([1] Section 5.4, [2] Chapter 4.6-4.8)
  
• Lecture 9: Counting using recurrences ([1] Chapter 15)
  
• Lecture 10: Generating functions, introduction to probability ([1] Chapter 16, 18)
  
• Lecture 11: Random variables, basic inequalities, linearity of expectation ([1] Chapter 18, 19)
  
• Lecture 12: Applications of linearity of expectation ([1] Chapter 18).
  
• Lecture 13: Variance and Chebychev Inequality ([1] Chapter 19)
  
• Lecture 14: Central Limit Theorem, Weak Law of Large numbers and Continuous distributions: normal, exponential, uniform. ([1] Chapter 19)
  
• Lecture 15: Universal Hashing, skip lists. ([3], Chapter 6)
  
• Lecture 16: Introduction to vector spaces, basis ([4] Chapter 2)
  
• Lecture 17: Change of basis, dimension ([4] Chapter 2)
  
• Lecture 18: Linear transformation, matrix representation and change of basis ([4] Chapter 2)
  
• Lecture 19: Inner product, orthonormality ([4] Chapter 3.1, 3.4)
  
• Lecture 20: Eigenvalues, singular values and some applications ([4] Chapter 5.1-5.3, 6.3 )
  
• Lecture 21: Graphs: basic notions, depth first search ([2] Chapter 6.6)
  
• Lecture 22: Graphs: topological sort, breadth first search ([2] Chapter 6.6, [1] Chapter 9)
  

Course Contents

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
  

Grading (tentative)