Discrete Math for Computer Science - Algorithms & Recursion
Keep adding new skills with 10,000+ programs for $239 (usually $399). Save now.
Discrete Math for Computer Science - Algorithms & Recursion
This course is part of Discrete Mathematical Tools for Computer Science Specialization
Instructor: Kenneth Wai-Ting Leung
Included with
Ask Coursera
Recommended experience
Recommended experience
What you'll learn
Analyse algorithm efficiency using asymptotic growth and mathematical reasoning.
Apply number theory concepts to algorithms and basic cryptographic systems.
Design and reason about recursive algorithms using induction and recurrence relations.
Details to know
February 2026
6 assignments
See how employees at top companies are mastering in-demand skills
Build your subject-matter expertise
- Learn new concepts from industry experts
- Gain a foundational understanding of a subject or tool
- Develop job-relevant skills with hands-on projects
- Earn a shareable career certificate
There are 7 modules in this course
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 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.
What's included
1 reading
1 reading•Total 10 minutes
- Course introduction and overview•10 minutes
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.
What's included
17 videos1 reading1 assignment
17 videos•Total 72 minutes
- Modular Arithmetic Overview•5 minutes
- Number Theory & Intro•3 minutes
- Divisibility_Definition•2 minutes
- Divisibility_Properties of Divisibility•2 minutes
- (Optional) Divisibility_Example•1 minute
- Divisibility_Euclid’s Division Theorem_Proof of Existence•13 minutes
- Divisibility_Euclid’s Division Theorem_Proof of Uniqueness•8 minutes
- Modular Arithmetic_Lemma•3 minutes
- (Optional) Modular Arithmetic_Example•4 minutes
- Modular Arithmetic_Theorem1 & 2•5 minutes
- Modular Arithmetic_Modular Arithmetic on Zm•2 minutes
- Modular Arithmetic_Properties of Arithmetic Modulo m & Proof of Associativity•5 minutes
- Modular Arithmetic_Additive inverses and multiplicative inverses•5 minutes
- Congruences_Definition & Modular Arithmetic and Congruences•4 minutes
- Congruences_Theorem & Corollary•7 minutes
- Applications of Modular Arithmetic_Parity Bits•3 minutes
- Applications of Modular Arithmetic_Random Numbers & Pseudorandom Numbers•2 minutes
1 reading•Total 30 minutes
- Modular Arithmetic•30 minutes
1 assignment•Total 20 minutes
- Quiz 1•20 minutes
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.
What's included
18 videos1 reading1 assignment
18 videos•Total 77 minutes
- GCD Overview •4 minutes
- GCD_intro•2 minutes
- Review of Primary School Knowledge•2 minutes
- Greatest Common Divisor_Definition•3 minutes
- Greatest Common Divisor_Euclidean Algorithm_Lemma•6 minutes
- (Optional) Greatest Common Divisor_Euclidean Algorithm_Example•5 minutes
- Greatest Common Divisor_gcds as Linear Combinations•7 minutes
- Greatest Common Divisor_The Extended Euclidean Algorithm & Puzzle_Water Measuring•3 minutes
- Multiplicative Inverses_Definition & Theorem•4 minutes
- Multiplicative Inverses_Proof of uniqueness•3 minutes
- Multiplicative Inverses_Finding Inverses_Examples•1 minute
- Solving Linear Congruences_Corollary & Proof, Example•5 minutes
- Solving Linear Congruences_Revisiting the String Hash Function•1 minute
- Solving Linear Congruences_HKID Checksum_Single & Transposition Error•5 minutes
- The Chinese Remainder Theorem_Sun-Tsu’s Problem & Theorem•6 minutes
- The Chinese Remainder Theorem_Proof•10 minutes
- (Optional) The Chinese Remainder Theorem_Example•2 minutes
- (Optional) InclassEx•8 minutes
1 reading•Total 30 minutes
- GCD•30 minutes
1 assignment•Total 20 minutes
- Quiz 2•20 minutes
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.
What's included
18 videos1 reading1 assignment
18 videos•Total 101 minutes
- Cryptography Overview•5 minutes
- Secret Key Cryptography_Intro•1 minute
- Secret Key Cryptography_Caesar Cipher (Shift Cipher) & Example•5 minutes
- Secret Key Cryptography_Affine Ciphers•3 minutes
- Secret Key Cryptography_Block Ciphers•3 minutes
- Secret Key Cryptography_AES•1 minute
- Key Exchange_Problems with secret-key cryptography & The Key Exchange Puzzle•3 minutes
- Key Exchange_Modular exponentiation & A One-Way Function_Modular Exponentiation and Logarithm•13 minutes
- Key Exchange_Discrete Logarithm & Diffie-Hellman Key Exchange•8 minutes
- Key Exchange_Man-in-the-middle Attack•2 minutes
- Public Key Cryptography and RSA_Intro & Public Key Cryptography•5 minutes
- Public Key Cryptography and RSA_The RSA Cryptosystem•2 minutes
- Public Key Cryptography and RSA_Another one-way function_Multiplication and factoring•8 minutes
- Public Key Cryptography and RSA_Key Generator, RSA Encryption & Decryption, RSA in Use & Correctness•5 minutes
- Public Key Cryptography and RSA_Fermat Little Theorem_Lemma•6 minutes
- Public Key Cryptography and RSA_Fermat Little Theorem_Theorem, Corollary & Proof•8 minutes
- Public Key Cryptography and RSA_RSA Correctness_Proof•22 minutes
- (Optional) InclassEx•1 minute
1 reading•Total 30 minutes
- Cryptography•30 minutes
1 assignment•Total 20 minutes
- Quiz 3•20 minutes
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.
What's included
18 videos1 reading1 assignment
18 videos•Total 82 minutes
- Algorithms Overview•3 minutes
- Revisiting the Selection Sort Algorithm & How to Measure the Running Time•4 minutes
- Revisiting the Selection Sort Algorithm_Solution•6 minutes
- The Growth of Functions•2 minutes
- Big-Theta_Definition•3 minutes
- Big-Theta_Using Definition to Derive Big-Theta•2 minutes
- Big-Theta_Comparison of Algorithms•4 minutes
- Big-Theta_Examples1 & Solving Geometric Series•18 minutes
- (Optional) Big-Theta_Examples2•10 minutes
- (Optional) Big-Theta_Examples3•2 minutes
- Big-Theta_Limitation of Big-Theta•3 minutes
- Big-Oh & Big-Omega, Review•3 minutes
- Big-Theta, Big-Oh & Big-Omega_Examples•6 minutes
- (Optional) Analysis of Algorithms_Example_Insertion Sort•4 minutes
- Analysis of Algorithms_Worst-case Analysis•5 minutes
- (Optional) Analysis of Algorithms_Example_Linear Search•2 minutes
- (Optional) Analysis of Algorithms_Example_Binary Search•5 minutes
- (Optional) InclassEx•1 minute
1 reading•Total 10 minutes
- Algorithms•10 minutes
1 assignment•Total 20 minutes
- Quiz 4•20 minutes
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.
What's included
16 videos1 reading1 assignment
16 videos•Total 79 minutes
- Induction Overview•3 minutes
- Climbing an Infinite Ladder & Validity of Mathematical Induction•3 minutes
- Proving Summations_Example1 & The Good and Bad of Induction•8 minutes
- (Optional) Proving Summations_Example2•2 minutes
- (Optional) Proving Inequalities_Example1 & 2•3 minutes
- Proving Divisibility Results•3 minutes
- Number of Subsets of a Finite Set•8 minutes
- Odd Pie Fight Problem_Proof•10 minutes
- Tiling Checkerboards•10 minutes
- Euclid’s Division Theorem•6 minutes
- Variants of Induction•1 minute
- Strong Induction•3 minutes
- Fundamental Theorem of Arithmetic•4 minutes
- Two Piles of Matches Problem•5 minutes
- Mistakes in Proofs by Induction1•9 minutes
- Mistakes in Proofs by Induction2•2 minutes
1 reading•Total 10 minutes
- Induction•10 minutes
1 assignment•Total 20 minutes
- Quiz 5•20 minutes
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.
What's included
26 videos1 reading1 assignment
26 videos•Total 143 minutes
- Recursion Overview•4 minutes
- Recursively Defined Functions_From Induction to Recursion•3 minutes
- (Optional) Recursively Defined Functions_Example1•7 minutes
- (Optional) Recursively Defined Functions_Example2•9 minutes
- Recursively Defined Functions_Recurrences & Solving First-Order Linear Recurrence•10 minutes
- Recursively Defined Functions_Mortgage Calculation•3 minutes
- Recursively Defined Functions_Counting Rabbits•2 minutes
- Recursively Defined Functions_Fibonacci Numbers_Intro•2 minutes
- (Optional) Recursively Defined Functions_Fibonacci Numbers_Example1•10 minutes
- (Optional) Recursively Defined Functions_Fibonacci Numbers_Example2_Counting Bit Strings•5 minutes
- Recursively Defined Functions_Revisiting Euclid’s GCD Algorithm_Lemma•5 minutes
- Recursively Defined Functions_Revisiting Euclid’s GCD Algorithm_Proof of Lemma•9 minutes
- Other Recursively Definitions_Recursively Defined Sets•4 minutes
- Other Recursively Definitions_Full Binary Trees•3 minutes
- Structural Induction_Example1 & Proof, Structural Induction Framework•8 minutes
- Structural Induction_Example2_Full Binary Trees•14 minutes
- Structural Induction_More examples on recursive definition and structural induction & Example3•7 minutes
- Structural Induction_Strings•3 minutes
- Structural Induction_Balanced Parentheses•2 minutes
- Structural Induction_String Concatenation•5 minutes
- Structural Induction_Length of a String•1 minute
- (Optional) Structural Induction_Example4•2 minutes
- Recursive Algorithms_Recursive Algorithms, Euclid’s GCD Algorithm & Fibonacci Numbers•1 minute
- Recursive Algorithms_The Tower of Hanoi•7 minutes
- Recursive Algorithms_Summary•3 minutes
- (Optional) InclassEx•14 minutes
1 reading•Total 30 minutes
- Recursion•30 minutes
1 assignment•Total 20 minutes
- Quiz 6•20 minutes
Earn a career certificate
Add this credential to your LinkedIn profile, resume, or CV. Share it on social media and in your performance review.
Instructor
Explore more from Algorithms
- Status: Free TrialU
University of California San Diego
Course
- Status: Free TrialB
Birla Institute of Technology & Science, Pilani
Course
- Status: Free TrialT
The Hong Kong University of Science and Technology
Course
- Status: Free TrialT
The Hong Kong University of Science and Technology
Course
Why people choose Coursera for their career
Frequently asked questions
To access the course materials, assignments and to earn a Certificate, you will need to purchase the Certificate experience when you enroll in a course. You can try a Free Trial instead, or apply for Financial Aid. The course may offer 'Full Course, No Certificate' instead. This option lets you see all course materials, submit required assessments, and get a final grade. This also means that you will not be able to purchase a Certificate experience.
When you enroll in the course, you get access to all of the courses in the Specialization, and you earn a certificate when you complete the work. Your electronic Certificate will be added to your Accomplishments page - from there, you can print your Certificate or add it to your LinkedIn profile.
Yes. In select learning programs, you can apply for financial aid or a scholarship if you can’t afford the enrollment fee. If fin aid or scholarship is available for your learning program selection, you’ll find a link to apply on the description page.
More questions
Financial aid available,