EECS 70: Discrete mathematics and probability theory, Spring 2013

Final exam details

  • Location: 100 Haas Pavilion (i.e. the basketball courts). We will be in the back of the room.
  • Time: 8-11am (but IEEE will serve cake at 7:45am so get there early!)
  • Date: Thursday, May 16
  • Cheat sheets: 3 pages of 8.5"x11" handwritten notes will be permitted (both sides)
  • Calculators: silent abacus only (subject to TA approval)

A few other notes:
  • Important: You will be required to have your student ID in order to take the final. Please bring yours and remind your friends.
  • Note that there will be another class taking a final in the same room at the same time. Please do your best to be courteous to them. This includes being ready to start the final at 8am sharp.
  • If you think you are likely to ask for clarifications during the exam, please try to sit toward the outside of the row. We'll come to you but it's much easier and less disruptive if you're near the edge.

A skeleton of the exam has been released at http://inst.eecs.berkeley.edu/~cs70/sp13/exams/released.pdf and on Piazza at https://piazza.com/class#spring2013/cs70/1142. Please read through the Piazza post for clarifications on the grading scheme and ask there if you have any questions. Some highlights:
  • We will automatically drop your lowest grade in the straightforward section. Thus you are essentially being graded on your best 9 answers in that section.
  • A similar scheme is applied to the true/false section (essentially graded on your best 3 answers in that section).
  • In the straightforward section, you only have to show your work if the problem directs you to do so. Otherwise, a correct answer with no work will receive full points. In all other sections you must show work or give an explanation to get any credit.
  • Problems within the first two sections (straightforward and true/false) are weighted roughly equally.

Instructor and Lecture

GSIs and Discussion Sections

Please click here for a list of the GSIs, their office hours, and their discussion sections. This page lists some of our readers (readers also hold office hours!).

You are free to attend multiple sections as long as they aren't crowded. They will be covering the same basic material, but different GSIs might have different approaches to it.

Problem Set Party: Thursday

Due to popular demand we've decided to convert the Thursday reader office hours (4-6pm) into a second homework party with readers, GSIs, and Prof. Sahai. We have a much smaller room (380 Soda) so consider this a "mini" homework party.

Problem Set Party: Friday

Every Friday from 2-5PM in the Wozniak Lounge in 430 Soda Hall, there will be a "problem set party." This is completely optional. GSIs will be present in shifts as will some readers. Students are expected to help each other out, and if desired, form ad-hoc "pickup" homework groups in the style of a pickup basketball game.

The Woz is a relatively big space and if the weather is nice, we can also access the patio outside. But if the room is crowded, excercise good judgement and make room for others by leaving if you can find an alternative source of assistance. When the room is not crowded, people from the class are welcome to just hang out as long as they aren't bothering other people. Some social games might be available.

This is an experiment. For it to succeed, you all have to be very responsible in taking care of the room, not making messes, and putting things back the way they were.

Homework

Homeworks are always due at noon.
View statistics on homework grades

Notes (these will update)

There is no textbook for this class. Instead, the class lecture notes have been iteratively tuned through the years of different instructors teaching this course. Most everything covered in lecture will be mentioned in these notes. However, these notes are a work in progress. So they will change a bit before and after a given lecture. Consequently, it is a very good idea to at least skim the notes before attending lecture, and then read them over a couple of days after the lecture and reconcile them with your own handwritten notes.

Weekly schedule



Every week there are about 15 hours of opportunities for personalized face-to-face interaction with the course staff (faculty, GSIs, and readers) during their office hours and the weekly homework party.

In particular, you are encouraged to talk to the readers if you want any feedback regarding your assignments and the approaches that you took, and are still confused after reading the solutions, watching the video solutions, and talking with your own study group.

All on Monday:

Syllabus

Discrete mathematics and probability theory provide the foundation for many algorithms, concepts, and techniques in the field of Electrical Engineering and Computer Sciences. 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 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:

These units will now be described in more detail.

Logic and Proofs

Modular Arithmetic

Counting and Discrete Probability

