CS 30: Discrete Math in CS
Spring 2025 | 10 hour (MWF 10:10—11:15; Th 12:15—13:05) | ECSC 116
Professor Amit Chakrabarti
Home Schedule Assessment Policies

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

The Course's Rhythm

After going over some prerequisites on the first day of classes, the course will be divided into nine modules, corresponding to our nine-week term. Each such module will run from one Wednesday to the following Tuesday, as follows

  • Lecture class on Wednesday.
  • Working session on Thursday (x-hour).
  • Lecture class on Friday.
  • Working session on Monday, which requires advance preparation from students.
  • Homework: early submission deadline on Monday night at 11:59 pm.
  • Homework: final deadline on Tuesday night at 10:00 pm.

As you can see, we'll be using every X-hour.

For each module, a single document called Notes and Problems will be made available on Canvas. The lecture notes are meant to be read and re-read closely, but they are not a replacement for a textbook. The problems will fall into three categories.

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

Expectations and Deadlines

You should read through a module's notes soon after the Wednesday class that starts the module. In fact, doing some pre-reading before Wednesday's class is encouraged. In Thursday's working session, you'll do some of the early problems from the module: 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 section leader who'll be in the class for this purpose).

In Friday's class, I'll wrap up my presentation of the module, but a good portion of the learning won't yet get done, because this learning consists of you solving the module's remaining problems. This will happen during Monday's working session, for which you should come prepared with written up solution sketches. Your Ninja will verify your preparedness (there will be a grading incentive for this) and then, as usual, you will present some solutions on a whiteboard.

By the end of each Monday class, you should be at least 80% done with your homework, which consists of all the problems (shown in blue boxes) from the module. You should aim to submit your homework by 11:59 pm that same night; doing so earns you some bonus credit towards your grade. We will continue to accept submissions until the late deadline of 10:00 pm the following night (i.e., Tuesday night), but no later than that. Submissions should be made on Gradescope (linked from the Canvas page).

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.

Exams

We have three in-class exams.

  • Midterm exam 1 will be held on Thu Apr 24 from 6:30 to 8:30 pm in location TBD. It will be based on Modules 1, 2, and 3.
  • Midterm exam 2 will be held on Thu May 15 from 6:30 to 8:30 pm in location TBD. 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 Sat Jun 7 from 8:00 to 11:00 am in location TBD, 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.