CS 70, Spring 2006
Discrete Mathematics for Computer Science



Instructor:
  Umesh Vazirani (vazirani AT cs, Tu 1:30-2:30, 671 Soda Hall, 642-0572)

TAs:
  Gatis Midrijanis (gatis AT cs, M10-11, F10-11, 511 Soda Hall)
  Chris Crutchfield (cyc AT eecs, Tu5-6, 551 Soda Hall)

Lectures Tue and Thu, 11:00-12:30, 141 McCone
Check the newsgroup ucb.class.cs70 regularly! If you have never accessed UCB newsgroups before, there is online information about how to do it.


Announcements
Course Overview
Tentative list of topics
Syllabus
Texts
Prerequisites
Assessment
Lecture notes
Assignments

Announcements

Final exam
solutions are now available!
Final exams have been graded, so without further ado: FINAL EXAM GRADES. Grades are indexed by student ID modulo 9001 (a prime, just for fun).
Selected solutions from the study guide have been posted. Good luck on the midterm!
A study guide and sample questions for midterm 2 have been posted in the April 4 lecture notes. Also new notes for lecture 17, "basics of counting" have been posted.
Questions 5 and 6 on homework 8 have been deferred to the next homework and will be due on Tuesday, April 4.
Midterm 1 is scheduled on March 2, and Midterm 2 on April 6.
A new section has been scheduled W4-5 in 320 Soda Hall.
It was announced in class 2/2 that assignments will be due Fridays at 4 pm.

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

Unfortunately, there is no book that adequately covers all the material in this course at the right level. We will post lecture notes on this website. The following textbook is recommended but not required: 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 30% on the homeworks, 15% on each of the midterms, and 40% 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 Jan 17 Propositional logic and quantifiers Notes [ps] [pdf].
2 Jan 19 Proof techniques Notes [ps] [pdf].
3 Jan 24 Induction Notes [ps] [pdf].
[Rosen 3.3]
4 Jan 26 Strong induction and well-ordering principle Notes [ps] [pdf].
[Rosen 3.3]
5&6 Jan 31 & Feb 2 Stable marriages External notes
7&8&9 Feb 7 & Feb 9 and Feb 14 Modular Arithmetic and Euclid's Algorithm Notes [ps] [pdf].
[Rosen 2.4 background on division; Rosen pp. 161-165, 177-179]
10 Feb 16 Chinese Remainder Theorem & Fingerprinting Notes [ps] [pdf].
[Rosen pp. 185-187]
11 Feb 21 Polynomials, finite fields and Secret Sharing Notes [ps] [pdf].
12 Feb 23 Secret sharing contd. (continuing from same notes as last time).
13 Feb 28 Error correcting codes, Berlekamp-Welsh decoder Notes [ps] [pdf].
Scribe Lecture notes [ps] [pdf].
14 Mar 2 Midterm 1  
15&16 Mar 7&9 Eulerian Graphs Notes [ps] [pdf]. [Rosen 2.6]
Optional reading on Hypercubes [ps] [pdf].
17 Mar 14 Basics of counting Notes [ps] [pdf].
[Rosen 4.1-4.4]
18 Mar 16 Basic probability Notes [ps] [pdf].
[Rosen 5.1, 5.2]
19 & 20 Mar 21 & 23 Conditional probability Notes [ps] [pdf].
[Rosen 5.1, 5.2]
Mar 28 No class! Enjoy Spring break.  
Mar 30 No class! Enjoy Spring break.  
21 Apr 4 Midterm Review Study Guide and Practice Problems [ps] [pdf].
Selected Solutions [ps] [pdf].
Apr 6 Midterm 2  
22 Apr 11 Random variables, expected values Notes [ps] [pdf].
[Rosen 5.3]
23 Apr 13 Linearity of expectation, variance Notes [ps] [pdf].
[Rosen 5.3]
24 Apr 18 Variance, tail bounds (Continuing from same notes as last time)
25 Apr 20 Some Important Distributions Notes [ps] [pdf].
26 & 27 Apr 25 & 27 Estimation, Statistics and Normal Distribution Notes [ps] [pdf].
28 May 2 How to Lie with Statistics Notes [ps] [pdf].
29 May 4 Countability, diagonalization, computability Notes [txt].
30 May 9 Halting problem Optional: A relevant essay [ps] [pdf]
Lecture notes may be corrected and updated from time to time.

Assignments

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