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.

Math55 and CS70 cover similar material; Math55, however, typically covers
a wider range of topics in less depth and with fewer applications, and
is less closely tailored to Computer Science. L&S Computer Science
majors must take CS70; EECS students are strongly encouraged to take
CS70 rather than Math55, especially if they are intending to major
in Computer Science and/or if they found the more conceptual parts of CS61A
enjoyable and relatively straightforward.

**Instructor:**

David Wagner
(daw@cs, 629 Soda Hall,
642-2758)

**TAs:**

Luqman Hodgkinson
(luqman@cs)

Aaron Kleinman
(kleinman@math)

Min Xu
(mxu87 (at) berkeley (dot) edu)

**Addresses:**

Contact address:
cs70@imail.eecs

Web page:
http://www-inst.eecs.berkeley.edu/~cs70/

**Lectures:**

MWF, 11:00-12:00, 390 HMMB

**Sections:**

*101.* Tu 1:00-2:00, 7 Evans; Kleinman

*102.* Tu 2:00-3:00, 7 Evans; Hodgkinson

*103.* Tu 4:00-5:00, 246 Dwinelle; Hodgkinson

*104.* Tu 5:00-6:00, 246 Dwinelle; Xu
(section notes)

*105.* W 9:00-10:00, 3102 Etcheverry; Kleinman

**Office Hours:**

Kleinman: Tu 2:00-3:00, W 10:00-11:00, 852 Evans

Hodgkinson: Th 1:00-3:00, 711 Soda (*revised 4/22*)

Xu: Th 10:00-11:00, 711 Soda

Wagner: Mon 1-2:30pm, 629 Soda

- Please check the course newsgroup, ucb.class.cs70, for announcements.

The following schedule is tentative and subject to change. The Rosen readings are optional, but may be useful in providing you with extra information and/or a treatment of a topic from a different perspective.

Topic
| Readings
| |

1/23 | Overview | Notes. |

1/25 | Propositional logic |
Notes. [Rosen 1.1-1.4] |

1/28 | Proofs |
Notes. [Rosen 1.5-1.7] |

1/30 | More proofs | (cont. from above) |

2/1 | Induction |
Notes. [Rosen 4.1] |

2/4 | Induction, cont. | (cont. from above) |

2/6 | Strong induction |
Notes. [Rosen 4.2] |

2/6 | Well-ordering, recursive algorithms |
Notes. [Rosen 4.2, 4.3] |

2/11 | Stable marriage | Notes (revised 2/12). |

2/13 | Cake cutting | Notes. |

2/15 | Modular arithmetic |
Notes. [Rosen 3.4] |

2/18 | No class! | |

2/20 | gcd, algorithmic complexity | (cont. from above) [Rosen 3.6] |

2/22 | Euclid's algorithm | (cont. from above) |

2/25 | Modular inverses, extended Euclidean algorithm | (cont. from above) |

2/27 | Review | |

2/29 | Midterm 1 | |

3/3 | Polynomials, Secret sharing | Notes. |

3/5 | Error-correcting codes | Notes. |

3/7 | Fingerprints | Notes. |

3/10 | Graphs | Notes. [Rosen 9.1, 9.2, 9.5] |

3/12 | Intro to counting | Notes. [Rosen 5.1, 5.2, 5.3] |

3/14 | Advanced counting | (cont. from above) [Rosen 5.4, 5.5] |

3/17 | Guest lecture: Combinatorial hashing | Slides: pdf, pdf (6-up), powerpoint; rearranger.scm, rearranger example. |

3/19 | Intro to probability | Notes. [Rosen 6.1] |

3/21 | Conditional probability | Notes. [Rosen 6.2] |

3/24-28 | No class! Enjoy Spring break. | |

3/31 | Conditional probability, cont. | (cont. from above) [Rosen 6.3] |

4/2 | Hashing | Notes. |

4/4 | Load balancing | (cont. from above) |

4/7 | Review | |

4/9 | Midterm 2 | |

4/11 | Random variables | Notes. [Rosen 6.4] |

4/14 | Expected values | (cont. from above) [Rosen 6.4] |

4/16 | Linearity of expectation | (cont. from above) [Rosen 6.4] |

4/18 | Variance | Notes. |

4/21 | Variance | (cont. from above) |

4/23 | Important distributions | Notes. |

4/25 | How to lie with statistics | Notes. |

