Propositional calculus (Propositional logic)

Random variable

Set theory

Expectation

Conditional probability

Independence (probability theory)

Randomized Algorithms

Large Deviation Bounds

Packet Routing

Sample Complexity

Martingales

Rademacher complexity

Probabilistic Method

Hashing

Markov Chains

Monte Carlo method

CSCI 1550/2450 Probabilistic Methods in Computer Science Brown University Spring 2022 This analytical course dives into the mathematical underpinnings of computing successes like machine learning and cryptography, emphasizing the role of probability, randomness, and statistics. Students will explore mathematical models, theorems, and proofs. Practical implementations are not covered, focusing instead on the theories driving computational probabilities. CSCI 1550/2450 is a course on the mathematics that motivates, formulates, and explains many of the great successes of computing, including statistical machine learning, Monte Carlo methods, and modern cryptography. Probability, randomness, and statistics play a key role in these and almost any other modern computer science application. This course introduces the novel mathematical and computation methods that were developed at the interplay of probability and computing. The course focuses on mathematical models, theorems and proofs, and leaves implementation and experiments to other courses. - CSCI 1550/2540 is a theory/analytical course - analysis, theorems, no implementations.
- The course covers modern mathematics at the interface of probability theory and computation
- Formulates, and explains many of the great successes of computing, such as machine learning, cryptography, modern finance, computational biology, etc.
- This course focuses on tools, not particular applications. CS145 or equivalent (first three chapters in the course textbook). ## Textbook

