CS70
Discrete Mathematics and Probability Theory
Fall 2013
Previous sites:
http://inst.eecs.berkeley.edu/~cs70/archives.html
Instructor and Lecture
- 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
Announcements:
Dates to remember:
- 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
Homeworks
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.
Homework Regrade Policy:
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.
Other Important Homework 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 Assignments:
- 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]
Practice Problems
Notes
Supplements
Lecture Slides
Discussion Handouts
Online Homework
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
Grading Policies:
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
Office Hours:
Feel free to attend any of the office hours listed in the table below:
Discussion Sections:
You may swap between discussion sections as long as there is room in your new discussion section.
Links and GSI Contact Info:
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
Syllabus
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