Computability

Proofs

Modular arithmetic

RSA (cryptosystem)

Countability

Conditional probability

Random variable

Continuous Probability

Poisson distribution

Fermat’s Little Theorem

Secret Sharing

Counting

Combinations of Events

Total Expectation

Central Limit Theorem

Stable Matching

Expectation

Propositional calculus (Propositional logic)

Graphs

Chinese Remainder Theorem

Error Correcting Codes

Discrete Probability

Bayes' theorem

Variance

Concentration Inequalities

Induction

Euclid

Polynomials

Independence (probability theory)

Distributions

Joint and Conditional PMFs

Gaussian Distribution

CS 70: Discrete Mathematics and Probability Theory UC Berkeley Fall 2022 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. 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. 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. There is no textbook for this class. Instead, there is a set of comprehensive lecture notes posted on [the front page](https://www.eecs70.org/) 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.

CS 70: Discrete Mathematics and Probability Theory

Mathematical Foundations

Fundamental Results

Polynomial Time

Cook-Levin Theorem

Smalll Space

Polynomial Hierarchy

Probabilistic Classes

Reversible Computation

Turing Machines

Completeness

Nondeterminism

Ladner's Theorem

Randomness

Circuit Complexity

Complexity Theory

Hardness

Satisfiabilty

Karp's List

Polynomial Space

Kolmogorov complexity

Interactive Proofs

Hypercomputation

Time Complexity

P/NP

Space Complexity

Immerman–Szelepcsényi theorem

Randomized Algorithms

Descriptive complexity theory

15-455 Undergraduate Complexity Theory Carnegie Mellon University Spring 2023 This course provides an initial dive into complexity theory, exploring computations bound by resources like time, space, and energy. Emphasis is placed on low complexity classes.  This course provides a gentle introduction into complexity theory, the theory of computations that are restricted by various resource bounds (time, space, energy, ...). We start with a brief tour of the computational universe at large and then home in on the low complexity classes that are most relevant in theoretical computer science such as P, NP, PSPACE. LOG,NLOG, BPP, RP and circuit-based classes.   

15-455 Undergraduate Complexity Theory

Theoretical Computer Science

Computability

2 courses cover this concept

CS 70: Discrete Mathematics and Probability Theory

15-455 Undergraduate Complexity Theory