Overview

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.

Syllabus

Introduction to Discrete Math for Computer Science (Algorithms & Recursions)

This module explores number theory (GCD, modular arithmetic), cryptography basics, mathematical induction, recurrence relations, and algorithm correctness. Students learn to prove properties of recursive and iterative solutions and understand secure systems like RSA encryption. It equips learners to design, verify, and analyze efficient, secure computational processes in software, cybersecurity, and advanced computing.

Modular Arithmetic

Modular arithmetic studies arithmetic operations under remainders and divisibility. This topic introduces divisibility, congruences, and modular computations, which simplify calculations with large numbers and form the basis of many algorithms in computer science, including hashing, cryptography, and error detection.

Greatest Common Divisor

This topic explores greatest common divisors (GCDs), the Euclidean algorithm, and their applications. It also introduces multiplicative inverses, linear congruences, and the Chinese Remainder Theorem, which are fundamental tools for solving number-theoretic problems efficiently in algorithms and cryptography.

Cryptography

This topic introduces cryptography as the study of secure communication over insecure channels. It covers secret-key cryptography, classical ciphers, key exchange problems, and public-key cryptography concepts, illustrating how number theory and modular arithmetic enable secure data transmission in modern systems.

Algorithms

This topic studies how to evaluate algorithm efficiency by analyzing running time and growth rates. It introduces asymptotic notation, such as Big-Theta, and applies these concepts to compare algorithms, emphasizing performance for large inputs rather than exact execution details.

Induction

Mathematical induction is a proof technique used to establish the truth of infinitely many statements. This topic introduces the principle of induction, its variants, and applications to proving formulas, inequalities, and properties of recursively defined structures common in mathematics and computer science.

Recursion

Recursion defines objects and processes in terms of themselves. This topic introduces recursive definitions, recursive algorithms, and techniques for reasoning about their correctness and efficiency.