Principles of Discrete Applied Mathematics

This lecture introduces the pigeonhole principle, demonstrating its applications and briefly covering foundational concepts in probability and sample spaces within discrete mathematics.

This session elaborates on event independence, conditional probability, Bayes' rule, random variables, and the crucial concept of linearity of expectation in probabilistic analysis.

The lecture explains and proves the principle of inclusion-exclusion, applying it to the hat check problem and discussing the coupon collector's problem and independence of random variables.

This lecture explores combinatorial counting techniques, focusing on binomial coefficients, bijections, and dual counting methods, demonstrating how Catalan numbers enumerate Dyck paths and various tree structures.

The Cayley tree theorem is proved through double counting. The lecture then introduces generating functions, detailing their basic structure and methods for combination, such as addition and multiplication.

This lecture demonstrates the application of generating functions to solve linear recurrence equations, deriving an expression for Fibonacci numbers, and introduces two-variable generating functions.

This lecture focuses on deriving the generating function for Catalan numbers and subsequently using it to obtain their explicit formula, a key result in combinatorial mathematics.

The lecture covers tail bounds, specifically Markov's and Chebyshev's inequalities, to estimate the probability of a random variable deviating from its mean, proving the weak law of large numbers.

This lecture introduces and proves Chernoff's theorem, a powerful tail bound for sums of independent random variables, offering tighter estimations than previous bounds.

This lecture covers modular arithmetic, including finding modular inverses using the Euclidean algorithm, the extended Euclidean algorithm, and applying the Chinese Remainder Theorem.

This lecture introduces fundamental concepts of group theory, defining groups, subgroups, and cosets, and culminates in the proof of Lagrange's theorem and its application to Fermat's Little Theorem.

This lecture introduces linear programs, illustrates with diet and bake sale examples, defines standard and canonical forms, and provides an initial discussion of dual linear programs.

This lecture extends duality theory to arbitrary linear programs, introduces complementary slackness, offers a physics-inspired proof of strong duality, and uses it to prove Koenig's theorem.

The lecture introduces zero-sum games, defining payoff matrices and illustrating with examples like matching pennies, concluding with an explanation of the Nash equilibrium concept.

This lecture explains the maximum flow problem, demonstrating that max-flow is bounded by min-cut, and proves their equality by formulating the max-flow as a linear program and taking its dual.

Beginning with data compression history, this lecture defines first-order sources and entropy, then states and proves Shannon's noiseless coding theorem for optimal compression ratios.

Reviewing Shannon's theorem, this lecture introduces prefix-free codes and their binary tree decoding, then details Huffman's algorithm for constructing optimal prefix-free codes.

This lecture explores reliable information transmission over noisy channels, beginning with repetition codes, and proves Shannon's noisy coding theorem for the binary symmetric channel.

This lecture demonstrates error correction in noisy channels through Hamming codes, detailing the 7-bit Hamming code's operation, defining linear codes, and discussing general Hamming codes.

This lecture introduces Reed-Solomon codes, explaining their polynomial construction, how the fundamental theorem of algebra determines their minimum distance, and methods for decoding.