4/28 | Tail bounds, Chebyshev's inequality | (see Notes from 4/18) |

4/30 | Polling | Notes. |

5/2 | I.i.d. random variables, Central limit theorem | (cont. from above) |

5/5 | Infinity, countability | Notes. |

5/7 | Diagonalization | (cont. from above) |

5/9 | Computability, Halting problem, Godel's theorem | Notes. |

5/12 | TBD |

- 1/29: handout 1, solutions
- 2/5: handout 2, solutions
- 2/12: handout 3, solutions
- 2/19: handout 4, solutions
- 2/26: handout 5, solutions
- 3/4: handout 6, solutions
- 3/11: handout 7 (on the moon), handout 7 (on earth), solutions
- 3/18: handout 8, solutions
- 4/1: handout 9, solutions
- 4/8: handout 10, solutions
- 4/15: handout 11, solutions
- 4/22: handout 12, solutions
- 4/29: handout 13, solutions
- 5/6: handout 14, solutions

Homeworks will be submitted online. Paper submissions will not be accepted. Submit the Latex source and the resulting PDF; information on using Latex is available.

- Homework 1 (due 1/31); latex template; solutions.
- Homework 2 (due 2/7) (Q6.4 revised 2/4); latex template; solutions.
- Homework 3 (due 2/14); latex template; solutions.
- Homework 4 (due 2/21); latex template; solutions.
- Homework 5 (due 2/28); latex template; solutions.
- Homework 6 (due 3/6) (Q3 revised 3/2); latex template; solutions.
- Homework 7 (due 3/13); latex template; solutions.
- Homework 8 (due 3/20); latex template; solutions.
- Homework 9 (due 4/3); latex template; solutions.
- Homework 10 (due 4/17) (Q4 slightly revised 4/11); latex template; solutions (Q3(e) revised 4/19).
- Homework 11 (due 4/24) (Q5 slightly revised 4/19); latex template; solutions.
- Homework 12 (due 5/1) (Q3 hint added 4/25, Q5(f) deleted 4/30); latex template; solutions.
- Homework 13 (due 5/8) (Q4 background revised slightly 5/6); latex template; solutions.

Quizzes must be completed online once a week, before midnight on each Sunday. The quizzes will check your progress so far, so you should be doing the reading for the prior week before taking the quiz. Quizzes must be done on your own (no collaboration, and no discussion of the questions or your answers with others).

- Quiz #1 (due Sun 1/27 11:59pm), solution.
- Quiz #2 (due Sun 2/3 11:59pm), solution.
- Quiz #3 (due Sun 2/10 11:59pm), solution.
- Quiz #4 (due Sun 2/17 11:59pm), solution.
- Quiz #5 (due Sun 2/24 11:59pm), solution.
- Week 6: no quiz.
- Quiz #7 (due Sun 3/9 11:59pm), solution.
- Quiz #8 (due Sun 3/16 11:59pm), solution.
- Quiz #10 (due Sun 3/30 11:59pm), solution.
- Quiz #12 (due Sun 4/13 11:59pm), solution.
- Quiz #13 (due Sun 4/20 11:59pm), solution.
- Quiz #14 (due Sun 4/27 11:59pm), solution.
- Quiz #15 (due Sun 5/4 11:59pm), solution.

- 50 points: Homeworks (average of all but your lowest hw score, with the average capped at 50 pts).
- 10 points: Quizzes (average of your quiz scores).
- 40 points: Midterm I (Feb 29, in class). (solutions)
- 40 points: Midterm II (Apr 9, in class). (solutions)
- 60 points: Final Exam (May 17, 12:30-3:30pm, in Bechtel Auditorium). (solutions)

The grading standard is available and has been fixed at the beginning of the course:

A+: [*] A: 160-200 A-: 150-159 B+: 140-149 B: 130-139 B-: 120-129 C+: 110-119 C: 100-109 C-: 90-99 D: 70-89 F: 0-69 [*] A+ awarded at instructors' discretionThe instructors reserve the right to add extra points to your grade at the end of the class (for instance, if the final exam was unexpectedly harder than intended).

If you have a question, your best option is to post a message to the newsgroup. The staff (instructor and TAs) will check the newsgroup regularly, and if you use the newsgroup, other students will be able to help you too. When using the newsgroup, please avoid off-topic discussions, and please do not post answers to homework questions before the homework is due.

