Algorithms tutorial

Learn how to solve problems step by step, and how to tell a good algorithm from a slow one.

Course contents

Introduction to Algorithms — What an algorithm is, why programs need one, its five key features, how algorithms are grouped, deterministic and non-deterministic algorithms, correctness, efficiency and the design process.
Complexity Analysis — How to measure an algorithm by how its work grows: time and space complexity, Big-O, the common complexity classes, best, average and worst cases, and amortized analysis.
Recursion — What recursion is, how to think recursively, base and recursive cases, the call stack, tracing a recursive function, the five types of recursion, and recursion versus loops.
Constraints — How to read the limits in a problem: time and memory limits, space complexity, auxiliary space, in-place algorithms, time-space tradeoffs, and picking an algorithm from the constraints.

Linear Search — What searching is, how linear search checks items one by one, the iterative and recursive versions, its complexity, and when to use it.
Binary Search — How binary search halves a sorted list, the template and its common bugs, its complexity, lower and upper bound, first and last occurrence, and binary search on the answer.
Advanced Searching — Jump search, interpolation search and exponential search, how to search a collection whose size is unknown, how the searches compare, and how to choose one.

Quadratic Sorts — Bubble sort, selection sort and insertion sort, step by step, with the ideas of stable, in-place and adaptive sorting, their complexity, and how the three compare.
Merge Sort — How merge sort splits a list and merges sorted halves, its code, O(n log n) complexity, stability and memory use, top-down and bottom-up versions, and where it is used.
Quick Sort — How quicksort partitions around a pivot, how to choose the pivot, the Lomuto and Hoare partitions, its complexity, variants and uses, and how it compares with merge sort.
Advanced Sorting — Heap sort, the non-comparison sorts (counting, radix and bucket sort), stable sorting and comparators, and how to choose a sorting algorithm.

Two Pointers — How two index variables walk an array from both ends, in the same direction, or at two speeds, to solve pair, reverse, duplicate and cycle problems in one pass.
Sliding Window — How a window of neighbouring items slides along an array, the fixed and variable windows, how windows expand and shrink, common uses and why it runs in O(n) time.
Prefix Sums — How an array of running totals answers the sum of any range with one subtraction, plus difference arrays for range updates, 2D prefix sums for rectangles, common uses and optimizations.
Hashing Techniques — How to use hash maps and hash sets to solve problems: fast lookups, frequency maps, duplicate detection, counting pairs, grouping anagrams, and their complexity.
Binary Search Patterns — How to use binary search beyond sorted lists: searching on the answer, monotonic yes/no tests, shrinking the search space for peaks and rotated arrays, and the common problem types.
Bit Manipulation — How numbers are stored as bits, the bitwise operators, how to set, clear and toggle one bit, bit masks, XOR tricks, and uses like powers of two, counting bits and listing subsets.

Divide and Conquer — How divide and conquer splits a problem, solves the parts and combines their answers, how to write its recurrence, the Master Theorem, its complexity and its common uses.
Greedy Algorithms — How greedy algorithms build an answer from the best choice at each step, the greedy choice property and optimal substructure, common greedy problems, and when greedy works or fails.
Backtracking — How backtracking tries a choice, explores it and undoes it, the state space tree, pruning, common problems like subsets, permutations and N queens, and its complexity.

Dynamic Programming — How dynamic programming saves the answers to smaller problems, memoization and tabulation, state and transition design, the knapsack, sequence, grid and partition patterns, and how to save memory.

String Algorithms — String basics, then pattern matching with naive search, KMP and Rabin-Karp, the Z algorithm, suffix arrays and suffix trees, and where string algorithms are used.

Graph Algorithms — How to walk a graph with BFS and DFS, order tasks with topological sort, find cycles and connected parts, and spot the common graph problem patterns.
Graph Path & Tree Algorithms — How to find the cheapest routes in a weighted graph with Dijkstra, Bellman-Ford and Floyd-Warshall, and how to join every node at the lowest cost with Kruskal and Prim.
Advanced Graph Algorithms — How to find strongly connected components, bridges and cut vertices, shrink a graph to its condensation, walk Euler and Hamiltonian paths, and compute who can reach whom.

Advanced Algorithms — How maximum flow, convex hulls, randomized algorithms, meet in the middle and branch and bound work, and how to pick the right technique from the input size.