CS70: Discrete Mathematics and Probability Theory, Summer 2015


Instructor: Chung-Wei Lin
Email: cwlin@eecs.berkeley.edu
Lecture: M-Th 2-3:30pm, 155 Dwinelle
OH: M 4:30-5:30pm, 504 Cory
       W 6-7pm, 531 Cory

Head TA: Steven Bi
Email: chenhsi@berkeley.edu

TA: Caroline Chan
Email: cchan14@berkeley.edu
DIS: Tu-F 10-11am, 405 Soda
OH: Th 12-1pm, 411 Soda

TA: Favian Ho
Email: favianho@berkeley.edu
DIS: Tu-F 11-12pm, 102 Latimer
OH: W 4-5pm, 411 Soda

TA: Nathan Mandi
Email: nvmandi7@berkeley.edu
DIS: M-Th 4-5pm, 310 Soda
OH: Tu 12-1pm, 611 Soda

TA: Kunal Marwaha
Email: marwahaha@berkeley.edu
DIS: M-Th 4-5pm, B51 Hildebrand
OH: Tu 5:30-6:30pm, 611 Soda

TA: Anna Papitto
Email: annapapitto@gmail.com
DIS: M-Th 5-6pm, 310 Soda
OH: Tu 6-7pm, 611 Soda

TA: Akshay Ramachandran
Email: akshayram@berkeley.edu
DIS: M-Th 5-6pm, 102 Latimer
OH: Tu 6:30-7:30pm, 611 Soda

TA: Diana Rha
Email: diana.yeji@berkeley.edu
DIS: Tu-F 1-2pm, 405 Soda
OH: W 6-7pm, 531 Cory

TA: Lexing Tong
Email: lexing.tong@berkeley.edu
DIS: M-Th 5-6pm, 3107 Etcheverry
OH: Tu 4-5pm, 611 Soda

TA: Jerry Ueijo
Email: jerryuejio@gmail.com
DIS: M-Th 4-5pm, B56 Hildebrand
OH: Th 5:15-6pm, 611 Soda

TA: Nathan Zhang
Email: nzhang32@berkeley.edu
DIS: Tu-F 12-1pm, 3107 Etcheverry
OH: W 10-11am, 651 Soda
       Th 7-8pm, 212 Cory



Note Topic Lecture
Note 0 Review of Math Notation --- 4C 6C 8C
Note 1 Propositions and Quantifiers 1A, 1B
Note 2 Proofs 1B, 1C
Note 3 Induction 1D
Note 4 Stable Marriage 2A, 2B
Note 5 Modular Arithmetic 2C
Note 6 Bijections and RSA 2D, 3A
Note 7 Polynomials 3A, 3B
Note 8 Error Correcting Codes 3C
Note 9 Counting 3D, 4A
Note 10 Introduction to Discrete Probability 4A, 4B, 4D
Note 11 Conditional Probability 4D, 5A, 5B, 5C
Note 12 Random Variables 5C, 5D
Note 13 Variance 6A, 6B
Note 14 Two Killer Applications 6B, 6D
Note 15 Chebyshev's Inequality 7A, 7B
Note 16 Some Important Distributions 7B, 7C
Note 17 Continuous Probability ---
Note 18 Graph Theory 7D, 8A
Note 19 Infinity and Uncountability 8B
Note 20 Self-Reference and Uncomputability ---


Week 1 1A / Answer 1B / Answer 1C / Answer 1D / Answer
Week 2 2A / Answer 2B / Answer 2C / Answer
Week 3 3A / Answer 3B / Answer 3C / Answer 3D / Answer
Week 4 4A / Answer 4B / Answer Review
Week 5 5A / Answer 5B / Answer 5C / Answer 5D / Answer
Week 6 6A / Answer 6B / Answer Review
Week 7 7A / Answer 7B / Answer 7C / Answer 7D / Answer
Week 8 8A / Answer 8B / Answer Review


Midterm 1 Jul 16 (Thu) 6-8pm Solution
Midterm 2 Jul 30 (Thu) 6-8pm Solution
Final Exam Aug 13 (Thu) 6-9pm Solution


HW Problem Due Date HW Party Time HW Party Location HW Solution
Homework 0
Homework 1 Jun 29 (Mon) Noon Jun 26 (Fri) 2-5pm 540 Cory (ASV Room)
Homework 2 Jul 6 (Mon) Noon Jul 3 (Fri) 2-5pm 430-438 Soda (Woz Lounge)
Homework 3 Jul 13 (Mon) Noon Jul 10 (Fri) 2-5pm 430-438 Soda (Woz Lounge)
Homework 4 Jul 21 (Tue) Noon Jul 17 (Fri) 2-5pm 540 Cory (ASV Room)
Homework 5 Jul 28 (Tue) Noon Jul 24 (Fri) 2-5pm 430-438 Soda (Woz Lounge)
Homework 6 Aug 4 (Tue) Noon Jul 31 (Fri) 2-5pm 430-438 Soda (Woz Lounge)
Homework 7 Aug 10 (Mon) Noon Aug 7 (Fri) 2-5pm 540 Cory (ASV Room)




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.

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

Don't wait until the last minute to start homeworks! Our 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 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!)

Come to homework parties! We encourage collaboration on homeworks (but please read the homework policy above! all solutions must be your own). If you want to find a group to work with, or you and your friends want a nice place to work together, come to the homework parties.

Take part in discussion sections! Discussion sections are not auxiliary lectures. They are an opportunity for interactive learning, through guided group problem solving and other activities. 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.

Pay attention in lectures! As the semester proceeds, many of you will no doubt feel the urge to "daydream" during lectures, or to skip them altogether, on the grounds that you can catch up by reading the lecture notes. If you follow this strategy, you should be aware that reading mathematics is NOT the same as reading a novel or a news article: each page of mathematics needs to be read many times before it is fully understood, and needs to be backed up by examples and discussion. Following the material in class should save you several readings; even just watching it go by without fully understanding it makes your later reading easier. And you also get the benefit of student questions, examples etc. Exactly how you handle lectures is up to you. One strategy is to print out the lecture notes in advance, bring them to lecture, and add a few additional notes during class.