Discrete Mathematics and Probability Theory

Fall 2013

Previous sites: http://inst.eecs.berkeley.edu/~cs70/archives.html

- Instructor: Umesh Vazirani
- Lecture: TuTh 11:00 AM-12:30 PM, Wheeler Auditorium
- Office: 671 Soda Hall
- Office hours: Tu 1:30 PM-2:30 PM

- Written homeworks are posted Mondays and are due the following Monday at 5pm.
- Online homeworks are post Sundays and are due the following Friday at 1pm.
- Midterm 1 review session: Friday Sept 27th 5-7pm in 2050 VLSB.
- Midterm 1: Oct 1st (in class)
- Midterm 2: Nov 5th (in class)
- Final Review Session: Thursday (Dec 12th) 11am-2pm in 2050 VLSB.
- Final: Dec 18th 8-11am

CS70 will be using Pandagrader to manage homework submissions. You should by now have received an email with instructions from Pandagrader. If you haven't, email help@pandagrader.com.

Every week, there will be two homework parties attended by some of the TAs and readers one will be from 2-5 on Thursday and one will be held on Friday from 1:30-4:30pm. Both will take place in the Wozniak Lounge. Feel free to drop by for any help on homework and/or other questions you might have.

You may ask for a regrade on particular questions or the entire homework using pandagrader if you feel your homework was not graded correctly.

Please don't abuse the system, though, as we may be forced to regrade entire homework with stricter partial credit policies.

**No late homework is accepted!***But...*your lowest score will be dropped.**this means your lowest offline score will be dropped in addition to your lowest online score (i.e. 2 grades will be dropped)**- Collaboration is encouraged! . . . But:
- Since the main goal of homework is to help prepare for exams simply giving someone the answers will hurt them in the long run.
- Please don't post very complete answers on the web or Piazza, but please feel free to share hints and insights.
- Please remember that while collaboration is encouraged, copying constitutes cheating. Any student found cheating risks automatically failing the class and being referred to the Office of Student Conduct. Collaboration includes explaining the meaning of a question, discussing a way of approaching a solution, or collaboratively exploring how to solve a problem within your group. Copying means reading and reproducing another student's solution. In other words, you should write your homework solution strictly by yourself.
- Extra Credit is graded separately from the rest of the homework.
- Typically performance on extra credit problems is mostly relevant to the border between an A and an A+.

- Homework 0, due Tuesday Sept 3, 10:30 AM
- Homework 1, due Monday Sept 9, 5 PM [Solutions]
- Homework 2, due Monday Sept 16, 5 PM [Latex] [Solutions]
- Homework 3, due Monday Sept 23, 5 PM [Latex] [Solutions]
- Homework 4, due Monday Sept 30, 5 PM [Latex] [Solutions]
- Homework 5, due Monday Oct 7, 5 PM [Latex] [Solutions]
- Homework 6, due Monday Oct 14, 5 PM [Latex] [Solutions]
- Homework 7, due Monday Oct 21, 5 PM [Latex] [Solutions]
- Homework 8, due Monday Oct 28, 5 PM [Latex] [Solutions]
- Homework 9, due Monday Nov 4, 5 PM [Latex] [Solutions]
- Homework 10, due Monday Nov 11, 5 PM [Latex] [Solutions]
- Homework 11, due Monday Nov 18, 5 PM [Latex] [Solutions]
- Homework 12, due Monday Nov 25, 5 PM [Latex] [Solutions]
- Homework 13, due Monday Dec 9, 5 PM [Latex] [Solutions]

- Induction[Selected Solutions]
- Stable Marriage[Selected Solutions]
- Modular Arithmetic[Selected Solutions]
- RSA[Selected Solutions]
- Polynomials[Selected Solutions]
- Error Correction[Selected Solutions]
- Graphs[Selected Solutions]
- Counting and Sample Spaces[Selected Solutions]
- Conditional Probability[Selected Solutions]
- Random Variables[Selected Solutions]
- Continuous Probability[Selected Solutions]
- Infinity and Uncountability[Selected Solutions]

- wiki!
- Note 0: Sets and Mathematical Notation
- Note 1: Induction
- Note 2: Stable Marriage
- Note 3: Modular Arithmetic
- Note 4: Bijections and RSA
- Note 5: Polynomials and Finite Fields
- Note 6: Error Correcting Codes
- Note 7: An Introduction to Graphs
- Note 8: Probability Theory
- Note 9: Sample Spaces, Events
- Note 10: Conditional Probability
- Note 11: Two Killer Apps
- Note 12: Random Variables
- Note 13: Variance
- Note 14: Chebyshev + Estimating Bias
- Note 15: Some Important Distributions
- Note 16: Continuous Probability
- Note 17: How to Lie with Statistics
- Note 18: Infinity and Uncountability
- Note 19: Self-Reference and Computability

- Modular Inverse Note
- Review Session Questions: 1, 2, 3, 4, 5, 6, 7, 8
- Review Session Board Work
- Solutions to Midterm 1
- Solutions to Midterm 2
- wiki!
- Final Review Problems
- Final Review Board Work
- Solutions to Final Exam

