Counting

Python

Independence (probability theory)

Random variable

Joint Discrete Distributions

Correlation

Multinomial Distribution

Markov chain Monte Carlo (MCMC)

Beta distribution

Hypothesis Testing

Multi-Armed Bandits

Probability via Simulation

Discrete random variables

Continuous Random Variables

Joint Continuous Distributions

Multivariate Normal Distribution

Discrete Time Stochastic Process

Dirichlet Distribution

Bootstrapping

Markov's inequality

Convolution

Discrete Probability

Expectation

The Normal Distribution

Conditional distribution

Moment Generating Functions

Order Statistics

Maximum a Posteriori Estimation

Confidence Intervals

The Chernoff Bound

Maximum Likelihood Estimation (MLE)

Conditional probability

Variance

Transforming Random Variables

Covariance

Limit Theorems

Central Limit Theorem

Method of Moments Estimation

Properties of Estimators

Credible Intervals

Chebyshev‘s inequality

CSE 312 Foundations of Computing II University of Washington Winter 2022 This course dives deep into the role of probability in the realm of computer science, exploring applications such as algorithms, systems, data analysis, machine learning, and more. Prerequisites include CSE 311, MATH 126, and a grasp of calculus, linear algebra, set theory, and basic proof techniques. Concepts covered range from discrete probability to hypothesis testing and bootstrapping. ## Why is CSE 312 Important?

While the initial foundations of computer science began in the world of discrete mathematics (after all, modern computers are digital in nature), recent years have seen a surge in the use of probability as a tool for the analysis and development of new algorithms and systems. As a result, it is becoming increasingly important for budding computer scientists to understand probability theory, both to provide new perspectives on existing ideas and to help further advance the field in new ways.

Probability is used in a number of contexts, including analyzing the likelihood that various events will happen, better understanding the performance of algorithms (which are increasingly making use of randomness), or modeling the behavior of systems that exist in asynchronous environments ruled by uncertainty (such as requests being made to a web server). Probability provides a rich set of tools for modeling such phenomena
and allowing for precise mathematical statements to be made about the performance of an algorithm or a system in such situations.

Furthermore, computers are increasingly often being used as data analysis tools to glean insights from the enormous amounts of data being gathered in a variety of fields; you’ve no doubt heard the phrase “big data” referring to this phenomenon. Probability theory and statistics are the foundational methods used for designing new algorithms to model such data, allowing, for example, a computer to make predictions about new or uncertain events. In fact, many of you have already been the users of such techniques. For example, most email systems now employ automated spam detection and filtering. Methods for being able to automatically infer whether or not an email message is spam are frequently rooted in probabilistic methods. Similarly, if you have ever seen online product recommendation (e.g., “customers who bought X are also likely to buy Y”), you’ve seen yet another application of probability in computer science. Even more subtly, answering detailed questions like how many buckets you should have in your a hash table or how many machines you should deploy in a data center (server farm) for an online application make use of probabilistic techniques to give precise formulations based on testable assumptions.
 Our goal in this course is to build foundational skills and give you experience in the following areas:

1. **Understanding the combinatorial nature of problems**: Many real problems are based on understanding the multitude of possible outcomes that may occur, and determining which of those outcomes satisfy some criteria we care about. Such an understanding is important both for determining how ikely an outcome is, but also for understanding what factors may affect the outcome (and which of those may be in our control).
2. **Working knowledge of probability theory and some of the key results in statistics**: Having a solid knowledge of probability theory and statistics is essential for computer scientists today. Such knowledge includes theoretical fundamentals as well as an appreciation for how that theory can be successfully applied in practice. We hope to impart both these concepts in this class.
3. **Appreciation for probabilistic statements**: In the world around us, probabilistic statements are often made, but are easily misunderstood. For example, when a candidate in an election is said to have a 53% likelihood of winning does this mean that the candidate is likely to get 53% of the vote, or that that if 100 elections were held today, the candidate would win 53% of them? Understanding the difference between these statements requires an understanding of the model in the underlying probabilistic analysis.
4. **Applications in machine learning and theoretical computer science**: We are not studying probability theory simply for the joy of drawing summation symbols (okay, maybe some people are, but that’s not what we’re really targeting in this class), but rather because there are a wide variety of applications where probability and statistics allow us to solve problems that might otherwise be out of reach (or would be solved more poorly without the tools that probability and statistics can bring to bear). We’ll look at examples of such applications throughout the class. For example, machine learning is a quickly growing subfield of artificial intelligence which has grown to impact many applications in computing. It focuses on analyzing large quantities of data to build models that can then be harnessed in real problems, such as filtering email, improving web search, understanding computer system performance, predicting financial markets, or analyzing DNA. Probability and statistics form the foundation of these systems. Another example application area is the use of randomized algorithms and probabilistic data structures. These usually have simpler and more elegant implementations than their deterministic counterparts, and have more efficient time and/or space complexity. We will be learning about some of these applications and you will have the opportunity to implement some of these algorithms.
 CSE 311 and MATH 126. Here is a quick rundown of some of the mathematical tools we’ll
