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

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.

#DateTopicsReferences
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.