Math 19/CS 19: Discrete Math for Computer Science

The day-by-day schedule will be determined as we go along, but here are the topics we'll cover.

• Logic and proof techniques (Rosen Chp. 1)
• Sets and relations (Rosen Chp. 2 and 8)
• Asymptotics (Rosen Chp. 3)
• Induction and recursion (Rosen Chp. 4)
• Counting techniques (Rosen Chp. 5 and 7)
• Discrete probability (Rosen Chp. 6 and 7; possibly some supplemental material)
• Graphs and trees (Rosen Chp. 9 and 10)

I teach Math 29 every other spring out of course notes I wrote (and continually rewrite), and there is a chapter of background that is mostly relevant to this class. It covers some of topics 1, 2, and 4 above. There will be some translation needed between it and our textbook, because the symbols used are not always the same. [updated Sep 16, 11am]

Material for First Midterm:

Logic, sections 1.1-1.4: Sept 22 and 24. Homework

Introduction to proofs, sections 1.6, 1.7: Sept 24 and 27. No assignment.

Sets, sections 2.1 and 2.2: Sept 27 and 29. Homework

Functions and relations, sections 2.3, 8.1, 8.5: Sept 29, Oct 1 and 4. Homework

Algorithm analysis (summation formulas and big-O notation), sections 2.4, 3.1-3: Oct 4, 6, 8.    pdf of graphs   Homework

Suggested material from the book's review to each chapter is available on the homework page.   relation overhead

Material for Second Midterm:

Induction and recursion, sections 4.1, 4.3: Oct 11, 13, 18, 20. Homework

Counting, sections 5.1-5.4, 7.5-7.6: Oct 18, 20, 22. Note: the primary sections here are 5.1 and 5.3. 5.2 is so you have some familiarity with the Pigeonhole Principle but we will not be particularly versatile in its application. 5.4 is primarily so you have a higher comfort level with combinations and factorial manipulation. 7.5 and 7.6 cover the generalized Inclusion-Exclusion Principle, for which I only need you to know the 2-set form found in 2.2 (p. 122). These priorities are reflected in the homework selection: Homework   pdf with some counting tips

Probability, Chapter 6: Oct. 22-Nov 1 (at least). You may ignore Monte Carlo algorithms and the probabilistic method in 6.2 and the geometric distribution in 6.4. Tree diagrams for probability are not required, but there may be problems given that are much easier using them. Here is a textbook section explaining them, and we will continue to use them in lecture.    pdf about variance and independence   Homework

Suggested material from the book's review to each chapter is available on the homework page.

Material for Final Exam:

All of the above, plus:

Introduction to graphs: 9.1, 9.2, adjacency matrices from 9.3, definitions of "path" and "connected" from 9.4. Homework

More on graphs and trees: special kinds of paths, weighted graphs, spanning trees. 9.6, 10.1, 10.4, 10.5. We will discuss some of 9.5 in class, as well as algorithms for finding minimal paths and (minimal) spanning trees, but you are not responsible for those on the final. Homework

Suggested material from the book for final exam review as well as a pdf of extra review problems and their answers are available on the homework page. Here is a pair of small, worked-out examples from counting and probability, including a scaled-down version of the "flush given ace" problem. Here is the review sheet for the final exam.

Back to the main 19 page.

Last modified December 3, 2010