Discrete Math for Computer Science - Algorithms & Recursion

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.