If your question is personal or not of interest to other students, you may send email to cs70@imail.eecs. Email to this address is forwarded to the instructor and all TAs. We prefer that you use this address, rather than directly emailing the instructor and/or your TA. If you wish to talk with one of us individually, you are welcome to come to our office hours. If the office hours are not convenient, you may make an appointment with any of us by email. Please reserve email for the questions you can't get answered in office hours, in discussion sections, or through the newsgroup.

In a class this large, it can be challenging for the instructor to
gauge how smoothly the class is going. We always welcome any feedback
on what we could be doing better. If you would like to send anonymous
comments or criticisms, please feel free to use an anonymous remailer
like this
one to avoid revealing your identity.

**Computer accounts:**
We will use 'named' accounts this semester.
Further information is
here.
After you have obtained your account,
you will need to register with our grading software.
See these instructions.

**Collaboration:** You are encouraged to work on homework problems
in study groups of two to four people; however, you must **always**
write up the solutions on your own, and you must **never** read or copy
the solutions of other students. Similarly, you may use books or online
resources to help solve homework problems, but you must **always**
credit all such sources in your writeup and you must **never**
copy material verbatim.
**Warning:** Your attention is drawn to the Department's
Policy on Academic Dishonesty.
In particular, you should be aware that
copying solutions, in whole or in part, from other
students in the class *or any other source* without acknowledgment
constitutes cheating. Any student found to be cheating risks automatically
failing the class and being referred to the Office of Student Conduct.

**Regrading Policies:**
Regrading of homeworks or exams will only be undertaken in cases where
you believe there has been a genuine error or misunderstanding.
Bear in mind that our primary aim in grading is consistency, so that
all students are treated the same; for this reason, we will not adjust
the score of one student on an issue of partial credit unless the score
allocated clearly deviates from the grading policy we adopted for that
problem. If you wish to request a regrading of a homework or exam, you
must return it to your section TA with a written note on a separate piece
of paper explaining the problem. The entire assignment may be regraded,
so be sure to check the solutions to confirm that your overall score will
go up after regrading. All such requests must be received within one
week from the date on which the homework or exam was made available for
return.

**1. Don't fall behind!** In a conceptual class such as this, it is
particularly important to maintain a steady effort throughout the semester,
rather than hope to cram just before homework deadlines or exams.
This is because it takes time and practice for the ideas to sink in.
Make sure you allocate a sufficient number of hours every week to the
class, including enough time for reading and understanding the material
as well as for doing assignments. (As a rough guide, you should expect to
do at least one hour of reading and two hours of problem solving for each
hour of lecture.) *Even though this class does not have
any major projects, you should plan to spend as much time on it as on
any of your other technical classes.*

**2. Take the homeworks seriously!** The homeworks are explicitly
designed to help you to learn the material as you go along. Although
the numerical weight of the homeworks is not huge, there is usually a
strong correlation between homework scores and final grades in the class.
Also, regardless of how well you did on the homework, *read the sample
solutions*, even for the problems you got right. You may well learn
a different way of looking at the problem, and you may also benefit from
emulating the style of the solutions. (In science people learn a lot
from emulating the approach of more experienced scientists.)

**3. Make use of office hours!** The instructor and TAs hold
office hours expressly to help you. It is often surprising how many
students do not take advantage of this service. You are free to
attend as many office hours as you wish (you are not constrained just
to use the office hours of your section TA). You will also likely get
more out of an office hour if you have spent a little time in advance
thinking about the questions you have, and formulating them precisely.
(In fact, this process can often lead you to a solution yourself!)

**4. Take part in discussion sections!** Discussion sections are
**not** auxiliary lectures. They are an opportunity for interactive
learning. The success of a discussion section depends largely on the
willingness of students to participate actively in it. As with office
hours, the better prepared you are for the discussion, the more you are
likely to get out of it.

**5. Form study groups!** As stated above, you are encouraged to
form small groups (two to four people) to work together on homeworks and
on understanding the class material on a regular basis. In addition to
being fun, this can save you a lot of time by generating ideas quickly and
preventing you from getting hung up on some point or other. Of course,
it is your responsibility to ensure that you contribute actively to the
group; passive listening will likely not help you much. And recall the
caveat above that you **must** write up your solutions on your own.

*Mail inquiries to* `cs70@imail.eecs`.