/
Programming › Design of Algorithms
← Back to Home
Programming · Module 02

Design of
Algorithms

From divide & conquer to approximation algorithms — the curriculum covering randomised algorithms, network flow, linear programming, NP-completeness, and the theoretical toolkit for hard problems.

13+
Chapters
52+
Practice Problems
2
Languages
₹0
Cost
Inspired by MIT 6.046J · Design and Analysis of Algorithms · Spring 2015
Implementations in Python 3 C++17 — toggle between languages inside each chapter
What you will learn
🎲
Randomised Algorithms
Expected-time and with-high-probability analysis. Randomised Quicksort, skip lists, hashing — algorithms that use randomness to beat deterministic lower bounds.
🌊
Network Flow & LP
Max-flow min-cut theorem, Ford-Fulkerson, Edmonds-Karp. Linear programming duality, simplex method — how continuous optimisation underlies discrete algorithms.
📐
Hardness & Approximation
NP-completeness, reductions, why some problems resist polynomial algorithms — and approximation algorithms and FPT techniques for surviving NP-hard problems in practice.
⚠️
Prerequisites. You should be comfortable with asymptotic notation, graph algorithms (BFS/DFS/Dijkstra/Bellman-Ford), dynamic programming (SRT BOT), and basic complexity (P vs NP). If you have not completed Introduction to Algorithm, start there first →
Chapters 13 chapters · Python + C++
01
Divide & Conquer + Master Theorem
Interval scheduling, convex hull, Strassen matrix multiplication, median finding. Recurrence solving via substitution, recursion trees, and the Master Theorem.
Foundational ● Live 4 MCQ
→
02
Fast Fourier Transform
Polynomial representations, DFT, nth roots of unity, FFT algorithm, IFFT. O(n log n) polynomial multiplication from O(n²) — the algorithm that changed signal processing.
Foundational ● Live 4 MCQ
→
03
Advanced Data Structures I — vEB and Skip Lists
van Emde Boas trees for O(log log u) successor/predecessor. Skip lists with randomised level promotion, with-high-probability O(log n) search.
Intermediate ● Live 4 MCQ
→
04
Hashing, Augmentation and B-Trees
Universal and perfect hashing. Order-statistics trees, range trees, orthogonal range search. 2-3 trees and B-trees for external memory — why databases use them.
Intermediate ● Live 4 MCQ
→
05
Amortization and Union-Find
Aggregate, accounting, and potential methods. Union-Find with union-by-rank and path compression. The inverse Ackermann function α(n) — nearly constant in practice.
Intermediate ● Live 4 MCQ
→
06
Randomized Algorithms
Matrix multiplication verification. Randomised Quicksort and Select — expected O(n log n) and O(n). Las Vegas vs Monte Carlo. Paranoid analysis and Chernoff bounds.
Intermediate ● Live 4 MCQ
→
07
Advanced Dynamic Programming
Longest palindromic subsequence, optimal BST, alternating coin game. Boolean expression parenthesisation. Rectangular blocks — DP on partial orders.
Intermediate ● Live 4 MCQ
→
08
All-Pairs Shortest Paths, Greedy and MST
Matrix multiplication APSP, Johnson's algorithm. Greedy choice and optimal substructure. Prim's and Kruskal's MST algorithms — and the exchange argument proof technique.
Intermediate ● Live 4 MCQ
→
09
Network Flow
Flow networks, max-flow min-cut theorem. Ford-Fulkerson, Edmonds-Karp O(VE²). Bipartite matching, vertex cover, baseball elimination — flow as a modelling language.
Advanced ● Live 4 MCQ
→
10
Linear Programming
LP formulation, geometric intuition, standard form. Strong duality, complementary slackness. Simplex method. Max-flow as LP — connecting continuous and combinatorial optimisation.
Advanced ● Live 4 MCQ
→
11
NP-Completeness and Approximation Algorithms
3SAT, circuit SAT, reduction chains. Vertex cover 2-approximation, set cover O(log n). Metric TSP 2-approximation and Christofides ⅔-approximation.
Complexity ● Live 4 MCQ
→
12
Fixed-Parameter Algorithms and Distributed Computing
FPT algorithms, kernelisation for vertex cover. Synchronous and asynchronous distributed models, BFS spanning trees, Luby's MIS, leader election.
Advanced ● Live 4 MCQ
→
13
Cryptography and Cache-Oblivious Algorithms
RSA encryption, digital signatures, MACs, Merkle trees. Cache-oblivious model, van Emde Boas layout, cache-oblivious sorting — algorithms that work without knowing the cache size.
Advanced ● Live 4 MCQ
→