Continuous Probability

Diagonalization and Self-Reference

Policies

Grading

Homework

Homeworks will be assigned each Monday evening and will be due the following Monday at noon. NO late homeworks will be accepted.

Your lowest homework score of the semester will be dropped.

Homework Submission

Homeworks will be submitted electronically, as pdfs. Details of the online submission system are on Piazza. Homeworks may be prepared by hand, in LaTeX, or even using Microsoft Word (with equation editor --- but you're much better off learning LaTeX). If by hand, you will need to scan your work. Please see scanning instructions to scan to pdf.

Note that you will need to name your file "hwX.pdf" (e.g. "hw2.pdf") in order to submit it.

Homework Grading

We will have many readers for this class, but the primary way that the homework will be graded is by yourselves. Solutions will be posted online and then you will be expected to read them and enter your own scores for every problem in the homework on a simple coarse scale (0 = didn't attempt or very very wrong, 1 = off in the wrong direction or no clear direction, 2 = half-way there, 3 = mostly right but a few things missing or wrong, 4 = 100% correct). Your grades will be due within a week of the homework deadline and if you don't enter any grades by the deadline, you are giving yourself a zero on that assignment. Make sure that you correctly enter your instructional account ID ("cs70-XX") when submitting your homework scores as this is how we will record your grade. Without this, you will get a zero for that assignment.

Just like we encourage you to use a study group for doing your homework, we strongly encourage you to have others help you in grading your assignments while you help grade theirs. This will also help you avoid self-favoritism.

The readers are going to grading a randomly selected subset of problems and so we will catch any attempts at trying to inflate your own scores. This will be considered cheating and is definitely not worth the risk.

Homework feedback

Readers are available to give you detailed feedback on your solutions during their office hours. This is intended to help you improve your understanding of the material. Make sure you bring either a printout of your homework or your laptop with the file open for the ease of the readers.

Reader office hours: If you have any questions, please ask on Piazza.

Exams

There will be two midterms and one final exam.

Grade Breakdown

Extra credit will be available for many creative activities. (For example: translate the key ideas in a lecture into Internet Memes, make a web demo for a particular concept, create your own YouTube video explaining a concept in a way that is complementary to the way it had been discussed in class, creating practice problems with solutions, etc...) Talk with your GSI in person or post on Piazza if you want to get feedback from the entire class.

Course Communication

The instructors and TA will post announcements, clarifications, hints, etc. on Piazza. Hence you must check the CS70 Piazza page frequently throughout the term. (You should already have access to the CS70 Spring 2013 forum. If you do not, please let us know.) 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 mark your question as private on Piazza, so only the instructors will see it. 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, we expect the students to be familiar with reading and designing programs.

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 officially 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. Unofficially, you are welcome to attend other discussion sections but only if there is physical room. Get up and leave if there are registered students waiting. You also might not get participation credit from the other TA.

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

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 -- we really do care that you learn!

Accommodations for Students with Physical, Cognitive, or Psychological Disabilities

If you have been issued a letter of accommodation from the Disabled Students Program (DSP), please contact Professor Sahai as soon as possible to work out the necessary arrangements. If you need an accommodation and have not yet seen a Disability Specialist at the DSP, please do so as soon as possible.

If you would need any assistance in the event of an emergency evacuation of the building, the DSP recommends that you make a plan for this in advance. (Contact the DSP accest specialist at 643-6456.)

Illness

If you have a fever, do not come to lecture or discussion or office hours or to the problem set party until at least 24 hours after the fever has passed. Email your GSI to let them know. If this forces you to miss a homework, we will drop an extra homework for you.

Similarly, do not attend a midterm if you have a fever. Please let us know a short time in advance if this is going to happen, and we will make appropriate accomodations.

For non-contagious illnesses, use your good judgement. But spreading contagious disease is just horrible manners if you can prevent it.

Advice

The following tips are offered based on our experience with this course.

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, you must read the sample solutions. 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! A good practice 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.

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. You are strongly advised 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. Some groups try to 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.