CS 70, Fall 2006
Discrete Mathematics for Computer Science

Instructors:
Christos Papadimitriou (christos AT cs, M, Th 5-6 pm, 689 Soda Hall)
Umesh Vazirani (vazirani AT cs, M, Th 1:00-2:00, 671 Soda Hall)

TAs:
David G Garmire (strive AT cs, 515 Soda Hall)
Lorenzo Orecchia (orecchia AT cs, 595 Soda Hall)
Benjamin Rubinstein (benr AT eecs DOT berkeley DOT edu, 523 Soda Hall)

Announcements
Course Overview
Tentative list of topics
Texts
Prerequisites
Assessment
Lecture notes
Sections
Exam Material
Assignments

Announcements

Here is a list with all your homeowrk grades, indexed by your sid mod 164617. Let Lorenzo know if any discrepancies arise by Tuesday morning.

Final Exam Material:

Final from spring 2006: ps, pdf. And solutions: ps, pdf.
A few practice problems. More are coming: ps , pdf . Solutions: ps , pdf

NOTE: On Friday there will be no lecture. TAs will run a review session on Sunday 5.30-7pm, 310 Soda.
The final exam is going to be held on Tuesday, December 12, 12.30 - 3.30 pm, in 10 Evans. See you there.
Notes on diagonalization and countability have been posted.
Homework 12 announcement The due date for homework 12 has been postponed to Wednesday 29, 5pm. Problem 4 has been modified and a new version is now available.
Homework 11 announcement

balls.scm and BallsBins.java (precompiled BallsBins.class ) are provided for your convenience for Problem Set 11. For Scheme, please use the instructional CD and download STk for your system. Both codes provide the function "bb #n" as described in the assignment. NOTE: You may use 10^5 balls instead of 10^6 balls. (The Scheme code may take a little while, please be patient.)

Midterm announcements

The second Midterm is in class on Friday. It covers all material from Berlekamp-Welsh codes up to Variance.
A review session will be held Wednesday 6-7.30 pm in 306 Soda.
We will go through the following sample midterms:
Sample 1 pdf , ps ; Solution: pdf; ps
Sample 2 pdf , ps ;
Notice that these samples are probably slightly longer than the real midterm.
The GSIs are going to have extra office hours on Thursday: Ben(1-2:30pm, 611 Soda), David(TBA), Lorenzo(11am-1pm, 511 Soda).

Course Overview

The goal of this course is to introduce students to ideas and techniques from discrete mathematics that are widely used in Computer Science. The course aims to present these ideas "in action"; each one will be geared towards a specific significant application. Thus, students will see the purpose of the techniques at the same time as learning about them.

cs70 is required for L&S CS majors; EECS majors have a choice of cs70 or Math55. Broadly speaking the two courses cover similar material; however, Math55 covers a wider range of topics in less depth and with fewer applications, and is less closely tailored to Computer Science. You should take this course as an alternative to Math55 if you are intending to major in Computer Science and if you found the more conceptual parts of CS61A enjoyable and relatively straightforward.

Tentative list of topics

Propositions and Proofs
Mathematical Induction: recursion, the stable marriage problem
Infinity and diagonalization
Arithmetic Algorithms: Modular Arithmetic and GCD.
Polynomials and their Applications: error-correcting codes, secret sharing
Graphs, Euler tours, hypercubes.
Discrete Probability: counting, sample spaces, expectation, variance, load balancing, hashing, conditional probability, Bayesian inference, law of large numbers, power laws.
Self-Reference and Uncomputability

Texts

There are detailed lecture notes for this course that will be posted on this website. No textbook is required. If you wish to purchase a textbook, we recommend the following:

Discrete Mathematics and its Applications, by Kenneth H. Rosen, McGraw-Hill, Inc., New York.

Note that you should not view the existence of these materials as a substitute for attending class: you are warned that our discussion in class may deviate somewhat from the written material, and you should take your own notes as well.

Prerequisites

You must have taken CS61A, Math1A and Math1B (or equivalents).

Assessment

There will be weekly homeworks (which may include a couple of small programming exercises), two in-class midterms and one final. The overall grade will be based approximately 25% on the homeworks, 20% on each of the midterms, 5% on class participation/quizzes and 35% on the final.

Homeworks will usually be posted on the website on Friday and will be due at 4 pm on the following Friday. Late homework will be accepted only in extraordinary circumstances, and may in any case be penalized. The lowest homework grade will be dropped. You are encouraged to work on homework problems in groups of at most four people; however, you must always write up the solutions on your own. Similarly, you may use references to help solve homework problems, but you must write up the solution on your own and cite your sources. Copying solutions or code, in whole or in part, from other students or any other source without acknowledgment constitutes cheating. Any student found to be cheating in this class will automatically receive an F grade and will also be referred to the Office of Student Conduct.

Lectures

The following schedule is tentative and subject to change. Readings in Rosen are optional, in case you want extra background on the subject or a different presentation from a second point of view.

		Topic	Readings
