Discrete Mathematical Tools for Computer Science

This course focuses on the mathematical foundations behind algorithms, efficiency, and recursive problem solving, building on the logic and counting techniques developed in earlier courses. It introduces key ideas from number theory and shows how they naturally lead to efficient algorithms used throughout computer science. The course begins with modular arithmetic, divisibility, and greatest common divisors, leading to classic algorithms such as the Euclidean algorithm and its extended form. These concepts are then applied to practical problems in cryptography, including modular exponentiation, key exchange, and public-key encryption, illustrating how abstract mathematics enables secure communication. You will then study the analysis of algorithms, learning how to measure running time using asymptotic notation and compare algorithms based on their growth rates. The course emphasizes reasoning about performance rather than machine-dependent details. Finally, the course develops mathematical induction and recursion as powerful tools for defining, analyzing, and proving the correctness of algorithms. Topics include recursive definitions, recurrence relations, and structural induction, with classic examples such as Fibonacci numbers and recursive counting problems. By the end of the course, learners will be able to design recursive algorithms, analyze their efficiency, and understand the mathematical principles that make modern computation possible.

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.