Probabilistic Method

Basic Counting

Generating Functions

Some Extremal Problems

Linear-Algebraic-Methods

The Pigeon Hole Principle

Ramsey Theory

Partially Ordered Sets

Flows in Networks

Combinatorial Games

Polya Theory of Counting

Matroids

Recurrence relation

21-301 Combinatorics Carnegie Mellon University Fall 2021 This course provides a comprehensive introduction to Discrete Mathematics, emphasizing the application of these concepts in Computer Science. Topics include counting, recurrence relations, combinatorial games, Polya theory, and more.  The aim of this course is to introduce the student to some of the most important ideas in Discrete Mathematics. A subsidiary goal is to show how these ideas can be used to solve problems in Computer Science. This course delves into key concepts in Discrete Mathematics and demonstrates their applications in Computer Science problem-solving. The subject matter spans basic counting, recurrence relations, and more advanced topics like combinatorial games and Polya theory of counting. 

21-301 Combinatorics

Mathematical Foundations

Monte Carlo method

Sample Complexity

Randomized Algorithms

Large Deviation Bounds

Packet Routing

Martingales

Rademacher complexity

Hashing

Markov Chains

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