**CS70: Discrete Mathematics and Probability Theory, Summer 2011**

### Announcements

- (June 16) - All students should now have access to the CS70 Summer 2011 Piazza forum as well as the cs70su11 Google Groups announcement list. If you have not received an email notification for either of them, please let us know as soon as possible. You may also join the Google Group yourself from here.
- (June 15) - The course notes are now available from the Copy Central located on Hearst near Euclid.

### Assignments

Please check this section regularly for new homework assignments, discussion section notes, and programming assignments. Note the due dates for homework and programming assignments. Section notes are optional and should not be turned in.- Section 1, June 20
- Homework 1,
*due*June 22 - Programming Assignment 1,
*due*July 1 - Section 2, June 22
- Section 3, June 27
- Homework 2,
*due*June 28 - Section 4, June 29
- Homework 3,
*due*July 5 - Section 6, July 6
- Section 7, July 11
- Homework 4,
*due*July 11 - Section 8, July 13
- Section 9, July 18
- Programming Assignment 2,
*due*July 18 - Homework 5,
*due*July 19 - Section 10, July 20
- Section 11, July 25
- Homework 6,
*due*July 26 - Section 12, July 27
- Section 13, August 1
- Homework 7,
*due*August 1 - Section 14, August 3
- Programming Assignment 3,
*due*August 4 - Section 15, August 8
- Review Problems, August 9
- Section 16, August 10
- Homework 8,
*due*August 10

### Readings

Lecture notes will be posted here shortly before or after each lecture. We will also post reading assignments from the course notes for each lecture.- Lecture 1, Logic, June 20 (also read Note 1)
- Lecture 2, Proofs, June 21 (read Note 2)
- Lecture 3, Proofs and Induction, June 22 (start reading Note 3)
- Lecture 4, Induction, June 23 (finish reading Note 3)
- Lecture 5, Stable Marriage, June 27 (read Note 4)
- Lecture 6, Modular Arithmetic, June 28 (read Note 5)
- Lecture 7, Modular Arithmetic and RSA, June 29 (read Note 6)
- Lecture 8, Polynomials and Secret Sharing, June 30 (read Note 7)
- No lecture, July 4
- Lecture 10, ECC and Counting, July 5 (read Note 8)
- Lecture 11, Counting, July 6 (read Note 9)
- Lecture 12, Counting and Introduction to Probability, July 7 (start reading Note 10)
- Lecture 13, Introduction to Probability, July 11 (finish reading Note 10)
- Midterm 1 5-7pm in 10 Evans, July 12
- Lecture 15, Conditional Probability, July 13 (start reading Note 11)
- Lecture 16, Conditional Probability, July 14 (finish reading Note 11)
- Lecture 17, Conditional Probability and Hashing, July 18 (read Note 12)
- Lecture 18, Random Variables, July 19 (start reading Note 13)
- Lecture 19, Random Variables and Expectation, July 20 (finish reading Note 13)
- Lecture 20, Expectation and Important Distributions, July 21 (start reading Note 14)
- Lecture 21, Important Distributions, July 25 (finish reading Note 14)
- Lecture 22, Important Distributions and Variance, July 26 (read Note 15)
- Lecture 23, Variance and Polling, July 27 (read Note 16)
- Lecture 24, Multiple Random Variables, July 28 (start reading Note 17)
- Lecture 25, Inference, August 1 (finish reading Note 17)
- Midterm 2 5-7pm in 10 Evans, August 2
- Lecture 27, Introduction to Continuous Probability, August 3 (start reading Note 18)
- Lecture 28, Continuous Probability and Distributions, August 4 (continue reading Note 18)
- Lecture 29, Normal Distribution and the Central Limit Theorem, August 8 (finish reading Note 18)
- Lecture 30, Countability and Diagonalization (read Note 19)
- Lecture 31, Computability, August 10 (read Note 20)
- Final Exam 5-8pm in 10 Evans, August 11

