CS 30: Discrete Math in CS
Winter 2024 | 10A hour (TTh 10:10—12:00; F 15:30—16:20) | ECSC 008
Professor Amit Chakrabarti

Any content that's colored light gray is tentative and subject to change.

The Course's Rhythm

The course will be divided into nine modules, corresponding to our nine-week term. Each module will run from one Wednesday to the following Tuesday, with a problem set due on that Tuesday night. I will include some notes and background material with each problem set.

For each module, a single document called Notes and Problems will be made available on Canvas. There will be three categories of problems in this document.

  • Exercises: things that I'll do on the board in class. Solutions to these exercises will be included at the end of the document.
  • Graded problems: things that you'll need to submit by Tuesday night. Some of these problems will be done as in-class exercises.
  • Extra-credit problems: things I encourage you to do if you want to go deeper into the subject.

You should definitely read through these notes before Thursday's class. On Thursday, we'll have a mix of lecture and a working session where you'll do some of the early graded problems from the module. During the working session, you'll be organized into small groups to discuss the problems and present a written solution on a whiteboard to a Discrete Math Ninja (our term for a TA who'll be in the class for this purpose).

On Friday, during the x-hour, we'll have a lecture session where I'll discuss more of the module's content. Please follow up by re-reading the module's notes and prepare for the next class by working through the remaining exercises and the graded problems. (As you can see, we'll be using every X-hour.)

On Tuesday, we'll again have a mix of lecture and working session, but unlike the Thursday class, you're expected to come in with prepared solutions that you'll present to your partners and Ninja. By the end of this class, you should be at least 80% done with your homework. The homework consists of all the graded problems from the module. The homework needs to be submitted on Gradescope by 11:00 pm sharp that night.

Please read the policies section of the course website for submission instructions, the lateness policy (which is absolutely strict), grading standards, and the academic honor principle.

The Modules

The nine modules will cover the following topics. Some of this is subject to change and adjustment as the term progresses.

  1. Mathematical data types and notation. Sets, relations, and functions.
  2. Getting used to writing proofs. Examples involving divisibility, rationality, basic algebra.
  3. Logic and logical notation: propositions, predicates, quantifiers. More proofs (especially, by contradiction).
  4. Proof by induction. Basic counting principles. Counting subsets. Binomial coefficients.
  5. Probability spaces, events, conditioning, independence.
  6. Random variables, expectation, linearity, distributions.
  7. Graphs. Degrees, walks, paths, cycles, connectivity. Trees.
  8. Tree theorem. Bipartite graphs, matchings.
  9. More advanced theorems about graphs: Hall's and Koenig's theorems.


We have three in-class exams.

  • Midterm exam 1 will be held on Thu Jan 25 from 6:30 to 8:30 pm in ECSC 009. It will be based on Modules 1, 2, and 3.
  • Midterm exam 2 will be held on Thu Feb 15 from 6:30 to 8:30 pm in ECSC 009. It will be based on Modules 4, 5, and 6. Keep in mind that these modules will have built on the earlier ones.
  • The final exam will be held on Mon Mar 11 from 8:00 to 11:00 am in ECSC 008, as scheduled by the Registrar's Office. It will be based on all the modules, with a strong emphasis on Modules 7, 8, and 9.