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:
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 Midterm announcements

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


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: 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.

Exam Materials

Midterm 2

Midterm 1

Assignments

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