The textbook for the course is *[Probability and Computing Randomization and Probabilistic Techniques in Algorithms and Data Analysis, 2nd Edition](https://www.amazon.com/Probability-Computing-Randomization-Probabilistic-Techniques/dp/110715488X/ref=dp_ob_title_bk)* by [Michael Mitzenmacher](http://www.eecs.harvard.edu/%7Emichaelm/) and [Eli Upfal](/people/eli).

[Errata for the 1st Printing](http://www.eecs.harvard.edu/%7Emichaelm/MUErrataPrint1.pdf), [Errata for the 2nd Printing](http://www.eecs.harvard.edu/%7Emichaelm/MUErrataPrint2.pdf)

CSCI 1550/2450 Probabilistic Methods in Computer Science

Statement (logic)

Proof by contradiction

Truth table

Conjunctive normal form (CNF)

Disjunctive normal form (DNF)

First-order logic

Quantifier (logic)

Relation (mathematics)

Binary relation

Bijection, injection and surjection

Mathematical induction

Number theory

Modular arithmetic

RSA (cryptosystem)

Binomial theorem

The Pigeon Hole Principle

Probability theory

Graph theory

Tree (graph theory)

Random walk on graphs

CSCI 0220 Discrete Structures and Probability Brown University Spring 2023 CSCI 0220 provides a foundation in discrete math and probability theory. Key topics include logic, set theory, number theory, combinatorics, graph theory, and probability. No prior math background assumed. Aims to develop problem solving, communication, and collaboration skills. Introduces new concepts and ways of thinking to enable analyzing problems arising in computer science. Beginner-friendly introduction to core mathematical concepts underlying many aspects of CS. I don't know about you, but we're feeling 22! This class gives you the tools to explore interesting questions and convince yourself and others of their answers. You'll be introduced to new worlds of ideas and ways of thinking. We'll learn about Set Theory, Logic, Number Theory, Combinatorics, Graph Theory, and Probability. If these topics sound unfamiliar, not to fear: you're in exactly the right place! This course assumes no prior experience with these topics.  CS can feel like a very applied field. Why learn math?

- Problem solving
- Communication
- Collaboration

A key result of this class: you’ll have a vocabulary for discussing certain kinds of
problems that appear in many different contexts, and a toolbox of general approaches
for solving them.

A vital point of computer science (academic, industry, hobbyist): *communication*. Our expectations from you

- No mathematical background is assumed. We’re not doing calculus, statistics, ...
- Approach things with an open mind.
- Try to communicate clearly and concisely.
- Respect your classmates and TAs: we’re in this together.
- Let us know how you’re doing! [Mathematics for Computer Science — Lehman, Leighton, Meyer](https://cs22.io/static/files/Mathematics_for_Computer_Science.pdf)

Reading (and purchasing!) this textbook is not required, though many students in the past have found it helpful in reinforcing what's covered in lecture! 

CSCI 0220 Discrete Structures and Probability

Mathematical Proofs

Indirect Proofs

Function (computer programming)

Graphs

Mathematical Induction

Finite Automata

Regular Expressions

CS 103: Mathematical Foundations of Computing Stanford University Winter 2023 CS 103 introduces mathematical logic, proofs, and discrete structures, paving the way to an understanding of computational problem-solving. It encourages a profound appreciation of mathematical beauty while addressing concepts like finite automata and regular expressions. CS106B is a prerequisite or corequisite. The course also incorporates programming assignments. Are there “laws of physics” in computing? Are there fundamental restrictions to what computers can and cannot do? If so, what do these restrictions look like? What would make one problem intrinsically harder to solve than another? And what would such restrictions mean for our ability to computationally solve meaningful problems?

In CS103, we'll explore the answers to these important questions. We'll begin with an introduction mathematical logic, proofs, and discrete structures (sets, relations, functions). These mathematical tools will enable the real heart of the course, which is to rigorously answer questions like “what does it mean for a computer to solve a problem?” and “what makes some problems (sorting) inherently harder than others (searching)?”

In the course of the quarter, you'll see some of the most impressive (and intellectually beautiful) mathematical results of the last 150 years. In some ways, I like to think of this course as a course in both art appreciation and practice. I’ll bring you through a gallery and show you some of my favorite achievements of mathematical artistic beauty, and like a good tour guide help you understand what is special about what you’re looking at. You’ll also need to pick up the paintbrush yourself and write some proofs of your own. You'll learn how to think about computation itself and how to show that certain problems are impossible to solve. Finally, you'll get a sense of what lies beyond the current frontier of computer science, especially with regards to biggest open problem in math and computer science, the P = NP problem.  CS103 has CS106B as a prerequisite or corequisite. This means that if you want to take CS103, you must either have completed or be concurrently enrolled in one of CS106B or CS106X (or have equivalent background experience).

Over the course of the quarter, we will be giving out a number of programming assignments to help you better understand the concepts from the course. Those assignments will assume a familiarity with C++ and programming concepts (especially recursion) at a level that’s beyond what’s typically covered in CS106A. The timing on these assignments is designed so that they’ll sync up with what’s covered in CS106B.

Although CS103 is a course on the mathematical theory behind computer science, the only actual math we'll need as a prerequisite is high-school algebra. We'll build up all the remaining mathematical machinery we need as we go. We've released another handout detailing the mathematical prerequisites for this course, so if you have any questions, check it out and see what you find! ### Readings

There are two recommended textbooks for this quarter. The first is How to Read and Do Proofs by Daniel Solow, which is a great resource for learning how to approach mathematical problem-solving. The second is Introduction to the Theory of Computation, Third Edition by Michael Sipser. You might find this book useful in the second half of the quarter. We will never directly test material available only in the textbooks; the course materials we provide will be all you need.

There are copies of each of these books in reserve in the Engineering Library.

A helpful note from the School of Engineering:

*“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 103: Mathematical Foundations of Computing

Counting

Combinatorics

Bayes' theorem

Variance

Bernoulli distribution

Binomial distribution

Poisson distribution

Continuous Random Variables

Normal distribution

Joint probability distribution

Statistical inference

Beta distribution

Central Limit Theorem

Bootstrapping

P-Value

Algorithmic Analysis

Maximum Likelihood Estimation (MLE)

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

Register Machines

Iteration 

Closure

Zero Space

Minimization

Logic

Infinite Words

Groups

Polya Counting

Feedback Shift Registers

Coding Theory

Effective Resistance

Hypercomputation

Computation & Discrete Math

Primitive Recursion

Decidability

Orbits

Nondeterminism

Automata

Determinization

Finite Fields

15-354 Computation & Discrete Math Carnegie Mellon University Spring 2021 This advanced course reexamines traditional concepts of discrete mathematics (relations, functions, logic, graphs, algebra, automata) in the context of computation and algorithms, necessitating a strong background in discrete math. In a nutshell, the main idea behind this course is that the development of the digital computer, together with the theory of computation, is also one of the most important developments in mathematics in the 20th century. Consequently, this course takes a fresh look at some of the standard concepts of discrete mathematics (relations, functions, logic, graphs, algebra, automata), with strong and consistent emphasis on computation and algorithms. Another key concern is knowledge transfer: we need to realign traditional mathematical concepts with our new computational universe and find ways to apply ideas from one realm to the other. We begin with a brief introduction to computability and computational complexity. Other topics may include: iteration, orbits and fixed points; order and equivalence relations; transition systems; groups and actions; finite fields, randomness; propositional logic and satisfiability testing.

To get a better impression, take a look at some of the homework problems that were used in previous versions of this course: [CDM Assignments](https://www.cs.cmu.edu/~sutner/CDM/notes/hw-master-nosol.pdf). A few pictures can be found here: [CDM Gallery](https://www.cs.cmu.edu/~sutner/CDM/bilder.html) (challenge: figure out what these pictures mean, for as many as you can manage). A slightly dated paper outlining the course philosophy can be found at [Jeric](http://www.cs.cmu.edu/~sutner/papers/JERIC05.pdf).

Needless to say, a solid background in discrete math is necessary for this course. You should feel very much at home with all the 15-251 material.   

15-354 Computation & Discrete Math

The math foundations of Computer Science are the fundamental skills to understand advanced fields in Computer Science, and also the key to more advanced topics such as [*Theoretical Computer Science*](/topic/theoretical-computer-science). It includes a range of topics such as Discrete Mathematics, Probability Theory, Combinatorics etc. 

Mathematical Foundations

Computer Science

Mathematical Foundations

Prerequisites

Common concepts