### Personnel

__Instructor__

Amir Kamil (kamil *at* eecs, 517 Soda)

Office Hours: TuTh 12-1 in 751 Soda

__Lectures__

Mon, Tue, Wed, Thu 5:00-6:30 PM in 306 Soda

__Teaching Assistants__

Stewart Liu (stewart_liu *at* berkeley)

Office Hours: M 6:30-7:30 in 320 Soda, W 4-5 in 751 Soda

Victor Huang (cs70-tb *at* inst *dot* eecs)

Office Hours: MW 3-4 in 751 Soda

__Readers__

Cheng-yu Hong

Seunghoon Lee

Elaine Lung

__Lab Assistants__

He Ma

Office Hours: M 6:30-7:30 in 320 Soda, Tu 12-1 in 751 Soda

__Discussion Sections:__

*Note: Sections begin on Monday 6/20.
*

101 Mon, Wed 1-2 320 Soda Victor

102 Mon, Wed 2-3 320 Soda Stewart

### Course Overview

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

__Logic and Proofs__

The following topics will be covered in this unit:

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

__Modular Arithmetic__

The following topics will be covered in this unit:

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

__Counting and Discrete Probability__

The following topics will be covered in this unit:

- 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__

The following topics will be covered in this unit:

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

__Diagonalization and Self-Reference__

The following topics will be covered in this unit:

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

### Assessment

__Homeworks (20%)__

There will be seven or eight homework assignments over the course of the summer, generally one a week. These assignments will consist of practice problems designed to give you experience in the concepts introduced in class. Unless otherwise indicated, homeworks will be due **by 4:59pm on Tuesdays**. Turn in your homework in the boxes labeled "CS70" in 283 Soda Hall. **Please begin your answer to each problem on a new sheet of paper, and make sure that each sheet is labeled with your name, class account, student ID, section number, the assignment number, the problem number, and "CS70--Summer 2011."** You should turn in each problem separately in the appropriate box (e.g. problem 1 in box 1, etc.). Reason: Different problems may be graded in parallel by different readers. *Warning: You risk receiving no credit, or losing points, for any homework that does not conform to the above regulations!* Please take the time to write clear and concise solutions; we will not grade messy or unreadable submissions. **No late homeworks will be accepted.** We will drop the lowest homework score.

__Programming Assignments (10%)__

There will also be three short programming assignments during the summer. These assignments will demonstrate a mathematical concept, a computer science application of a mathematical concept covered in class, or a connection between a programming concept and a mathematical concept. Programming assignments should be turned in electronically, and further details will be provided when they are assigned. **You have a total of three slip days for the summer.** This means that you can turn in one programming assignment three days late and the rest on time, or three assignments a day late each, or one assignment two days late and another one day late, and so on. **The number of days an assignment is late will be rounded up**, so if you turn in an assignment an hour late, it will count as a whole day late.

__Exams (70%)__

There will be two midterms and a final. Each exam is cumulative, meaning that we reserve the right to ask questions on any material previously covered in class or in the assignments. However, the second midterm will have a significant emphasis on topics not covered on the previous midterm. The exam dates are as follows:

- First Midterm (17.5%):
**Tuesday July 12, 5-7pm, in 10 Evans** - Second Midterm (17.5%):
**Tuesday August 2, 5-7pm, in 10 Evans** - Final Exam (35%):
**Thursday August 11, 5-8pm, in 10 Evans**

**must contact the instructor as soon as possible**. If you miss an exam without prior permission from the instructor, you will receive a score of 0 on the exam unless you miss it because of an unexpected circumstance beyond your control, documented by a physician or equivalent authority. Students in the DSP program should also contact the instructor as soon as possible to make any necessary arrangements.

__Participation (0+ε%)__

Class participation will be taken into account for students on a grade borderline at the discretion of the instructor.

__Final Grades__

