Discrete Mathematics in Computer Science (SU21)

The Summer 2021 edition of CS 30 has ended, and this page is open to the public.

In the links below one can find the relevant lecture notes and assignments. However, the solutions have been locked, and I won't make them available. 

The course loosely followed the following excellent text by David Liben-Nowell, Discrete Mathematics for Computer ScienceThis book is available online!

Tentative Schedule

25th June Lecture 1 : Jargon I : Sets
28th June Lecture 2 : Jargon II : Functions
29th June (X hour) Lecture 3 : Jargon III : Propositional Logic
30th June Lecture 4 : Jargon IV : Predicate Logic
2nd July Lecture 5 : Proof via Contradiction
6th July (X hour) Lecture 6 : Induction
7th July Lecture 7 : Strong Induction
9th July Lecture 8 : Proving Recursive Programs Correct
12th July Lecture 9 : Combinatorics I : Product and Sum Principle
13th July (X hour) Lecture 10 : Combinatorics II : Bijection and Division Principle
14th July Lecture 11 : Combinatorics III : Four Fold Formula
16th July Lecture 12 : Combinatorics IV : Binomial Expansion and other Combinatorial Identities
Review (for Midterm on 29th July) Preparing for Midterm (7/29)
19th July Lecture 13 : Probability I : Basics
20th July (X hour) Lecture 14 : Probability II : Conditional Probability & Independence
21st July Lecture 15 : Probability III : Bayes Rule
23rd July Lecture 16 : Probability IV : Random Variables
26th July Lecture 17 : Probability V : Expectation
28th July Lecture 18 : Probability VI : Variance
29th July Midterm
30th July Lecture 19 : Probability VII : Deviation Inequalities
2nd Aug Lecture 20 : Graphs I : Basics + Handshake Lemma
4th Aug Lecture 21 : Graphs II : Perambulations and Connectivity
6th Aug Lecture 22 : Graphs III : Trees
9th Aug Lecture 23 : Graphs IV : Bipartite Graphs
11th Aug Lecture 24 : Graphs V : Matchings and Hall's Theorem
13th Aug Lecture 25 : Graphs VI : Application of Hall's Theorem
16th Aug Lecture 26 : Numbers I : Modular Arithmetic and Modular Exponentiation
17th Aug (X hour) Lecture 27 : Numbers II : GCD and Bezout's Identity
18th Aug Lecture 28 : Numbers III : Multiplicative Inverses
20th Aug Lecture 29 : Numbers IV : Fermat's Little Theorem
23rd Aug Lecture 30 : Numbers V : Public Key Crypto + RSA
25th Aug Lecture 31 : Conclusion + Halting Problem (not on the final)
Review (for Final on 29th August) Preparing for Final (8/29)
29th Aug, 8:00am In class Finals at LSC 100