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. Concretely this means having taken a college-level math course (Math 1A/B, 16A/B or other linear algebra). More broadly this means experience in math that doesn’t focus on just plug-and-chug calculations or algebraic manipulations.

Topics Covered

  • Basic logic
  • Proofs (direct, by contradiction, by contrapositive)
  • Induction
  • Stable Matching
  • 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, Central Limit Theorem)
  • Linear regression
  • Conditional expectation
  • Markov Chains

Workload

Course Work

  • Weekly problem sets
  • One midterm
  • One final

Time Commitment

There are 3 hours of lecture and 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, CS188, CS 189.

Usefulness for Research or Internships

CS70 is somewhat helpful for research and software engineering internships -- the problem solving aspect of CS70 might prove helpful for some interviews, as well as understanding more complex research theory. CS70 is also extremely useful for quantitative trading internships, as the probability portions of the course will cover almost all interview questions of that variety. 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. 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 will be less likely to struggle during a test.

Last edited: Spring 2023