Spring 2017 CS70 at UC Berkeley




A lightweight task manager containing all current CS70 tasks, both recommended and required. Try it.


We will use Piazza as the 'one-stop shop' throughout the semester: for a Q&A forum and for official announcements. Enrollment in Piazza is mandatory. If you have questions about anything related to the course, please post them on Piazza rather than emailing the instructor or TAs. Please do not post anything resembling a solution to a homework problem before it's due. If in doubt, you should make your post private (visible to instructors only). We always welcome any feedback on what we could be doing better. See the Piazza Etiquette section for more on using Piazza. To join the class on Piazza, follow this link piazza.com/berkeley/spring2017/cs70.


All homework will be submitted through Gradescope, and all homework and exam grades will be given back through Gradescope. To join the class on Gradescope, go to gradescope.com and enter this code: MDDBYM

Instructional Servers

CS70 does not make use of instructional accounts, but to get a computer account for this course, go to http://inst.eecs.berkeley.edu/webacct, or click 'WebAcct' on http://inst.eecs.berkeley.edu.


Midterm 1 is on Monday, Feb 13, 2017 8:00pm - 10:00pm. Midterm 2 is Thursday, Apr 06, 2017 7:00pm - 9:00pm.

Piazza Etiquette

Important Note:

We will encourage more student participation on Piazza rather than answering right away, that is, we will wait until other students step up and answer questions.

Of course, we will still provide clarifications on logistics, typos, subtle points, etc.

We want to make sure that you are helping each other out, and having instructors give away the answers isn't the most beneficial for your education either.

In order to make Piazza a better resource for everyone, we've outlined some guidelines for you to follow when posting your questions. Questions which follow these guidelines will have a higher chance of being answered!

1. Ask HW questions only in HW posts.

We've created individual posts for each problem from homework. Please ask questions, discuss problems, or help out in those posts only. Before asking a question, read through (or search) the whole post to see if your question has been answered.

2. Don't post answers in Piazza.

Please don't give away the answer on Piazza. You can explain things in a way that still lets other students figure out the essence of the problem on their own, but don't spoil the problem. For example, don't point to a useful YouTube link that works out essentially what the problem is asking about.

That is not cool.

Post such spoilers after the HW is due. That is totally fine. If you are not sure, post privately to instructors and then we'll let you know.

3. Try to make posts public.

While not violating Rule 2, try to make your questions public, because others might have the same question and we don't need to answer them multiple times.

4. Piazza is not OH. 5 minute-test.

If you think your questions may take more than 5 minutes to answer, please come to office hours or homework parties instead.

5. Neither Piazza nor TAs are for pre-grading.

Please do not post questions of the form:

  • "Is this the correct solution to hw X problem Y?"
  • "Would this receive full credit on hw X problem Y?"
  • "Is this the right level of detail for hw X problem Y?"

Please do not use Piazza as a medium to ask instructors to check your homework in advance. We simply cannot check every student's homework through Piazza.

Feel free to ask questions of clarification, or ask questions about the course content to achieve a deeper understanding, but at a certain point, you must apply your knowledge, give it your best shot, and submit your answers with confidence.

6. Post a screen shot of any resource referenced.

Your question should be self contained. The TAs (and other responders) should not have to scan through PDFs to even figure out what the question is. Ask yourself: am I referring to some lecture slide / lecture note / hw solution / discussion solution?

If the answer is yes, post a screen shot of the relevant part.

7. Post all your work.

Don't post one line saying:

At step n, I get XYZ, and I'm now confused.

This forces the TAs to guess:

What happened in steps 1, 2, ..., n-1 ?

Most likely, the TAs will guess wrong, and we run into a mess of followup questions trying to figure out what steps 1, 2, ..., n-1 were.

Instead, post:

Starting out, we have: ....

Then, I do ..., and I get ...

Next, I do ..., and I get ...

Next, I do ..., and I get ...

Now, I get $&%&#(, and this makes no sense.

Then, the TA can respond:

The mistake is at step 3, you're not allowed to apply ABC to XYZ because ...

8. Post narrow, precise questions.

Question of the form "Can someone please explain stable marriage to me?" are not helpful.

