Fall 2022

UC Berkeley

CS 70 presents key ideas from discrete mathematics and probability theory with emphasis on their application in Electrical Engineering and Computer Sciences. It addresses a variety of topics such as logic, induction, modular arithmetic, and probability. Sophomore mathematical maturity and programming experience equivalent to an Advanced Placement Computer Science A exam are prerequisites.

Logic, infinity, and induction; applications include undecidability and stable marriage problem. Modular arithmetic and GCDs; applications include primality testing and cryptography. Polynomials; examples include error correcting codes and interpolation. Probability including sample spaces, independence, random variables, law of large numbers; examples include load balancing, existence arguments, Bayesian inference.

Sophomore mathematical maturity, and programming experience equivalent to that gained with a score of 3 or above on the Advanced Placement Computer Science A exam.

The goal of this course is to introduce students to ideas and techniques from discrete mathematics that are widely used in Electrical Engineering and Computer Sciences. The course aims to present these ideas "in action"; each one will be geared towards a specific significant application. Thus, students will see the purpose of the techniques at the same time as learning about them.

There is no textbook for this class. Instead, there is a set of comprehensive lecture notes posted on the front page for each lecture. Make sure you revisit the notes after every lecture. Each note may be covered in one or more lectures.

Distinguished Alum Megan says, “When I took the course, I studied the notes until I was able to comfortably reproduce all of the proofs.

Bayes' theoremCentral Limit TheoremChinese Remainder TheoremCombinations of EventsComputabilityConcentration InequalitiesConditional probabilityContinuous ProbabilityCountabilityCountingDiscrete ProbabilityDistributionsError Correcting CodesEuclidExpectationFermat’s Little TheoremGaussian DistributionGraphsIndependence (probability theory)InductionJoint and Conditional PMFsModular arithmeticPoisson distributionPolynomialsProofsPropositional calculus (Propositional logic)RSA (cryptosystem)Random variableSecret SharingStable MatchingTotal ExpectationVariance