$ ls ~/lessons
Lessons
> Sorting Algorithms9 lessons
Algorithms that put elements in order, from simple methods to divide and conquer.
- 01Bubble SortA simple algorithm that sorts by comparing neighbouring elements.
- 02Selection SortA sorting algorithm that finds the smallest element on each pass and moves it to the front.
- 03Insertion SortA sorting algorithm that inserts each element into its place in the sorted left part.
- 04Merge SortA divide-and-conquer algorithm that splits the array and merges the sorted halves.
- 05Quick SortA fast divide-and-conquer algorithm that partitions the array around a pivot.
- 06Heap SortTurns the array into a max-heap and keeps moving the maximum to the end; O(n log n) with no extra memory.
- 07Shell SortSpeeds up insertion sort by comparing far-apart elements first and shrinking the gap.
- 08Counting SortSorts without comparisons by counting how many of each value there are; linear time for small ranges.
- 09Radix SortSorts numbers by the ones, tens, hundreds digit in turn with stable passes.
> Data Structures14 lessons
Ways to store and organise data, and the operations each one is good or bad at.
- 01StackA data structure where the last element in is the first out (LIFO).
- 02QueueA data structure where the first element in is the first out (FIFO).
- 03Linked ListA data structure that stores elements as nodes connected by pointers.
- 04Hash TableA data structure that spreads keys into buckets with a hash function for average O(1) access.
- 05Binary Search Tree (BST)A tree that keeps smaller values left and larger ones right for fast search and sorted traversal.
- 06Heap (Priority Queue)A complete binary tree stored in an array that gives O(1) access to the smallest (or largest) element.
- 07GraphA data structure of nodes and edges, explored with BFS and DFS.
- 08DequeA double-ended queue with O(1) adds and removes at both the front and the back.
- 09TrieA tree that stores words letter by letter, shares common prefixes and answers prefix queries in word-length time.
- 10Union-FindSplits elements into sets, merges sets and tells whether two elements share a set in almost constant time.
- 11AVL TreeA binary search tree that keeps the left/right height difference at most 1 at every node, rebalancing itself with rotations.
- 12Red-Black TreeA balanced search tree that colours nodes red and black to keep its height O(log n); the tree behind TreeMap and std::map.
- 13Segment TreeA binary tree of range sums that answers range queries and single updates in O(log n).
- 14Fenwick Tree (BIT)A Binary Indexed Tree: prefix sums and updates in O(log n) in a single array, using the lowest set bit.
> Searching Algorithms5 lessons
Ways to find a value in data, from linear search to binary search.
- 01Linear SearchThe simplest search: check the elements one by one from start to end.
- 02Binary SearchA fast search that halves the range at every step in a sorted array.
- 03Jump SearchSearches a sorted array by jumping ahead in blocks of √n and scanning one block.
- 04Interpolation SearchLooks where the value should be rather than in the middle; very fast on evenly spread data.
- 05Exponential SearchDoubles a bound to find a range, then binary searches it; very fast for values near the start.
> Graph Algorithms8 lessons
Algorithms that traverse nodes and edges and find paths and connections.
- 01Breadth-First Search (BFS)Explores a graph layer by layer from the start and finds shortest paths in unweighted graphs.
- 02Depth-First Search (DFS)Follows a branch to its end and backtracks; the basis of cycle detection and topological sorting.
- 03Dijkstra's AlgorithmA greedy algorithm that finds the cheapest paths from a start node to every node in a graph with non-negative weights.
- 04Kruskal's AlgorithmFinds a minimum spanning tree by trying edges from lightest to heaviest and keeping those that don't close a cycle.
- 05Prim's AlgorithmGrows a minimum spanning tree from one node, adding the cheapest link to the tree at every step.
- 06Topological SortOrders a directed acyclic graph's nodes so every arrow points forward; the standard way to resolve dependencies.
- 07Bellman-Ford AlgorithmFinds shortest paths even with negative edge weights, and detects negative cycles.
- 08Floyd-Warshall AlgorithmComputes shortest paths between every pair of nodes in a distance matrix using dynamic programming.
> Dynamic Programming6 lessons
Splitting a problem into overlapping subproblems and solving each once: memoization and tables.
- 01Fibonacci and MemoizationFrom recursion that solves the same subproblems over and over to memoization and tables that compute each value once.
- 020/1 KnapsackA DP table that decides to take or leave each item to fit the highest total value into a knapsack of limited capacity.
- 03Longest Common Subsequence (LCS)Finds the longest subsequence two sequences share in order using a DP table; the basis of diff and DNA alignment.
- 04Edit DistanceThe Levenshtein algorithm: the fewest letter replacements, deletions and insertions that turn one word into another.
- 05Coin ChangeFinds the fewest coins for an amount with DP, and shows when the greedy approach goes wrong.
- 06Longest Increasing Subsequence (LIS)Finds the longest strictly increasing subsequence of a sequence with O(n²) DP, with a look at the O(n log n) version.
> Backtracking4 lessons
Searching by building a solution step by step and undoing the last choice at dead ends: placements, subsets and orderings.
- 01N-QueensThe classic backtracking problem: place n queens so none attacks another, backing up at dead ends.
- 02Generating SubsetsThe backtracking pattern that generates all 2ⁿ subsets with a take/leave choice for each element.
- 03Generating PermutationsBacktracking that generates all n! orderings by choosing an unused element for each position and undoing it on return.
- 04Sudoku SolverThe most familiar example of backtracking: try digits in empty cells and back up when a rule breaks.
> String Algorithms3 lessons
Ways to find a pattern in text: from naive search to prefix tables and rolling hashes.
- 01Naive String SearchThe simplest string search: place the pattern at every position of the text and compare letter by letter.
- 02KMP AlgorithmKnuth-Morris-Pratt: uses the pattern's prefix table to search in O(n + m) without ever moving back in the text.
- 03Rabin-Karp AlgorithmString search that compares the hashes of the pattern and a sliding window, checking letters only when the hashes match.
> Greedy Algorithms3 lessons
Algorithms that make the choice that looks best right now: when they are right and when they mislead.
- 01Activity SelectionThe classic greedy algorithm that picks the most non-overlapping activities by taking the one that ends first.
- 02Fractional KnapsackA greedy algorithm that fills the knapsack by value per unit of weight when items can be split, giving the best result.
- 03Huffman CodingGreedy compression that gives frequent letters short codes by repeatedly merging the two lightest trees.