- 8
- Units
- 35
- Lessons
- 6/6
- Labs
Design algorithms with confidence: divide and conquer, greedy, dynamic programming, graph algorithms and NP-completeness.
What you'll learn
The key areas this subject covers, mapped to the official curriculum.
- Asymptotic analysis and recurrences
- Divide and conquer strategies
- Greedy and dynamic programming design
- Graph, backtracking and number-theoretic algorithms
- NP-completeness and problem complexity
Course units
The structured path through this subject.
- 1
Foundation of Algorithm Analysis
What an algorithm is, how to measure its efficiency with asymptotic notation, and how to solve the recurrences that describe recursive algorithms.
4 topics · 4 lessons available
- 2
Iterative Algorithms
Loop-based algorithms, the loop invariants that make them correct, and the summation techniques used to analyse them.
4 topics · 4 lessons available
- 3
Divide and Conquer Algorithms
Breaking problems into independent subproblems: the paradigm, classic examples, and the master method for their analysis.
5 topics · 5 lessons available
- 4
Greedy Algorithms
Making the locally best choice at each step: the greedy method and problems where it is provably optimal.
5 topics · 5 lessons available
- 5
Dynamic Programming
Storing and reusing solutions to overlapping subproblems: the principle, the classic problems, and the greedy-versus-DP divide.
5 topics · 5 lessons available
- 6
Backtracking
Systematic search through a state-space tree with pruning: backtracking and its branch-and-bound refinement.
4 topics · 4 lessons available
- 7
Number Theoretic Algorithms
The mathematics under cryptography: divisibility, GCD, modular arithmetic, primality testing and RSA.
4 topics · 4 lessons available
- 8
NP Completeness
Separating easy from hard problems: the classes P and NP, polynomial reductions, and what to do with NP-complete problems.
4 topics · 4 lessons available
Subject details
- Code
- CSC-325
- Credit hours
- 3
- Semester
- Semester V
- Category
- programming