There's an entire lecture note written on it. There are multiple parts to stable marriage:

  • actual algorithm
  • proof of termination
  • proof of stability
  • proof that it's male optimal
  • proof that it's female pessimal

No TA is arrogant enough to think they can rewrite the lecture better than notes that have evolved over decades of teaching. Instead, the question should be precise, like:

Title: Can someone please explain this step of the proof of stability?


[ Image of Stable Marriage Algorithm ]

[ Image of Proof of Stability / with an arrow draw in ]

In the proof of stability, I get that we have:

  • fact 1 in your own words
  • fact 2 in your own words
  • fact 3 in your own words

However, I don't get how we get:

  • fact 4 in your own words



There is no textbook for this class. Instead, there is a set of fairly comprehensive lecture notes. Make sure you revisit the notes after lecture. Each note may be covered in one or more lectures. Note 0 is background material that you should make sure you understand before the first lecture.


Release Schedule: Discussions for the coming week are released the Sunday before at 10 p.m. Discussion A solutions are published every Tuesday at 10 p.m., and Discussion B solutions are published every Thursday at 10 p.m.

The discussion sections will not cover new material, but rather will give you additional practice solving problems. You can attend any discussion section you like. However, if there are fewer desks than students, then students who are officially enrolled in that section will get seating priority.


Release Schedule: Every Friday at 10 p.m., homework for the coming week is released. Homework is then due on Gradescope the following Friday at 10 p.m.; the solutions for that homework will be released 2 hours after the deadline. Homework is then returned to you, graded, approximately one week after the deadline.

All homeworks are graded for accuracy and it is highly recommended that you do them. You are expected to show your work and justify all of your answers. Your lowest homework score will be dropped, but this drop should be reserved for emergencies.


Release Schedule: Slides are released the Sunday before at 10 p.m. the day of.
Slides generally follow the notes. Lecture videos are provided via CalCentral.


The following is the list of topics that we will be covering this semseter, roughly in the order specified below.

Review of Math Notation

Propositions and Quantifiers



Stable Marriage

Graph Theory

Modular Arithmetic

Bijections and RSA


Error Correcting Codes

Infinity and Uncountability

Self-Reference and Uncomputability


Introduction to Discrete Probability

Conditional Probability

Two Killer Applications

Random Variables


Chebyshev's Inequality

Some Important Distributions

Continuous Probability

Markov Chains

Review of Probability



We have a zero-tolerance policy for cheating. First-time offenses will result in negative points for the corresponding assignment and a meeting with the professors and/or head TAs. Second-time offenses will see more serious consequences, possibly a failing grade and definitely a referral to the Center for Student Misconduct.


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. 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 strongly encourage. But you should write your homework solution strictly by yourself so that your hands and eyes can help you internalize this material. 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 being a jerk or free-rider regarding 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.

However, we are very fair. No student will be accused of cheating without a human being looking over their case. And nobody will be sent to Student Conduct without at least the head TA and Prof concurring that this is warranted and makes sense. Algorithms help us focus our attention, but decisions are made by compassionate human beings.


We are allowing students to not do homework if they choose not to have an assessment method for this approach. You make the choice of how you wish to proceed after getting feedback on the first homework. For both options, you are encouraged to access the course resources that are available to you all; help in hw parties, office hours that will be additionally staffed by readers, discussions, and piazza.

The Sundry item below is simply some questionaires which should take roughly half an hour. Both options require them.

Test-Only Option

  • Midterm 1: 25%
  • Midterm 2: 25%
  • Sundry: 1%
  • Final: 49%

Homework Option

Note that the "Test-only Score" below includes all categories from the "Test-Only Option" listed above: midterm 1, midterm 2, sundry, and final.

  • Homework: 15%
  • Test-only Score: 85%

Discussion of Options

These two configurations correspond to the European test at the end approach, and the standard American approach where we force students to do homework to keep up. There are clear arguments for each approach, and it is difficult for us to know what will produce the best results for students. This is an endeavor to let you choose.

Regardless of which option you choose, the course staff will support you: put together relevant homeworks for practice, along with solutions, have sections, with section worksheets, and solutions, homework parties, office hours with additional support beyond the teaching assistants, and some tutoring support.