Discrete random variables

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

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)

Counting

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

Histories of AI

Societal impacts of AI

Vector (mathematics and physics)

Dot product

Geometric interpretations

Taking gradients

Probability distributions

Mean

Marginal distributions

Big-O notation

Computational complexity

Recurrence relation

Dynamic programming

Continuous optimization

Objective functions

Gradient descent

Machine learning

Loss minimization

Hinge loss

Equitable performance

Design and organization of features

Computation graphs

Deep learning models composition

Cross-validation (statistics)

Search problem

Breadth-first search (BFS)

Uniform cost search (UCS)

UCS heuristics

Markov Decision Process (MDP)

Transportation problem

Discounting factor

Reinforcement learning (RL)

Model-free Monte Carlo

Q-learning

Function approximation

Game theory

Minimax algorithm

Temporal difference (TD) learning

Variable-based models

Backtracking search

Gibbs sampling

Bayesian network

Laplace smoothing

Logic

Entailment

Satisfiability

Soundness

Modus ponens

First-order logic

Unification (computer science)

Linear regression

Linear classification

Stochastic gradient descent (SGD)

Non-linear functions

Neural network

Backpropagation

Generalization

K-means clustering

Exhaustive search

Depth-first search (DFS)

UCS correctness

Relaxed search problems

Dice game

Policy evaluation

Value iteration

Model-based Monte Carlo

State–action–reward–state–action (SARSA)

Epsilon-greedy exploration

Deep Reinforcement Learning

Halving game

Alpha-beta pruning

Nash equilibrium

Factor graphs

AC-3 algorithm

Markov random field

Hidden Markov Model (HMM)

Propositional calculus (Propositional logic)

Contradiction

Model checking

Completeness

Horn clauses

Substitution (logic)

Skolem functions

CS 221 Artificial Intelligence: Principles and Techniques Stanford University Autumn 2022-2023 Stanford's CS 221 course teaches foundational principles and practical implementation of AI systems. It covers machine learning, game playing, constraint satisfaction, graphical models, and logic. A rigorous course requiring solid foundational skills in programming, math, and probability. The goal of artificial intelligence (AI) is to tackle complex real-world problems with rigorous mathematical tools. In this course, you will learn the foundational principles and practice implementing various AI systems. Specific topics include machine learning, search, Markov decision processes, game playing, constraint satisfaction, graphical models, and logic.  This course is fast-paced and covers a lot of ground, so it is important that you have a solid foundation in a number of areas. Here are the basic skills that you need and the classes that teach those skills:

- Programming (ideally Python): [CS 106A](http://www.stanford.edu/class/cs106a/), [CS 106B](http://www.stanford.edu/class/cs106b/), [CS 107](http://www.stanford.edu/class/cs107/)
- Discrete math, mathematical rigor: [CS 103](http://www.stanford.edu/class/cs103/)
- Probability: [CS 109](http://www.stanford.edu/class/cs109/)
- Linear algebra: [Math 51](https://web.stanford.edu/class/math51/textbook.html)

It is less important that you know particular things (e.g., we don't use eigenvectors in this course even though that's a pillar of any linear algebra course), and more important that you've done enough related things that you feel at ease with it. While it is possible to fill in the gaps, this course does move quickly, and ideally you want to be focusing your energy on learning AI rather than catching up on prerequisites. We have made a few [prerequisite modules](https://stanford-cs221.github.io/autumn2022/modules) that you can review to refresh your memory, and the first homework (foundations) will allow you to also get some practice on these basics. ### Further Reading

There are no required textbooks for this class, and you should be able to learn everything from the lecture notes and homeworks. However, if you would like to pursue more advanced topics or get another perspective on the same material, here are some great resources:

- [Russell and Norvig. Artificial Intelligence: A Modern Approach](http://aima.cs.berkeley.edu/). A comprehensive reference for all the AI topics that we will cover.
- [Koller and Friedman. Probabilistic Graphical Models](http://mitpress.mit.edu/books/probabilistic-graphical-models). Covers factor graphs and Bayesian networks (this is the textbook for CS228).
- [Sutton and Barto. Reinforcement Learning: An Introduction](https://mitpress.mit.edu/books/reinforcement-learning). Covers Markov decision processes and reinforcement learning (free online).
- [Hastie, Tibshirani, and Friedman. The Elements of Statistical Learning](https://web.stanford.edu/~hastie/ElemStatLearn/). Covers machine learning from a rigorous statistical perspective (free online).
- [Tsang. Foundations of Constraint Satisfaction](http://www.bracil.net/edward/fcs.html). Covers constraint satisfaction problems (free online).

Note that some of these books use different notation and terminology from this course, so it may take some effort to make the appropriate connections.

CS 221 Artificial Intelligence: Principles and Techniques

Artificial Intelligence

Discrete random variables

2 courses cover this concept

CSE 312 Foundations of Computing II

CS 221 Artificial Intelligence: Principles and Techniques