- Lecture 1: Introduction + Induction
- Lecture 2: Induction
- Lecture 3: Induction
- Lecture 4: Induction + Stable Marriage
- Lecture 5: Stable Marriage
- Lecture 6: Modular Arithmetic
- Lecture 7: Bijections + RSA
- Lecture 8: Polynomials & Secret Sharing
- Lecture 9: Modular Arithmetic, Polynomials, Secret Sharing
- Lecture 10: Polynomials & Error Correction
- Lecture 11: Midterm I
- Lecture 12: Graphs and Eulerian Tours
- Lecture 13: Hypercubes
- Lecture 14: Probability + Counting
- Lecture 15: Counting
- Lecture 16: Sample Spaces + Events
- Lecture 17: Conditional Probability I
- Lecture 18: Conditional Probability II: Intersections and Unions
- Lecture 19: Two Killer Apps
- Lecture 20: Midterm II
- Lecture 21: Random Variables + Expectation
- Lecture 22: Expectation + Variance
- Lecture 23: Markov, Chebyshev, Bias Estimation
- Lecture 24: Some Important Distributions
- Lecture 25: Continuous Probability
- Lecture 26: Normal Distribution + How to Lie with Statistics
- Lecture 27: Infinity + Uncountable + Uncomputable
- Lecture 28: Self-Reference + Diagonalization + Uncomputable

- Discussion 1 [Solutions]
- Discussion 2 [Solutions]
- Discussion 3 [Solutions]
- Discussion 4 [Solutions]
- Discussion 5 (Advanced Version) [Solutions]
- Discussion 6 [Solutions]
- Discussion 7 [Solutions]
- Discussion 8 [Solutions]
- Discussion 9 [Solutions]
- Discussion 10 (Midterm 2 Solutions)
- Discussion 11 [Solutions]
- Discussion 12 [Solutions]
- Discussion 13 [Solutions]
- Discussion 14 [Solutions]

The Online homework is meant to help you understand the material better. Therefore there is no penalty for wrong submissions.

You should start working on your online homework as early as possible after it is posted, and in any case by the due date Fridays at 1 pm. It will help you follow the material in lectures that week. It will also make it easier for you to work on the written homework.

To access the online homework use this address: http://cs70-anari.rhcloud.com.

- Online Homework 1, due Tuesday Sept 10, 10:30 AM
- Online Homework 2, deadline extended to Tuesday 17, 10:30 AM
- Online Homework 3, due Friday Sept 20, 1:00 PM
- Online Homework 4, due Friday Sept 27, 1:00 PM
- Online Homework 5, due Friday Oct 4, 1:00 PM
- Online Homework 6, due Friday Oct 11, 1:00 PM
- Online Homework 7, due Friday Oct 18, 1:00 PM
- Online Homework 8, due Friday Oct 25, 1:00 PM
- Online Homework 9, due Friday Nov 1, 1:00 PM
- Online Homework 10, due Friday Nov 8, 1:00 PM
- Online Homework 11, due Friday Nov 15, 1:00 PM
- Online Homework 12, due Friday Nov 22, 1:00 PM
- Online Homework 13, deadline extended to Saturday Dec 7, 1:00 PM

The final grad will be calculated using the following percentages:

- 15% max(Online Homework, Offline Homework)
- 15% Offline Homework (regardless of online score)
- 20% Midterm 1
- 20% Midterm 2 (optionally we can replace midterm2 + final by max{midterm2 + final, 1.5 x final}, so students who did really poorly on the midterm have another shot at demonstrating that they did really learn the material.)
- 30% Final Exam

Feel free to attend any of the office hours listed in the table below:

You may swap between discussion sections as long as there is room in your new discussion section.

The best way to find more information about the course or get in touch with a TA is to use piazza.

If you are human feel free to replace any --at-- and --dot-- with the obvious punctuation marks below:

- Urmila: mahadev--at--eecs--dot--berkeley--dot--edu
- Nima: anari--at--eecs--dot--berkeley--dot--edu
- Jamie: jamieli550--at--gmail--dot--com
- Paul: paulfchristiano--at--gmail--dot--com
- Jonah: jsherman--at--cs--dot--berkeley--dot--edu
- Johanna: xcye--at--berkeley--dot--edu
- Stephan: shadams--at--eecs--dot--berkeley--dot--edu
- Panna: panna--at--eecs--dot--berkeley--dot--edu
- Kevin: kevintee--at--berkeley--dot--edu
- Abhishek: abhigupta--at--berkeley--dot--edu
- Tselil: tschramm--at--cs--dot--berkeley--dot--edu

Discrete mathematics and probability theory provide the foundation for many algorithms, concepts, and techniques in the field of Electrical Engineering and Computer Sciences. Induction is closely tied to recursion and is widely used, along with other proof techniques, in theoretical arguments that are critical to understanding the foundations of many things from algorithms to control to learning to signal processing to communication to artificial intelligence. Similarly for modular arithmetic and probability theory. EECS70 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:

- Induction Proofs
- Modular Arithmetic
- Graphs
- Counting and Discrete Probability
- Diagonalization, Self-Reference and Logic

These units will now be described in more detail.

**Induction Proofs**

- Simple induction
- Strong induction
- Recursion and induction
- Well ordering principle
- 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

**Graphs**

- Eulerian Tours
- Hypercubes and parallel computation

**Counting and Probability**

- Combinatorics and counting
- Probability spaces and events
- Conditional probability and Bayes' rule
- Hashing and bin packing
- Random variables and distributions
- Expectation, variance, and Chebyshev bounds
- Polling and the law of large numbers
- How to lie with statistics
- Continuous probability spaces and random variables
- Normal distributions and the Central Limit Theorem

**Diagonalization, Self-Reference and Logic**

- Cardinality of infinite sets
- Cantor's diagonalization proof
- Uncomputability and the halting problem
- Logic and Godel's incompleteness theorem