Computer Science 70 — Discrete Mathematics and Probability Theory (4 Units)

Course Overview

Summary

The purpose of CS70 is to provide the foundation for algorithms, concepts, and techniques to be expanded upon in further EECS classes. This foundation includes writing proofs (with various proof techniques), Boolean logic, modular arithmetic, basic graph theory, and discrete and continuous probability.

Prerequisites

  • CS61A or E7

Mathematical maturity recommended.

Topics Covered

  • Basic logic
  • Proofs (direct, by contradiction, by contrapositive)
  • Induction
  • Stable Marriage
  • Graph Theory (hypercubes, Eulerian paths, Hamiltonian paths)
  • Modular Arithmetic (Euclid's Algorithm, Extended Euclid's)
  • Bijections, RSA, Fermat's Little Theorem
  • Polynomials over finite fields (secret sharing, error-correcting codes, Berlekamp-Welsh)
  • Countability and Computability
  • Counting and Combinatorial Arguments
  • Discrete Probability, Conditional Probability, Probabilistic Inference (Bayes Rule), Independence
  • Probability: Expectation and Variance (applications with hash tables)
  • Law of Large Numbers, Confidence Intervals, Linear Regression
  • Distributions (discrete, continuous)
  • Bounds (Markov, Chebyshev, Chernoff, Central Limit Theorem)
  • Markov Chains

Workload

Course Work

  • Weekly problem sets
  • Two midterms
  • One final

Time Commitment

There are 3 hours of lecture and 1 or 2 hours of discussion per week.

Expect a steady workload from the weekly problem sets taking 10-15 hours.

Choosing the Course

When to take

Take this class as soon as possible (after taking CS61A), as it is a prerequisite for many upper division classes.

What next?

After CS70, it is a good idea to take CS170 (Algorithms), because the class is of a similar format. CS70 is a prerequisite for many other upper division classes, including EE126, CS161, CS162, and CS188.

Usefulness for Research or Internships

CS70 is somewhat helpful for research and internships -- the problem solving aspect of CS70 might prove helpful for some interviews, as well as understanding more complex research theory. However, CS70 is a prerequisite for CS170, which is a very useful class for computer science job interviews.

Additional Comments/Tips

It is highly recommended that you work on the problem sets in a study group; not only will you likely finish quicker, but you can help each other understand the concepts, and ultimately you will have an easier time studying for the exams. The staff usually holds 1-2 weekly homework parties for this purpose.

The course is also split up into two separate sections, the first being discrete math and the second being probability. The general consensus is that the probability portion of the course (second half of the course) is significantly more difficult. In other words the class does not increase in difficult linearly; the last part of the course has a huge spike in difficulty. Make sure you keep up with lectures, discussion, and homework.

The course also differs in flavor with different professors. If you take CS70 with Professors Rao or Walrand, the homeworks are not as intensive as Professor Sahai’s variant of the course, but the exams are significantly more challenging. The course with Professor Sahai has a much larger workload in terms of problem sets, but the exams are slightly easier than those of Rao and Walrand.

To obtain a firm grasp of the concepts being taught in class, it is important to not only complete the homeworks, but to understand them. Test questions are usually slight variations and are often easier than the homework questions. Therefore, if you are able to solve the homework questions, then you be more likely to not struggle during a test.