- Instructor: Umesh Vazirani
- Lecture: TTh 3:30-5:00 PM, 155 Dwinelle
- Office: 671 Soda Hall
- Office hours TuTh 5-6 pm

- Rahul Basu
- Sections
- Section 111, Wednesday 12-1 PM, 209 Dwinelle

- Office hours
- Thursday 12:30-2:30 PM, 751 Soda

- Andrew B. Godbehere
- Sections
- Section 101, Wednesday 10-11 AM, 87 Evans
- Section 102, Wednesday 11-12 PM, 3102 Etcheverry

- Office hours
- Tuesday 2-3:30pm, Soda 751
- Friday 3-4:30pm, Soda 411

- Jiung Lee
- Sections
- Section 107, Wednesday 4-5 PM, Evans 87
- Section 108, Wednesday 5-6 PM, Evans 87

- Office hours
- Monday 2:30-3:30 PM, 283E Soda
- Friday 10:30-11:30 AM, 283E Soda

- Lisha Li
- Sections
- Section 110, Wednesday 10-11 AM, 136 Barrows

- Office hours
- Wednesday 11-12 AM, Evans 1062

- Shivaram Lingamneni
- Sections
- Section 105, Wednesday 2-3 PM, 87 Evans
- Section 112, Wednesday 6-7 PM, 320 Soda

- Office hours
- Wednesday 3-4 PM, Evans 710
- Thursday 6-7 PM, Evans 710

- Baruch Sterin
- Sections
- Section 109, Wednesday 1-2 PM, 320 Soda
- Section 106, Wednesday 3-4 PM, 87 Evans

- Office hours
- Wednesday 4:30-5:30 PM, 545F Cory
- Thursday 7-8 PM, 545F Cory

- Ian Vonseggern
- Sections
- Section 103, Wednesday 12-1 PM, Evans 87
- Section 104, Wednesday 1-2 PM, Evans 87

- Office hours
- Thursday 10:30-12:30 PM, 751 Soda

- Homework #13, updated (due November 30)
- Homework #12 (due November 16)
- Homework #11 (due November 9)
- Homework #9 (due October 26)
- Homework #8 (due October 19)
- Homework #7 -- updated again (due October 12)
- Homework #6 (due October 5) -- Second Update
- Homework #6 (due October 5) -- UPDATED!
- Homework #5 (due September 28)
- Homework #4 (due September 21)
- Homework #3 (due September 14)
- Homework #2 (due September 7)
- Homework #1 (due August 31)

- Lecture Notes #23: Intro to Sets
- Lecture Notes #22: Self-Reference and Computability
- Lecture Notes #21: Infinity and Countability
- Lecture Notes #20: Kalman Filter
- Lecture Notes #19: A Brief Into to Continuous Probability
- Lecture Notes #18: Inference
- Lecture Notes #17: I.I.D. Random Variables
- Lecture Notes #16: Variance
- Lecture Notes #15: Some Important Distributions
- Lecture Notes #14: Random Variables:Distribution and Expectation
- Lecture Notes #13: An Application: Hashing
- Lecture Notes #12: Conditional Probability
- Lecture notes #11: Intro to Discrete Probability
- Lecture notes #10: Counting
- Lecture notes #9: Graphs
- Lecture notes #8: Error Correcting Codes
- Lecture notes #7: Polynomials
- Lecture notes #6: Public Key Cryptography
- Lecture notes #5: Modular Arithmetic
- Lecture notes #4: Stable Marriage
- Lecture notes #3: Induction
- Lecture notes #2: Proofs
- Lecture notes #1: Course Outline and Propositions

- Section #14 solutions
- Section #14
- Section #13 solutions
- Section #13
- Section #12 solutions
- Section #12
- Section #11 solutions
- Section #11
- Section #10 solutions
- Section #9 solutions
- Section #8
- Section #8 solutions
- Section #7
- Section #7 solutions
- Section #6
- Section #5
- Section #5 solutions
- Section #4
- Section #4 solution sketch
- Section #3
- Section #2

Discrete mathematics and probability theory provide the foundation for many algorithms, concepts, and techniques in the field of Electrical Engineering and Computer Science. For example, computer hardware is based on Boolean logic. Induction is closely tied to recursion and is widely used, along with other proof techniques, in computer science theory. Modular arithmetic and probability theory are essential in many computer science applications including security and artificial intelligence. CS70 will introduce you to these and other mathematical concepts. By the end of the semester, you should have a firm grasp of the theoretical basis of these concepts and their applications to general mathematical problems. In addition, you will learn how they apply to specific, important problems in the field of EECS.

This course is divided into five main units, each of which will introduce you to a particular mathematical concept as well as its applications. The units are as follows:

- Logic and Proofs
- Modular Arithmetic
- Counting and Discrete Probability
- Continuous Probability
- Diagonalization and Self-Reference

These units will now be described in more detail.

**Logic and Proofs**

- Propositions and quantifiers
- Direct proofs
- Proofs by contradiction and contraposition
- Simple induction
- Strong induction
- The stable marriage problem

**Modular Arithmetic**

- Congruence relations
- Euclid's GCD algorithm and multiplicative inverses
- The RSA cryptosystem
- Polynomials over finite fields
- Error correcting codes

**Counting and Discrete Probability**

- Combinatorics and combinatorial proofs
- Probability spaces and events
- Conditional probability and Bayes' rule
- Hashing
- Random variables and distributions
- Expectation, variance, and Chebyshev bounds
- Polling and the law of large numbers
- Joint distributions and Bayesian inference