Assignment of final grades will be based on departmental guidelines. However, we will not artificially lower grades if students perform exceptionally well in the class. In other words, if everyone does well in the class, we will be happy to assign higher grades than called for in the guidelines.

### Course Policies

__Contact Information__

The instructors and TA will post announcements, clarifications, hints, etc. on Piazza. Hence you **must** check the CS70 Piazza page frequently throughout the summer. (You should already have access to the CS70 Summer 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 send email to cs70 at inst.eecs. Email to this address is forwarded to the instructors and all TAs. We prefer that you use this address, rather than directly emailing the instructors and/or your TA, as it will usually get a faster response and also helps to ensure consistency in our treatment of students. 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.

__Prerequisites__

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, you will be expected to do small programming assignments as well.

__Readings__

**The course notes, Discrete Mathematics and Probability Theory, are now available at Copy Central on Hearst Ave near Euclid.** Please purchase a copy as soon as possible. We will cover most all of these notes in the order given. For additional background and examples, students may optionally consult the books

*Discrete Mathematics and its Applications*, by Kenneth Rosen (6th ed., McGraw-Hill, New York, 2007) and

*Introduction to Probability*, by Bertsekas and Tsitsiklis (2nd ed., Athena Scientific, Massachusetts, 2002).

__Discussion Sections__

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.

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

__Homeworks__

Your homework solutions must be written legibly and contain your name, your discussion section time, and the homework number. *You might receive no credit for assignments that are turned in without this information.* We do not attempt to grade messy and unreadable solutions. *Homework problems will be graded on both correctness and format*, so make sure you define all your variables, conform to the structure of an inductive proof, and so on. *Unless stated otherwise, show all your work.* If a problem can be interpreted in more than one way, clearly state the assumptions under which you solve the problem. In writing up your homework you are allowed to consult any book, paper, or published material. If you do so, you are required to cite your source(s). Model solutions will be made available after the due date. Graded problem sets will be returned in discussion section.

__Late Homework Policy__

We will give no credit for homeworks turned in after the deadline. No exceptions. Please don't ask for extensions. We don't mean to be harsh, but we prefer to make model solutions available shortly after the due date, which makes it impossible to accept late homeworks. The lowest grade will be dropped.

__Grading Policies__

On homeworks and exams, we insist that you provide a clear explanation of your proof. The readers are going to grade both the correctness of your answer AND the style of your proof and your mathematical reasoning. Answers that are not rigorous enough, or do not convey the basic ideas may not get full credit; however unnecessarily long answers are bound to get penalized as well. In general, the amount of details you should give to get full credit, should be enough to convince yourself, fellow students, the reader and the instructors (in increasing order of difficulty) that your understand the basic ideas behind what you are trying to prove and that you use the correct tools and arguments in your reasoning.

__Regrading Policies__

Regrading of homeworks or exams will only be undertaken in cases where you believe there has been a genuine error or misunderstanding. If you believe that your homework or exam answer was correct and you should have received full points, prepare a written note explaining which question you believe was misgraded and justifying your opinion, staple this to the cover of your homework, and return it to your TA. Some important points:

**We will not accept**verbal regrade requests or regrade requests without a cover sheet stapled on.**We will not regrade**your assignment on the spot; we will regrade it in batch mode.- We will only accept regrade requests for
**up to one week**after your graded solution was made available for return. - For homework grading appeals, we will only accept homework regrade requests if you believe that your answer on that problem is 100% correct and you should have received
**full**credit;**we will not regrade homeworks**in cases where you believe that you should have received**more partial credit**. - We reserve the right to
**regrade the entire assignment**, so be sure to check the solutions to confirm that your overall score will go up after regrading.

__Don't Be Afraid to Ask for Help__

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!

### Advice

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!** My best advice 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.

**Make use of office hours!** The instructor and TA 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 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!)

**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. I strongly advise 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. I've seen a few groups that 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.

### Computing Resources

The following documents may help you in taking advantage of the computing resources available to you.