CS 30: Discrete Mathematics in Computer Science
Winter 2018 | 10A hour (TTh 10:10-12:00, x-hr W 15:30-16:20) | LSC 200

This page will be updated frequently with current and upcoming topics.

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

Topics Day-by-Day

References to the recommended textbooks are made as follows: [LLM] is the Lehman-Leighton-Meyer book, and [Ros] is the Rosen book. The notation [LLM 4.1,4.2] means "sections 4.1 and 4.2 of the Lehman-Leighton-Meyer book", the notation [Ros Ch 6] means "chapter 6 of the Rosen book", and so on.

1Th Jan 4Sets and relations Slides
[LLM 4.1, 4.4]; [Ros 2.1, 2.2]
2Tu Jan 9Functions Slides
[LLM 4.2, 4.3, 4.5]; [Ros 2.3, 2.5]
3Th Jan 11Logic and quantifiers Slides
[LLM 3.1–3.3, 3.6]; [Ros 1.1–1.5]
4Tu Jan 16Styles of proof; Counting: sum principle Slides
[LLM Ch 1, 15.1, 15.2]; [Ros 1.6–1.8, 6.1]
5Th Jan 18Product and division principles; Subsets Slides
[LLM 15.1–15.7] [Ros 6.1, 6.3]
6Tu Jan 23Binomial coefficients; A taste of mathematical induction Slides
[LLM 15.5–15.7, 15.10, 5.1]; [Ros 6.3–6.5, 5.1]
XW Jan 24Binomial coefficients wrap-up  
7Th Jan 25Mathematical induction; Inclusion-Exclusion principle Slides
[LLM 5.2, 5.3, 15.9]; [Ros 5.2, 5.3, 8.5, 8.6]
8Tu Jan 30Probability: sample spaces, events Slides
[LLM Ch 17]; [Ros 7.1, 7.2]
XW Jan 31(Review session for Midterm 1)  
9Th Feb 1Conditioning, independence Slides
[LLM Ch 18]; [Ros 7.2, 7.3]
10Tu Feb 6Random variables, expectation, linearity Slides
[LLM 19.1, 19.2, 19.5]; [Ros 7.2, 7.4]
11Th Feb 8Probability distributions, variance Slides
[LLM 19.3, 19.4]; [Ros 7.4]
12Tu Feb 13Deviations Notes
[LLM 20.1–20.4]; [Ros 7.4]
13Th Feb 15Graphs: (un)directed, degrees, walks, paths, cycles Slides
[LLM 12.1–12.4, 12.7–12.8]; [Ros 10.1–10.4]
14Tu Feb 20Graph connectivity, trees, and the tree theorem Slides, Notes
[LLM 12.11]; [Ros 10.4, 11.1, 11.4]
XW Feb 21 (Review session for Midterm 2)  
15Th Feb 22Digraphs, bipartite graphs, matchings, marriages Slides
[LLM 10.1–10.5, 12.5]; [Ros 10.2]
16Tu Feb 27Matchings: Hall's and König's theorems (last time's slides)
[LLM 12.5]; [Ros 10.2]
17Th Mar 1 Planarity and coloring, Euler's theorem Slides
[LLM 12.6, 13.1–13.4]; [Ros 10.7, 10.8]
18Tu Mar 6 The five-color theorem; Warp up Notes
[LLM 13.4–13.6]

The syllabus is divided into 18 units, roughly corresponding to the 18 regular classes above. Although not shown in the above plan, X-hours may be used (perhaps frequently) to catch up, as needed.

The Structure of a Class

Each class will have a three-part structure. The structure of class N is as follows:

  • (about 10 minutes) recap of material from unit N-1;
  • (about 40 minutes) class exercises for unit N-1;
  • (about an hour) lecture on unit N.

The most novel aspect of the course will be the class exercises. These will be homework-like problems, except that you have to present your solutions in class, to your Group Ninja (our term for an in-class TA). Students will be divided into groups of about 5 students each, and each group will have a Discrete Math Ninja. Each Ninja is a past student of CS 30 who knows all of the material in the class very well. Each Ninja will work with 2 groups. The class exercises should be approached as follows.

  • Each group will be seated at their own station, which will have a large table, enough chairs, a whiteboard, and a TV display that you can connect to your computer. You will present solutions either on the whiteboard or the TV display.
  • There will usually be three problems assigned as class exercises. Begin by discussing solution approaches with the other students in your group. Seek help from your Ninja if you don't fully understand the exercise problems, or if you are stuck.
  • About 20 minutes in, write out solution sketches and check with your Ninja that you are on the right track.
  • Make corrections/changes as needed, and finalize your solutions over the next 20 minutes.
  • Your Ninja will grade your work on each problem as follows. All students in a group will get the same grade.
    • (2 points) You got it right or mostly right.
    • (1 point) You made a good effort but did not get it right.
    • (0 points) You either didn't solve it or made a poor effort.
  • If you are absent for a class, you get 0 points for all class exercise problems for that day.

Exceptions: Class 1 will not have any graded class exercises, and Unit 18 will not be represented in any class exercises.

Soon after class N, a set of practice problems for unit N will be made available on Canvas. The class exercises for unit N (to be solved during class N+1) will either be drawn from this set of practice problems or will be slight variants of problems from this set. Therefore, if you wish, you can prepare for each class by working on the practice problems in advance, either on your own, or in collaboration with your fellow students.

There is homework associated with every class. The homework for class N will consist of (1) reviewing material by reading the slides or notes posted for class N, and (2) reading related sections from one or both of the textbooks. This homework is due before class N+1. There is nothing to submit and no grade for this homework, but I assume that you will nevertheless do the homework. Accordingly, my lectures will not repeat certain definitions or basics from the textbook. Be warned that not doing the homework will make it very hard to follow along during class N+1.

There is also weekly written homework to be submitted every Wednesday night, for which each student will receive their own grades. For more on this, go to the Homework tab.