1&2	August 28 and 30	Propositional logic and quantifiers	Notes [ps] [pdf]. Background reading on sets [ps] [pdf].
3	September 1	Proof techniques	Notes [ps] [pdf].
4&5	September 6&8	Induction	Notes [ps] [pdf]. [Rosen 3.3]
6&7	September 11 & 13	Stable marriage	Notes [ps] [pdf].
8&9&10	September 15, 18 and 20	Modular Arithmetic and Euclid's Algorithm	Notes [ps] [pdf]. [Rosen 2.4 background on division; Rosen pp. 161-165, 177-179]
11 & 12	September 22 & 25	Polynomials, finite fields and Secret Sharing	Notes [ps] [pdf].
13 &14	September 29 & October 2	Error correcting codes, Berlekamp-Welsh decoder	Notes [ps] [pdf]. Scribe Lecture notes [ps] [pdf].
15	October 4	Midterm 1
16&17	October 6&9	Eulerian Graphs	Notes [ps] [pdf]. [Rosen 2.6]
18 & 19	October 11& 13	Hypercubes - expansion, gray codes	Notes [ps] [pdf].
20 & 21	October 16 & 18	Basics of counting	Notes [ps] [pdf]. [Rosen 4.1-4.4]
22	October 20	Basic probability	Notes [ps] [pdf]. [Rosen 5.1, 5.2]
23 & 24	October 23 & 25	Conditional probability	Notes [ps] [pdf]. [Rosen 5.1, 5.2]
25	October 27	Random variables, expected values	Notes [ps] [pdf]. [Rosen 5.3]
26 & 27	October 30 & November 1	Linearity of expectation, variance	Notes [ps] [pdf]. [Rosen 5.3]
28	November 3	Midterm 2
29 & 30	November 6 & 8	I.I.D. Random Variables	Notes [ps] [pdf].
31	November 13	Estimation, Statistics and Normal Distribution	Continuing with notes from last time.
32	November 15	Two Killer Applications	Notes [ps] [pdf].
33	November 17	Some Important Distributions	Notes [ps] [pdf].
34	November 20	Power Law Distributions	Lecture Notes [pg1.pdf] . [pg2.pdf] . [pg3.pdf] . [pg4.pdf] . More Notes Power Laws & Polya Urns. External link: Zipf, Power-laws, and Pareto - a ranking tutorial
35	November 27	How to Lie with Statistics	Notes [ps] [pdf].
36, 37, 38 & 39	November 29 & December 1, 4 & 6	Infinity and diagonalization	Notes [ps]. [pdf].
40	December 8	Halting problem	Notes [ps]. [pdf]. Notes on diagonalization in pdf. Optional: A relevant essay [ps] [pdf]

Lecture notes may be corrected and updated from time to time.

Discussion sections

These are the handouts distributed in sections. They contain reviews of the material covered in class and useful optional exercises for you to practice on.

Week 1 - Propositional Logic: Truth Tables and Quantifiers. ps, pdf

Week 2 - More Propositional Logic. Different Proof Methods. Proofs by Induction. ps, pdf

Week 3 - More Propositional Logic. Strong Induction and Stable Marriage. ps, pdf

Week 4 - Stable Marriage. Modular Arithmetic: Euclid's Algorithm, Extended Euclid and Multiplicative Inverses. ps, pdf

Week 5 - Polynomials on Fields, Polynomial Interpolation. Secret Sharing. ps, pdf

Week 6 - Error Correcting Codes. ps, pdf

Week 7 - Graph Theory: Eulerian Graphs, Hypercubes. Basic Counting. ps, pdf

Week 8 - Quiz. ps, pdf

Week 9 - Random Variables: Independence & Conditional Probability. Expectation: Linearity of Expectation. ps, pdf

Week 10 - Distribution, Expectation. Variance: Chebyshev's Inequality. ps, pdf

Week 11 - Variance of Sums, I.I.D. Random Variables, Midterm 2 Solutions. ps, pdf

Week 12 - Central Limit Theorem, Card Shuffling, Estimating the Factorial Function. ps, pdf

Week 13 - No sections, thanksgiving break.

Week 14 - Sums/Averages of Normals, Power Laws (Zipf's law and Pareto distributions), Simpson's Paradox. ps, pdf

Week 15 - Countable and Uncountable Sets. ps, pdf

Exam Materials

Midterm 2: midterm pdf , ps ; solutions pdf , ps ;
Sample 1 pdf , ps ; Solution: pdf; ps
Sample 2 pdf , ps ;

Midterm 1

Sample 1 ps. Solutions ps.
Sample 2 ps.

Assignments

Assignments are due at 4 pm in cs70 homework drop box in 283 Soda Hall.

Problem Set 1 ps , pdf , due 9/1. Solutions ps , pdf
Problem Set 2 ps , pdf , due 9/8. Solutions ps, pdf
Problem Set 3 ps , pdf , due 9/15. Solutions ps , pdf
Problem Set 4 ps , pdf , due 9/22. Solutions ps, pdf
Problem Set 5 ps , pdf , due 9/29. Solutions ps , pdf
Problem Set 6 ps , pdf , due 10/6. Solutions ps , pdf
Problem Set 7 ps , pdf , due 10/13. Solutions ps , pdf
Problem Set 8 ps , pdf , due 10/20. Solutions ps , pdf
Problem Set 9 ps , pdf , due 10/27. Solutions ps , pdf
Problem Set 10 ps , pdf , due 11/13. Solutions ps, pdf
Problem Set 11 ps , pdf , due 11/20. NOTE: you may use n=10^5 instead of n=10^6 for problem 6. Solutions ps, pdf
Problem Set 12 ps , pdf , due 11/29. Solutions ps, pdf
Problem Set 13 ps , pdf , due 12.6. Solutions ps, pdf