Site menu:

Lecture notes

Some slides are based on the slides in MIT 6.042 (Spring 2007).

Lecture 0: about the course [slides] [pdf]
Lecture 1: sets [slides] [pdf]
  • Read chapter 5 of the textbook.
Lecture 2: basic counting [slides] [pdf]
  • Read chapter 6.2-6.4 of the textbook.
Lecture 3: binomial coefficients, inclusion-exclusion principle [slides] [pdf]
  • Read chapter 6.3 and 6.6-6.7 of the textbook.
Lecture 4: functions, pigeonhole principle [slides] [pdf]
  • Read 7 of the textbook.
Lecture 5: counting by mapping [slides] [pdf]
  • Read Chapter 6.4-6.5 of the textbook, and Chapter 10.1, 10.5, 11.3 of the notes.
Lecture 6: more counting by mapping [slides] [pdf]
  • Read Chapter 6.4-6.5 of the textbook, and Chapter 10.1, 10.5, 11.3 of the notes.
Lecture 7: number sequences [slides] [pdf]
  • Read Chapter 4.1 of the textbook, and Chapter 9.1 and 9.2 of the reference notes.
Lecture 8: recursion [slides] [pdf]
  • Read Chapter 8.1-8.2 of the textbook.
Lecture 9: solving recurrence [slides] [pdf]
  • Read Chapter 8.3 of the textbook.
Lecture 10: propositional logic [slides] [pdf]
  • Read Chapter 1.2 and 1.3 of the textbook.
Lecture 11: first order logic [slides] [pdf]
  • Read Chapter 2 of the textbook.
Lecture 12: methods of proofs [slides] [pdf]
  • Read Chapter 3 of the textbook, except 3.5 and 3.8.
Lecture 13: mathematical induction [slides] [pdf]
  • Read Chapter 4.2 and 4.3 of the textbook, and Chapter 3.3 and 3.4 of the reference notes.
Lecture 14: mathematical induction II [slides] [pdf]
  • Read Chapter 4.4 of the textbook, and Chapter 3.5 and 3.6 of the reference notes.
Lecture 15: introduction to graphs [slides] [pdf]
  • Read Chapter 11.1,11.2,11.4,11.5 of the textbook.
Lecture 16: graph matching [slides] [pdf]
  • Read Chapter 5.1 and 6.2 of the notes.
number theory: greatest common divisors [slides]
number theory: modular arithmetic [slides]
number theory: Chinese remainder theorem [slides]
number theory: cryptography [slides]
graph coloring [slides]