Overview

This course develops the mathematical tools needed to count, measure uncertainty, and reason about random processes, which are central to computer science, data analysis, and algorithm design. Building on the logical foundations from the first course, it introduces combinatorial counting techniques and probability theory through a discrete, computation-oriented lens. The course begins with the fundamentals of counting, including the product rule, sum rule, permutations, combinations, and binomial coefficients. You will learn how to count complex structures efficiently using techniques such as the principle of inclusion and exclusion, with applications ranging from algorithm analysis to data organization. The second half of the course focuses on probability, emphasizing its deep connection to counting. Topics include sample spaces, events, conditional probability, independence, and Bayes’ Theorem. You will also study random variables, probability distributions, expectation, and variance, gaining tools to model and analyze randomized algorithms and real-world uncertainty. Throughout the course, abstract concepts are reinforced with concrete examples drawn from computing, games of chance, and classic probability puzzles. By the end, learners will be able to systematically count possibilities, compute probabilities, and reason rigorously about randomness—skills essential for advanced study in algorithms, data science, machine learning, and beyond.

Syllabus

Introduction to Discrete Math for Computer Science (Counting & Probability)

This module teaches how to count arrangements, selections, and possibilities using permutations, combinations, binomial coefficients, and inclusion-exclusion. It covers probability fundamentals, conditional probability, random variables, and iconic problems like the Monty Hall dilemma to handle uncertainty. These tools are crucial for analyzing algorithm efficiency, game design, randomized systems, machine learning, and risk assessment.

Basics of Counting

Counting techniques provide systematic methods for determining the number of possible outcomes in discrete structures. This topic introduces basic counting principles such as the sum rule and product rule.

Permutations and Combinations

This topic studies methods for counting arrangements and selections of objects. It distinguishes between ordered and unordered selections and introduces formulas for permutations and combinations.

Binomial Coefficients

Binomial coefficients arise in counting combinations and in the expansion of binomial expressions. This topic covers the binomial theorem, Pascal’s identity, and important combinatorial identities.

The Inclusion-Exclusion Principle

The inclusion–exclusion principle provides a systematic way to count elements in overlapping sets. It is widely used in counting problems involving unions of multiple sets.

Introduction to Probability

This topic introduces probability as a measure of uncertainty based on counting outcomes. It defines experiments, sample spaces, events, and basic probability rules.

Conditional Probability and Bayes' Theorem

Conditional probability measures the likelihood of events given prior information. This topic introduces independence and Bayes’ theorem, enabling probabilistic reasoning in real-world decision making.

Random Variables

Random variables assign numerical values to outcomes of random experiments. This topic covers discrete and continuous distributions, expectation, and variance, forming the foundation of probability modeling.