**Continuous Probability**

- Continuous probability spaces and random variables
- Uniform and exponential distributions
- Normal distributions and the Central Limit Theorem

**Diagonalization and Self-Reference**

- Cardinality of infinite sets
- Cantor's diagonalization proof
- Uncomputability and the halting problem

Homeworks will be assigned each Friday and will be due the following **Friday at 5pm**. NO late homeworks will be accepted.

For the first few (3 or 4, precise number TBD) homeworks, you will be allowed to resubmit your homework to make up 50% of the points you missed. We hope you will use this to practice and learn, as the skills of thinking and writing in a formal mathematical domain require practice. The deadline for resubmission is always 11:59 PM on the Wednesday after the original due date.

Your lowest homework score of the semester will be dropped.

Homeworks will be submitted electronically, as a pdf. Details of the online submission system are forthcoming. Homeworks may be prepared in LaTeX, Microsoft Word (with equation editor), or by hand. If the latter, you will need to scan your work. Please see scanning instructions to scan to pdf.

Please note that each problem is graded separately. For proper grading, no two problems can share the same page!

There will be two midterms and one final exam.

- Midterm 1: September 27, IN CLASS
- Midterm 2: October 30, IN CLASS

There will be extra review sessions for the midterms, details on Piazza.

- Homework: 30%
- Midterms: 20% each (there are 2)
- Final: 30%

The instructors and TA will post announcements, clarifications, hints, etc. on Piazza. Hence you must check the CS70 Piazza page frequently throughout the fall. (You should already have access to the CS70 Fall 2011 forum. If you do not, please let us know so that we can add you.) If you have a question, your best option is to post a message there. The staff (instructors and TAs) will check the forum regularly, and if you use the forum, other students will be able to help you too. When using the forum, 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 mark your question as private on Piazza, so only the instructors will see it. If you wish to talk with one of us individually, you are welcome to come to our office hours. Please reserve email for the questions you can't get answered in office hours, in discussion sections, or through the forum.

In a class this large, it can be challenging for the instructors 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.

Sophomore mathematical maturity, and programming experience equivalent to that gained in CS3 or the Advanced Placement Computer Science A course (e.g., CS 3, E 7, CS 61A). If you lack any of these prerequisites, you may only take the class with special permission from the instructor. Although most of the work in the class will be pencil-and-paper exercises, we expect the students to be familiar with reading and designing programs.

Please enroll in a discussion section via Telebears, if you have not already. You may only enroll in a discussion section that has space available: see the online schedule. You may switch discussion sections only with the approval of the TA, and only if that section is not full. Outside of your discussion section, you should feel free to attend any of the staff office hours and ask any of us for help.

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. You must never read or copy the solutions of other students, and you must not share your own solutions with 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. We believe that most students can distinguish between helping other students and cheating. Explaining the meaning of a question, discussing a way of approaching a solution, or collaboratively exploring how to solve a problem within your group is an interaction that we encourage. On the other hand, you should never read another student's solution or partial solution, nor have it in your possession, either electronically or on paper. You must never share your written solutions, or a partial solution, with another student, even with the explicit understanding that it will not be copied. You should write your homework solution strictly by yourself. **You must explicitly acknowledge everyone whom you have worked with or who has given you any significant ideas about the homework.** Not only is this good scholarly conduct, it also protects you from accusations of theft of your colleagues' ideas.

**Warning**: Your attention is drawn to the Department's Policy on Academic Dishonesty. In particular, you should be aware that copying or sharing 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.

Are you struggling? We'd rather you approached us for help, rather than falling behind gradually over the semester until things become untenable. Sometimes this happens when students are afraid of an unpleasant conversation with a professor if they admit to not understanding something. We would much rather deal with your misunderstanding early than deal with its consequences later. Even if you are convinced that you are the only person in the class that doesn't understand the material, and that it is entirely your fault for having fallen behind, please overcome your feeling of guilt and ask for help as soon as you need it. Remember that the other students in the class are working under similar constraints--they are taking multiple classes and are often holding down outside employment. Don't hesitate to ask us for help--helping you learn the material is our job, after all!

If you have been issued a letter of accommodation from the Disabled Students Program (DSP), please contact Professor Vazirani as soon as possible to work out the necessary arrangements. If you need an accommodation and have not yet seen a Disability Specialist at the DSP, please do so as soon as possible.

If you would need any assistance in the event of an emergency evacuation of the building, the DSP recommends that you make a plan for this in advance. (Contact the DSP accest specialist at 643-6456.)

The following tips are offered based on our experience with CS 70.

**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 your other technical classes.

**Do the homeworks!** 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. (The most common denominator among people who do poorly in the class is that they skipped several homework assignments or multiple homework problems.)

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

**Don't wait until the last minute to start homeworks!** A good practice is to read through the homework problems as soon as they are available, and let them percolate in your brain. Think through possible approaches while you are waiting in line, or stuck in an elevator, or whatever. Sleeping on a problem has often helped people to come up with a creative approach to it. Definitely do not wait until the night before it is due to start working on the homework.

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

**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. You are strongly advised you to spend some time on your own thinking about each problem before you meet with your study partners; this way, you will be in a position to compare ideas with your partners, and it will get you in practice for the exams. Make sure you work through all problems yourself. Some groups try to split up the problems ("you do Problem 1, I'll do Problem 2, then we'll swap notes"); not only is this a punishable violation of our collaboration policies, it also ensures you will learn a lot less from this course.