{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Grokking Algorithms \u2014 Graph Algorithms\n", "\n", "Hands-on companion to the **Graph algorithms**, **Paradigms**, and\n", "**ML** sections of [grokking_algorithms.html](grokking_algorithms.html).\n", "\n", "Every code cell is preceded by a **\ud83d\udc0d Python in this cell** note and\n", "has per-line comments inside.\n", "\n", "**Covered in this notebook:**\n", "1. Breadth-first search (BFS)\n", "2. Dijkstra's algorithm\n", "3. A* search\n", "4. Greedy \u2014 set cover\n", "5. Dynamic programming \u2014 Fibonacci with memoization\n", "6. k-Nearest Neighbours" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1. Breadth-first search\n", "\n", "BFS explores a graph in layers \u2014 friends, then friends-of-friends.\n", "A **queue** (FIFO) drives the order. Finds the shortest path (in\n", "edges) on an unweighted graph." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **Python in this cell:** `from collections import deque` imports `deque` \u2014 a double-ended queue with O(1) append and popleft. `deque([start])` creates a deque containing one element. `{start}` is a one-element set. `set` membership (`x in seen`) is O(1) average \u2014 perfect for tracking visited nodes. A `dict` of `key \u2192 list` is one way to represent a graph." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from collections import deque\n", "\n", "graph = { # adjacency list: name \u2192 list of friends\n", " \"you\": [\"alice\", \"bob\", \"claire\"],\n", " \"alice\": [\"dave\"],\n", " \"bob\": [\"eve\"],\n", " \"claire\": [\"frank\"],\n", " \"dave\": [], \"eve\": [], \"frank\": [],\n", "}\n", "\n", "def bfs(start, target):\n", " queue = deque([start]) # start the search at one node\n", " seen = {start} # nodes we've already added to the queue\n", " while queue: # keep going while there's anything to visit\n", " node = queue.popleft() # pull from the FRONT \u2014 that's BFS\n", " if node == target:\n", " return True\n", " for neighbour in graph[node]:\n", " if neighbour not in seen:\n", " seen.add(neighbour)\n", " queue.append(neighbour) # enqueue at the BACK\n", " return False # exhausted reachable nodes \u2014 not found\n", "\n", "print(\"Find frank:\", bfs(\"you\", \"frank\"))\n", "print(\"Find ghost:\", bfs(\"you\", \"ghost\"))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### BFS that also returns the path\n", "\n", "Track each node's parent so we can rebuild the path when found." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **Python in this cell:** `parent = {start: None}` doubles as 'seen' (a key being present means we've enqueued the node) and as the parent map. `path[::-1]` is slicing with step -1, which reverses a list." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def bfs_path(start, target):\n", " queue = deque([start])\n", " parent = {start: None} # node \u2192 who enqueued it (None for start)\n", " while queue:\n", " node = queue.popleft()\n", " if node == target:\n", " # walk back from target to start using parent links\n", " path = []\n", " while node is not None:\n", " path.append(node)\n", " node = parent[node]\n", " return path[::-1] # reverse so it reads start \u2192 target\n", " for neighbour in graph[node]:\n", " if neighbour not in parent:\n", " parent[neighbour] = node # remember who got us here\n", " queue.append(neighbour)\n", " return None # no path exists\n", "\n", "print(\"Path to frank:\", bfs_path(\"you\", \"frank\"))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Try this \u2014 DFS by swapping one line.** Replace `queue.popleft()` with\n", "`queue.pop()` (which takes from the *end*). BFS becomes DFS." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 2. Dijkstra's algorithm\n", "\n", "When edges have weights, BFS no longer gives the cheapest path.\n", "Dijkstra replaces the BFS queue with a **priority queue** ordered by\n", "total cost." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **Python in this cell:** `float(\"inf\")` is a sentinel for 'no path known yet' \u2014 anything is smaller. A dict comprehension `{k: v for k in iterable}` builds a dict. `(distance, node)` tuples are pushed onto the heap so it orders by distance first. `dict.items()` yields `(key, value)` pairs to iterate." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import heapq\n", "\n", "def dijkstra(graph, source):\n", " distances = {node: float(\"inf\") for node in graph} # all start at \"unknown\"\n", " distances[source] = 0\n", " pq = [(0, source)] # heap of (distance, node)\n", "\n", " while pq:\n", " d, u = heapq.heappop(pq) # cheapest unvisited node\n", " if d > distances[u]:\n", " continue # stale entry \u2014 already found cheaper, skip\n", " for v, weight in graph[u].items():\n", " alt = d + weight # cost to reach v through u\n", " if alt < distances[v]:\n", " distances[v] = alt # update with new shorter distance\n", " heapq.heappush(pq, (alt, v))\n", " return distances\n", "\n", "# Small weighted graph: dict of dicts.\n", "graph = {\n", " \"start\": {\"a\": 6, \"b\": 2},\n", " \"a\": {\"end\": 1},\n", " \"b\": {\"a\": 3, \"end\": 5},\n", " \"end\": {},\n", "}\n", "print(dijkstra(graph, \"start\"))\n", "# cheapest start \u2192 end is 6: start \u2192 b (2) \u2192 a (3) \u2192 end (1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Try this:** raise `start \u2192 b` from 2 to 10. The cheapest path\n", "changes \u2014 Dijkstra routes through `a` instead. Edit and re-run." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 3. A* search\n", "\n", "Dijkstra plus a heuristic. Where Dijkstra picks the node with smallest\n", "`g(n)` (cost-so-far), A* picks smallest `f(n) = g(n) + h(n)` (cost +\n", "estimated remaining)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **Python in this cell:** `abs(x)` returns the absolute value. Tuples like `(0, 0)` make great grid coordinates \u2014 they're hashable so they can sit in sets and dicts. `dict.get(key, default)` reads a value or returns `default` if the key is missing \u2014 useful when 'not yet seen' should mean 'infinite cost'. `_` is the conventional name for 'value I don't need'." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import heapq\n", "\n", "def manhattan(a, b):\n", " # Manhattan distance: sum of absolute differences in each coordinate\n", " return abs(a[0] - b[0]) + abs(a[1] - b[1])\n", "\n", "def a_star(start, goal, walkable):\n", " open_set = [(manhattan(start, goal), 0, start)] # heap of (f, g, node)\n", " best_g = {start: 0} # cheapest cost-so-far we've seen for each node\n", "\n", " while open_set:\n", " _, g, current = heapq.heappop(open_set) # smallest-f node\n", " if current == goal:\n", " return g # reached the goal \u2014 return total cost\n", " for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]: # try 4 directions\n", " nxt = (current[0] + dx, current[1] + dy)\n", " if nxt not in walkable:\n", " continue # blocked or off-grid\n", " tentative = g + 1 # assume each step costs 1\n", " if tentative < best_g.get(nxt, float(\"inf\")):\n", " best_g[nxt] = tentative # found a shorter path to nxt\n", " f = tentative + manhattan(nxt, goal)\n", " heapq.heappush(open_set, (f, tentative, nxt))\n", " return None # exhausted reachable cells \u2014 no path\n", "\n", "# 3\u00d73 grid with a wall at (0, 1)\n", "walkable = {(0,0), (1,0), (1,1), (1,2), (0,2)}\n", "print(\"Path cost:\", a_star((0,0), (0,2), walkable)) # 4" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Bigger grid \u2014 see A* avoid walls" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **Python in this cell:** Set comprehensions can have nested loops AND conditions, same syntax as list comprehensions. `range(7)` produces 0..6. The grid is just a set of (row, col) tuples representing the walkable cells." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def build_grid(width, height, walls):\n", " # Walkable = every (r, c) except those in walls.\n", " return {(r, c) for r in range(height) for c in range(width)\n", " if (r, c) not in walls}\n", "\n", "walls = {(r, 3) for r in range(6)} # wall along column 3, rows 0-5\n", "grid = build_grid(7, 7, walls)\n", "\n", "cost = a_star((0, 0), (6, 6), grid)\n", "print(f\"Cheapest path cost: {cost}\")\n", "\n", "# ASCII visualisation\n", "for r in range(7):\n", " row = \"\"\n", " for c in range(7):\n", " if (r, c) == (0, 0): row += \" S \"\n", " elif (r, c) == (6, 6): row += \" G \"\n", " elif (r, c) in walls: row += \" \u2593 \"\n", " else: row += \" . \"\n", " print(row)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 4. Greedy \u2014 Set Cover\n", "\n", "Take the locally best option at every step. Often gives a great\n", "approximation when finding the truly optimal answer would take forever." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **Python in this cell:** `{...}` (with elements, not key:value) is a set literal. `set1 & set2` is set **intersection** \u2014 elements in both. `set1 -= set2` removes every element of set2 from set1 in place. Iterating a dict yields its keys; `dict.items()` yields `(key, value)`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "states_needed = {\"mt\", \"wa\", \"or\", \"id\", \"nv\", \"ut\", \"ca\", \"az\"}\n", "stations = {\n", " \"kone\": {\"id\", \"nv\", \"ut\"},\n", " \"ktwo\": {\"wa\", \"id\", \"mt\"},\n", " \"kthree\": {\"or\", \"nv\", \"ca\"},\n", " \"kfour\": {\"nv\", \"ut\"},\n", " \"kfive\": {\"ca\", \"az\"},\n", "}\n", "\n", "def greedy_set_cover(universe, sets):\n", " still_needed = set(universe) # copy so we don't mutate caller's set\n", " chosen = []\n", " while still_needed:\n", " best_name, best_cover = None, set()\n", " for name, members in sets.items(): # try every set\n", " covered = still_needed & members # how many still-needed it covers\n", " if len(covered) > len(best_cover):\n", " best_name, best_cover = name, covered\n", " if not best_name:\n", " return None # impossible \u2014 no set covers anything new\n", " chosen.append(best_name)\n", " still_needed -= best_cover # remove the states we just covered\n", " return chosen\n", "\n", "print(greedy_set_cover(states_needed, stations))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Try this \u2014 when greedy fails.** Coin change with [1, 3, 4] cents:\n", "greedy takes 4+1+1 = 3 coins for 6\u00a2, but the optimal is 3+3 = 2 coins." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **Python in this cell:** `sorted(coins, reverse=True)` returns a new list sorted high-to-low. `while target >= c:` keeps taking the current coin while it still fits." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def greedy_coins(target, coins):\n", " coins = sorted(coins, reverse=True) # try biggest coins first\n", " chosen = []\n", " for c in coins:\n", " while target >= c: # use this coin as many times as it fits\n", " chosen.append(c)\n", " target -= c\n", " return chosen if target == 0 else None # None if no exact change possible\n", "\n", "print(\"Make 6 with [1,3,4]:\", greedy_coins(6, [1, 3, 4]))\n", "# greedy \u2192 4+1+1 (3 coins). Optimal is 3+3 (2 coins). Greedy fails here." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 5. Dynamic programming \u2014 Fibonacci\n", "\n", "Naive recursive Fibonacci is O(2\u207f) because it recomputes the same\n", "numbers exponentially often. Memoized Fibonacci is O(n)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **Python in this cell:** Two function definitions, two strategies. Default parameter `memo=None` avoids the mutable-default-argument pitfall (we make a fresh dict on the first call). `n in memo` tests dict key membership in O(1) average." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Naive \u2014 recomputes everything, exponentially slow.\n", "def fib_naive(n):\n", " if n < 2:\n", " return n # fib(0)=0, fib(1)=1\n", " return fib_naive(n - 1) + fib_naive(n - 2)\n", "\n", "# Memoized \u2014 remembers what it computed.\n", "def fib_memo(n, memo=None):\n", " if memo is None:\n", " memo = {} # fresh dict per top-level call\n", " if n < 2:\n", " return n\n", " if n in memo:\n", " return memo[n] # already computed \u2014 return cached value\n", " memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)\n", " return memo[n]\n", "\n", "print(\"fib_naive(30):\", fib_naive(30))\n", "print(\"fib_memo(50): \", fib_memo(50)) # naive would take forever for n=50" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Time the difference" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **Python in this cell:** Same `time.perf_counter()` idiom as before. We measure naive in ms (because it's slow) and memo in \u00b5s (because it's fast)." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import time\n", "\n", "for n in [20, 25, 30, 35]:\n", " t0 = time.perf_counter()\n", " fib_naive(n)\n", " naive_time = time.perf_counter() - t0\n", " t0 = time.perf_counter()\n", " fib_memo(n)\n", " memo_time = time.perf_counter() - t0\n", " print(f\"n={n:>3} naive: {naive_time*1000:>8.1f} ms memo: {memo_time*1e6:>6.1f} \u00b5s\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Python's one-line shortcut\n", "\n", "`@functools.cache` does the memoization for you \u2014 no manual dict." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **Python in this cell:** Decorators (`@cache` above a function) wrap the function. `@cache` remembers every (args \u2192 result) pair so repeat calls return the cached answer instantly." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from functools import cache\n", "\n", "@cache # decorator \u2014 wraps fib() with caching\n", "def fib(n):\n", " if n < 2:\n", " return n\n", " return fib(n - 1) + fib(n - 2)\n", "\n", "print(fib(100)) # huge number, instant" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 6. k-Nearest Neighbours\n", "\n", "Classify a new point by finding the k closest already-labelled points\n", "and letting them vote." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **Python in this cell:** `math.sqrt(x)` is square root. `zip(a, b)` pairs elements from a and b: `zip([1,2], [10,20])` \u2192 `[(1,10), (2,20)]`. `sum(generator)` adds up everything the generator yields. `sorted(seq, key=fn)` sorts using `fn(item)` as the sort key. `lambda x: x[0]` is a tiny anonymous function returning the first element. `Counter.most_common(1)[0][0]` extracts the most-frequent item." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import math\n", "from collections import Counter\n", "\n", "def knn_predict(train, new_point, k=3):\n", " distances = []\n", " for features, label in train:\n", " # Euclidean distance: sqrt(sum of squared differences)\n", " d = math.sqrt(sum((a - b) ** 2 for a, b in zip(features, new_point)))\n", " distances.append((d, label))\n", " distances.sort(key=lambda x: x[0]) # sort by distance (first element)\n", " k_labels = [label for _, label in distances[:k]] # labels of k nearest\n", " return Counter(k_labels).most_common(1)[0][0] # majority vote\n", "\n", "# Features: (weight grams, diameter cm)\n", "train = [\n", " ((150, 8), \"apple\"),\n", " ((170, 9), \"apple\"),\n", " ((140, 7), \"orange\"),\n", " ((130, 6), \"orange\"),\n", "]\n", "print(\"Mystery fruit (145, 7.5):\", knn_predict(train, (145, 7.5), k=3))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Try this \u2014 what does k change?** With k=1 only the closest point\n", "matters. With k=4 *all* points vote. Try several k values." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **Python in this cell:** Same `knn_predict()` as above \u2014 we're just calling it in a loop with different k values." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for k in [1, 2, 3, 4]:\n", " pred = knn_predict(train, (145, 7.5), k=k)\n", " print(f\"k={k}: {pred}\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Feature scaling \u2014 why it matters\n", "\n", "With weight in grams (150) but diameter in metres (0.08), the\n", "distance is dominated by weight \u2014 diameter contributes almost\n", "nothing. Normalize first." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **Python in this cell:** Z-score normalization: subtract the mean, divide by the standard deviation. We compute mean and std ourselves rather than importing numpy. `**` is exponentiation: `x ** 2` is x squared, `x ** 0.5` is square root." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Same fruits but diameter in METRES instead of cm \u2014 distance gets distorted.\n", "bad_train = [\n", " ((150, 0.08), \"apple\"),\n", " ((170, 0.09), \"apple\"),\n", " ((140, 0.07), \"orange\"),\n", " ((130, 0.06), \"orange\"),\n", "]\n", "# Mystery fruit at 145 g, 0.075 m\n", "print(\"With raw mixed units:\", knn_predict(bad_train, (145, 0.075), k=3))\n", "\n", "# Z-score normalize each feature independently.\n", "def zscore(values):\n", " mean = sum(values) / len(values)\n", " std = (sum((v - mean) ** 2 for v in values) / len(values)) ** 0.5\n", " return [(v - mean) / std for v in values], mean, std\n", "\n", "weights, w_mean, w_std = zscore([w for (w, _), _ in bad_train])\n", "diams, d_mean, d_std = zscore([d for (_, d), _ in bad_train])\n", "scaled_train = [((w, d), label) for (w, d), (_, label) in zip(zip(weights, diams), bad_train)]\n", "scaled_query = ((145 - w_mean) / w_std, (0.075 - d_mean) / d_std)\n", "\n", "print(\"With z-score normalization:\", knn_predict(scaled_train, scaled_query, k=3))" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python", "version": "3.x" } }, "nbformat": 4, "nbformat_minor": 5 }