DAA
Design and Analysis of Algorithms
Analyse and design efficient algorithms: asymptotic analysis, recurrences, divide and conquer, greedy methods, dynamic programming, backtracking, graph algorithms and NP-completeness.
0%complete
- Lessons
- 21
- Runnable examples
- 41
- Quiz questions
- 84
- Visualizers
- 4
What you will be able to do
- Analyse running time with O, Ω and Θ
- Solve recurrences with the Master Theorem
- Design divide-and-conquer and greedy algorithms
- Solve problems with dynamic programming tables
- Use backtracking and branch and bound
- Explain P, NP, NP-complete and NP-hard
Syllabus
Unit 1Analysis of Algorithms
- 1What Is an Algorithm?The definition and five properties of an algorithm, how to write pseudocode, proving correctness with loop invariants, and the RAM model used to analyse running time.
- 2Asymptotic NotationsThe formal definitions of O, Ω and Θ (plus little-o and little-ω), proving bounds by finding c and n₀, the order of growth, and the properties exams test.
- 3Analysing Loops & Recursive CodeTurn code into running times: independent and dependent nested loops, logarithmic loops, writing recurrences for recursive functions, and an introduction to amortised analysis.
- 4Solving Recurrences & the Master TheoremSolve recurrences with the substitution method, recursion trees and the Master Theorem — with its three cases, worked examples, and the cases it cannot handle.
Unit 2Divide and Conquer
- 5Divide and ConquerThe divide, conquer, combine paradigm with full analysis of binary search, merge sort and quick sort, including quick sort's worst case and randomised pivots.
- 6More Divide and ConquerMax–min with fewer comparisons, counting inversions with merge sort, Karatsuba's fast multiplication and Strassen's matrix multiplication.
Unit 3Greedy Algorithms
- 7The Greedy MethodMake the locally best choice at every step: the greedy-choice property, activity selection, fractional knapsack, job sequencing with deadlines, and when greedy fails.
- 8Huffman CodingOptimal prefix-free codes for data compression: why prefix codes, building the Huffman tree with a min-priority queue, reading off codes, and computing the compressed size.
- 9Minimum Spanning TreesConnect every vertex at minimum total cost: spanning trees, Kruskal's algorithm with union-find, Prim's algorithm with a priority queue, traced on the same graph.
- 10Shortest Paths: Dijkstra & Bellman–FordSingle-source shortest paths in weighted graphs: relaxation, Dijkstra's greedy algorithm with a priority queue, why it fails on negative edges, and Bellman–Ford with negative-cycle detection.
Unit 4Dynamic Programming
- 11Dynamic ProgrammingSolve each subproblem once: overlapping subproblems and optimal substructure, memoisation vs tabulation, and DP solutions for Fibonacci and coin change.
- 120/1 KnapsackChoose whole items to maximise value within a weight limit: the DP table, the recurrence, tracing back the chosen items, and a space-optimised version.
- 13Longest Common SubsequenceFind the longest sequence common to two strings: subsequences vs substrings, the LCS table and recurrence, traceback, and the related edit-distance problem.
- 14Matrix Chain MultiplicationFind the cheapest way to parenthesise a product of matrices: why order matters, the m[i][j] recurrence, filling the table by chain length, and printing the optimal parenthesisation.
- 15All-Pairs Shortest Paths: Floyd–WarshallShortest distances between every pair of vertices with a three-loop DP, its recurrence over intermediate vertices, negative-cycle detection, and Warshall's transitive closure.
Unit 5Search, Graphs & Complexity
- 16BacktrackingExplore a state-space tree and abandon dead ends early: the N-Queens problem, subset sum, graph colouring and Hamiltonian cycles.
- 17Branch and BoundOptimisation by bounding: FIFO, LIFO and least-cost branch and bound, solving 0/1 knapsack with an upper bound, and the travelling salesperson problem.
- 18Topological Sort & ConnectivityOrder tasks with dependencies using Kahn's algorithm and DFS, find connected and strongly connected components, and detect cycles in directed graphs.
- 19String MatchingFind a pattern in a text: the naive algorithm, Rabin–Karp's rolling hash, and the Knuth–Morris–Pratt algorithm with its prefix function — with complexities.
- 20P, NP, NP-Complete & NP-HardTractable and intractable problems: decision problems, the classes P and NP, polynomial-time reductions, NP-complete and NP-hard problems, Cook's theorem, and coping with hardness.
- 21Algorithms Cheat SheetDesign and Analysis of Algorithms on one page: notations, recurrences, the Master Theorem, every algorithm's complexity, technique selection and exam favourites.