be using in this class: calculus (integration and differentiation), linear algebra (basic operations on vectors and matrices), an understanding of the basics of set theory (subsets, complements, unions, intersections, cardinality, etc.), and familiarity with basic proof techniques (including induction). - (Recommended) Alex Tsun, Probability & Statistics with Applications to Computing, 2020. Available free online [here](http://www.alextsun.com/files/Prob_Stat_for_CS_Book.pdf).
- (Optional) Sheldon Ross, A First Course in Probability (10th Ed.), Pearson Prentice Hall, 2018.
- (Optional) Larsen and Marx, An Introduction to Mathematical Statistics (5th edition). Prentice-Hall.
- (Optional) Dimitri P. Bertsekas and John N. Tsitsiklis, Introduction to Probability, First Edition, Athena Scientific, 2000. Available free online [here](https://www.vfu.bg/en/e-Learning/Math--Bertsekas_Tsitsiklis_Introduction_to_probability.pdf).

CSE 312 Foundations of Computing II

Mathematical Foundations

Theoretical Computer Science

Proofs

Modular arithmetic

RSA (cryptosystem)

Countability

Continuous Probability

Poisson distribution

Fermat’s Little Theorem

Secret Sharing

Combinations of Events

Total Expectation

Stable Matching

Propositional calculus (Propositional logic)

Graphs

Chinese Remainder Theorem

Error Correcting Codes

Bayes' theorem

Concentration Inequalities

Induction

Euclid

Polynomials

Computability

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

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

Combinatorics

Bernoulli distribution

Binomial distribution

Normal distribution

Joint probability distribution

Statistical inference

P-Value

Algorithmic Analysis

Maximum A Posteriori (MAP)

Naive Bayes

Logistic Regression

CS 109 Probability for Computer Scientists Stanford University Spring 2023 This course offers a thorough understanding of probability theory and its applications in data analysis and machine learning. Prerequisites include CS103, CS106B, and Math 51 or equivalent courses. CS109: Probability for Computer Scientists starts by providing a fundamental grounding in combinatorics, and then quickly moves into the basics of probability theory. We will then cover many essential concepts in probability theory, including common probability distributions, properties of probabilities, and mathematical tools for analyzing probabilities. The last third of the class will focus on data analysis and machine learning as direct applications of probability we've learned in the weeks prior. Read more here to learn what CS109 is all about. This is going to be a great quarter and we are looking forward to the chance to teach you!! After you're finished with CS109, we hope you'll have achieved the following learning goals:

- Reason about situations using probabilities, expectation, and variance.
- Feel comfortable learning about new probability concepts beyond the scope of this class (e.g., through one's own research, studies, or interests).
- Write programs to simulate random experiments and to test experiment hypotheses.
- Understand and implement simple machine learning algorithms like Naive Bayes and Logistic Regression.

## Course Topics

Here are the broad strokes of the course (in approximate order). More information is available on our Schedule page. We cover a very broad set of topics so that you are equipped with the probability and statistics you will see in your future CS studies!

- Counting and probability fundamentals
- Single-dimensional random variables
- Probabilistic models
- Uncertainty theory
- Parameter estimation
- Introduction to machine learning The prerequisites for this course are CS103, CS106B, and Math 51 (or equivalent courses). Probability involves a fair bit of mathematics (set theory, calculus, and familiarity with linear algebra), and we'll be considering several applications of probability in CS that require familiarity with algorithms and data structures covered in CS106B. Here is a quick rundown of some of the mathematical tools from CS103 and Math 51 that we'll be using in this class: multivariate calculus (integration and differentiation), linear algebra (basic operations on vectors and matrices), an understanding of the basics of set theory (subsets, complements, unions, intersections, cardinality, etc.), and familiarity with basic proof techniques. We'll also do combinatorics in the class, but we'll be covering a fair bit of that material ourselves in the first week. Past students have managed to take CS106B concurrently with CS109 and have done just fine. CS103 is the pre-requisite that we rely on the least. See our FAQ for more information. ## Optional Textbook

Sheldon Ross, *A First Course in Probability* (10th Ed.), Pearson Prentice Hall, 2018.

This is an optional textbook, meaning that the text is not required material, but students may find Ross offers a different and useful perspective on the important concepts of the class. Suggested, optional reading assignments from the textbook (10th Ed.) are in the schedule on the course website. The 8th, 9th, and 10th editions of the textbook are all fine for this class.

*Borrowing the textbook online*: HathiTrust, a library archive of which Stanford is a member, has granted the university online access to the 8th edition (2010) for the duration of the Fall quarter. The "check out" system works similarly to print reserves: A user can check out the book an hour at a time as long as they are actively using it. Access guidelines are on the [HathiTrust How To Use It webpage](https://www.hathitrust.org/ETAS-How-To). Once you're logged in, the book is at [this link](https://catalog.hathitrust.org/Record/006904347).

All students should retain receipts for books and other course-related expenses, as these may be qualified educational expenses for tax purposes. If you are an undergraduate receiving financial aid, you may be eligible for additional financial aid for required books and course materials if these expenses exceed the aid amount in your award letter. For more information, review your award letter or visit the [Student Budget website](https://financialaid.stanford.edu/undergrad/budget/index.html).

CS 109 Probability for Computer Scientists

Counting

4 courses cover this concept

CSE 312 Foundations of Computing II

CS 70: Discrete Mathematics and Probability Theory

15-455 Undergraduate Complexity Theory

CS 109 Probability for Computer Scientists