{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Grokking Algorithms \u2014 Foundations\n", "\n", "Hands-on companion to the **Foundations** and **Data Structures**\n", "sections of [grokking_algorithms.html](grokking_algorithms.html).\n", "\n", "Every code cell here is preceded by a short **\ud83d\udc0d Python in this cell**\n", "note \u2014 what new Python features the code uses \u2014 and every line inside\n", "the code has a comment. You should be able to understand any cell from\n", "the comments alone.\n", "\n", "**Covered in this notebook:**\n", "1. Big-O notation\n", "2. Recursion\n", "3. Hash tables\n", "4. Heaps & priority queues\n", "5. Binary search trees\n", "6. Union-Find" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1. Big-O notation\n", "\n", "Big-O describes how the number of steps an algorithm takes grows when\n", "the input grows. The cell below times two ways to check \"is x in this\n", "collection?\" as the collection grows from 1,000 to 1,000,000 items." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **Python in this cell:** `import time` brings in Python's timing tools. `time.perf_counter()` returns a high-resolution timer as a float (seconds since some arbitrary start). Subtract two readings to measure elapsed time. `list(range(n))` builds `[0, 1, 2, ..., n-1]`. `set(iterable)` builds a set \u2014 fast `in` membership testing. The `in` operator works on both, but `x in list` is O(n) and `x in set` is O(1) average. `f\"...\"` is an f-string: anything inside `{}` is replaced with that expression's value at run time." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import time # built-in timing tools\n", "\n", "sizes = [1_000, 10_000, 100_000, 1_000_000] # underscores improve readability; same as 1000, 10000, etc.\n", "\n", "for n in sizes:\n", " data_list = list(range(n)) # build a list [0, 1, 2, ..., n-1]\n", " data_set = set(data_list) # same elements, in a set\n", " target = n - 1 # worst case for linear search (last element)\n", "\n", " t0 = time.perf_counter() # mark the start time\n", " target in data_list # search the list \u2014 O(n)\n", " list_time = time.perf_counter() - t0 # elapsed seconds\n", "\n", " t0 = time.perf_counter()\n", " target in data_set # search the set \u2014 O(1) average\n", " set_time = time.perf_counter() - t0\n", "\n", " # f-string: {n:>9,} = n right-aligned in 9 spaces, with thousands commas\n", " print(f\"n = {n:>9,} list: {list_time*1e6:>8.1f} \u00b5s \"\n", " f\"set: {set_time*1e6:>6.1f} \u00b5s\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Try this:** change `target = n - 1` to `target = 0`. Linear-search\n", "times drop sharply \u2014 because the target is now at the front of the\n", "list and gets found immediately. Big-O usually means *worst case*;\n", "this experiment shows you the best case for comparison." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 2. Recursion\n", "\n", "A function that calls itself on a smaller version of the same problem.\n", "The classic example is **factorial**: `4! = 4 \u00d7 3 \u00d7 2 \u00d7 1 = 24`." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **Python in this cell:** `def name(parameter):` defines a function. `if condition:` runs the indented block only when the condition is True. `return value` ends the function and hands the value back to the caller. A function can call itself \u2014 that's recursion. `for i in range(6)` loops over `0, 1, 2, 3, 4, 5`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def factorial(n):\n", " if n <= 1: # base case \u2014 when to stop\n", " return 1 # 0! and 1! are both defined as 1\n", " return n * factorial(n - 1) # recursive case \u2014 n \u00d7 (n-1)!\n", "\n", "for n in range(6):\n", " print(f\"{n}! = {factorial(n)}\") # print factorials of 0 through 5" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Try this:** write a recursive `countdown(n)` function that prints\n", "n, n-1, n-2, ..., 1, then prints \"Go!\". Then write `sum_to(n)` \u2014\n", "it should add up 1 + 2 + ... + n." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **Python in this cell:** `pass` is a placeholder that does nothing \u2014 Python requires *something* inside a function body, and `pass` fills the slot while you think. Comments start with `#`. Lines starting with `#` are ignored by Python." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Your turn \u2014 fill these in.\n", "\n", "def countdown(n):\n", " # base case: when do you stop?\n", " # recursive case: print(n), then call countdown(n-1)\n", " pass # placeholder \u2014 replace with real code\n", "\n", "def sum_to(n):\n", " # base case: sum_to(0) should return 0\n", " # recursive case: n + sum_to(n - 1)\n", " pass # placeholder\n", "\n", "# Uncomment the lines below once you've filled in the functions above:\n", "# countdown(5)\n", "# print(sum_to(10)) # should print 55" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**What happens without a base case?** Try running this in a fresh cell.\n", "Python will eventually stop with `RecursionError` \u2014 each unfinished\n", "call sits on the call stack, and the stack is finite.\n", "\n", "```python\n", "def broken(n):\n", " return n * broken(n - 1) # no base case!\n", "\n", "# broken(5) # RecursionError after ~1000 calls\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 3. Hash tables\n", "\n", "Python's `dict` *is* a hash table. Give it a key, get a value back\n", "instantly. The \"instant\" part comes from running the key through a\n", "hash function that turns it into an array index." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **Python in this cell:** `{}` is an empty dictionary. `d[key] = value` adds or updates an entry. `d[key]` reads the value (raises `KeyError` if absent). `key in d` tests membership and returns `True` or `False`. `list(d.keys())` converts a view of dict keys into a real list." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "phone_book = {} # empty dict\n", "phone_book[\"alice\"] = \"081-234-5678\" # add an entry \u2014 key \"alice\", value the number\n", "phone_book[\"bob\"] = \"082-987-6543\" # another entry\n", "phone_book[\"zoe\"] = \"098-111-2222\" # a third\n", "\n", "print(phone_book[\"alice\"]) # look up alice's number \u2014 instant!\n", "print(\"bob\" in phone_book) # check membership \u2192 True\n", "print(list(phone_book.keys())) # all keys, as a list" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Counting things with a hash table\n", "\n", "One of the most common uses: count how often something appears." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **Python in this cell:** `from module import name` imports just one thing from a module. `Counter` is a subclass of `dict` specialised for counting. `some_string.split()` splits the string on whitespace into a list of words. `counter.most_common(n)` returns the n most-frequent items as a list of `(item, count)` tuples." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from collections import Counter # Counter \u2014 a counting dict\n", "\n", "sentence = \"the quick brown fox jumps over the lazy dog the fox is quick\"\n", "counts = Counter(sentence.split()) # split words and tally each\n", "print(counts) # full count of every word\n", "print(\"Most common 3:\", counts.most_common(3)) # top 3 by frequency" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Building a hash table from scratch\n", "\n", "To prove there's no magic \u2014 here's a minimal hash table with separate\n", "chaining (each slot holds a small list of (key, value) pairs)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **Python in this cell:** `class Name:` defines a class. `def __init__(self, ...)` is the constructor \u2014 it runs once when you create an instance. `self.attr` stores data on the instance. `[[] for _ in range(size)]` is a list comprehension creating `size` empty lists. `hash(x)` returns an integer hash for any hashable object. `%` is the modulo operator (remainder after division). `enumerate(seq)` yields `(index, value)` pairs as you iterate." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class HashMap:\n", " def __init__(self, size=8):\n", " self.size = size # how many slots (buckets)\n", " self.buckets = [[] for _ in range(size)] # one empty list per slot\n", "\n", " def put(self, key, value):\n", " idx = hash(key) % self.size # which slot this key belongs to\n", " bucket = self.buckets[idx] # the list at that slot\n", " for i, (k, _) in enumerate(bucket): # walk the slot's chain\n", " if k == key:\n", " bucket[i] = (key, value) # update existing entry\n", " return\n", " bucket.append((key, value)) # not found \u2192 append new entry\n", "\n", " def get(self, key):\n", " idx = hash(key) % self.size\n", " for k, v in self.buckets[idx]: # walk the chain at this slot\n", " if k == key:\n", " return v # found \u2014 return the value\n", " return None # key not in map\n", "\n", " def show(self):\n", " for i, bucket in enumerate(self.buckets):\n", " print(f\" slot {i}: {bucket}\")\n", "\n", "m = HashMap(size=4) # tiny size forces collisions\n", "for name in [\"alice\", \"bob\", \"claire\", \"dave\", \"eve\", \"frank\"]:\n", " m.put(name, len(name)) # store name \u2192 length-of-name\n", "\n", "print(\"Lookup 'claire':\", m.get(\"claire\"))\n", "print(\"Buckets:\")\n", "m.show() # see how names piled into 4 slots" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Try this:** count the unique words in a longer piece of text. Paste\n", "a paragraph from a book or news article, split on whitespace, use\n", "`Counter`. How many words appear only once?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 4. Heaps and priority queues\n", "\n", "A heap always keeps the smallest (or largest) element on top, with\n", "push/pop in O(log n) and peek in O(1). Python's `heapq` module is a\n", "**min-heap** stored as a flat list." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **Python in this cell:** `import heapq` brings in the heap functions. `heapq.heappush(heap, x)` inserts x while keeping the heap rule. `heapq.heappop(heap)` removes and returns the smallest element. The heap itself is just a Python list \u2014 the module operates on it in place." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import heapq # heap algorithms operating on plain lists\n", "\n", "heap = [] # an empty list IS a valid empty heap\n", "for x in [7, 3, 9, 1, 5]:\n", " heapq.heappush(heap, x) # push x in, maintain heap rule \u2014 O(log n)\n", "\n", "print(\"Heap (array form):\", heap) # not sorted! just heap-ordered\n", "print(\"Smallest:\", heap[0]) # root of the heap is always smallest\n", "print(\"Pop:\", heapq.heappop(heap)) # remove + return the smallest\n", "print(\"Pop:\", heapq.heappop(heap)) # \u2026and the next smallest\n", "print(\"Heap after two pops:\", heap)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **Python in this cell:** `heapq.heapify(L)` rearranges list `L` in place into a valid heap \u2014 this is O(n), faster than pushing items one at a time. List comprehensions like `[expr for _ in range(n)]` build a new list." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def heap_sort(items):\n", " h = list(items) # copy so we don't mutate caller's list\n", " heapq.heapify(h) # turn h into a heap in place \u2014 O(n)\n", " return [heapq.heappop(h) for _ in range(len(h))] # pop everything in order\n", "\n", "print(heap_sort([7, 3, 9, 1, 5, 2, 8, 4, 6]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Top-K with a heap\n", "\n", "A heap of fixed size K is the right structure for \"give me the K\n", "largest numbers in a stream\". Push everything; whenever the heap\n", "exceeds K, pop the smallest." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **Python in this cell:** `random.seed(0)` makes random output reproducible. `random.randint(a, b)` returns a random integer in `[a, b]` inclusive. `sorted(seq, reverse=True)` returns a new list sorted high-to-low." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import random\n", "\n", "def top_k_largest(stream, k):\n", " heap = [] # min-heap of \"current top-k\"\n", " for x in stream:\n", " heapq.heappush(heap, x) # always push\n", " if len(heap) > k:\n", " heapq.heappop(heap) # too many \u2014 drop smallest\n", " return sorted(heap, reverse=True) # return largest first\n", "\n", "random.seed(0) # reproducible random stream\n", "stream = [random.randint(1, 1000) for _ in range(50)]\n", "print(\"Top 5 largest:\", top_k_largest(stream, 5))\n", "print(\"Sanity check:\", sorted(stream, reverse=True)[:5])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Try this:** Python's `heapq` only does min-heaps. To use it as a\n", "max-heap, push `-x` and negate on pop. Write a function that returns\n", "the K *smallest* numbers in a stream (you'll want a max-heap)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 5. Binary search trees\n", "\n", "Every node follows one rule: everything in the left branch is smaller,\n", "everything in the right branch is bigger. Search, insert, and delete\n", "follow one path down the tree \u2014 O(log n) when balanced." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **Python in this cell:** `None` is Python's null/missing value \u2014 we use it for empty subtrees. `if root is None` tests for that. Functions can call themselves (recursion) to walk a tree. Default arguments like `out=None` are evaluated once at function-definition time, so the safe pattern for a mutable default is `if out is None: out = []` inside the function." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class Node:\n", " def __init__(self, key):\n", " self.key = key # value stored at this node\n", " self.left = None # left subtree (None means empty)\n", " self.right = None # right subtree\n", "\n", "def insert(root, key):\n", " if root is None:\n", " return Node(key) # empty spot \u2014 create node here\n", " if key < root.key:\n", " root.left = insert(root.left, key) # go left if smaller\n", " elif key > root.key:\n", " root.right = insert(root.right, key) # go right if bigger\n", " return root # equal \u2192 already in tree\n", "\n", "def search(root, key):\n", " if root is None or root.key == key:\n", " return root # not found (None) or found (the node)\n", " if key < root.key:\n", " return search(root.left, key) # smaller \u2192 recurse left\n", " return search(root.right, key) # bigger \u2192 recurse right\n", "\n", "def inorder(root, out=None):\n", " # In-order walk: left subtree, then node, then right subtree.\n", " # For a BST this visits keys in sorted order.\n", " if out is None:\n", " out = [] # safe default for mutable arg\n", " if root:\n", " inorder(root.left, out)\n", " out.append(root.key)\n", " inorder(root.right, out)\n", " return out\n", "\n", "root = None # start with an empty tree\n", "for k in [8, 3, 10, 1, 6, 14]:\n", " root = insert(root, k) # insert each key\n", "\n", "print(\"Search 6:\", search(root, 6) is not None) # True\n", "print(\"Search 7:\", search(root, 7) is not None) # False\n", "print(\"Inorder (should be sorted):\", inorder(root))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Try this:** insert `1, 2, 3, 4, 5, 6` *in that order* and call\n", "`inorder()`. Output is still sorted \u2014 but the tree itself is now a\n", "\"stick\" (every node has only a right child). Search becomes O(n).\n", "This is why production systems use self-balancing variants." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **Python in this cell:** Same `insert()` and `inorder()` as before. New here: `while node:` loops as long as `node` is truthy (i.e., not `None`). `node.right` follows the right pointer." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Adversarial insert order \u2014 tree degenerates into a linked list.\n", "bad_root = None\n", "for k in [1, 2, 3, 4, 5, 6]:\n", " bad_root = insert(bad_root, k)\n", "\n", "# Walk only the right chain to measure depth.\n", "depth = 0\n", "node = bad_root\n", "while node: # keep going while there's a node\n", " depth += 1\n", " node = node.right # follow right pointer\n", "print(f\"Tree depth: {depth} (a balanced tree of 6 nodes would be depth ~3)\")\n", "print(\"Inorder still works:\", inorder(bad_root))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 6. Union-Find (disjoint set)\n", "\n", "Track a collection of groups. `find(x)` says what group x is in;\n", "`union(x, y)` merges x's group with y's group. With path compression\n", "and union-by-rank, every operation is essentially O(1) in practice." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **Python in this cell:** `list(range(n))` here creates `[0, 1, 2, ..., n-1]` \u2014 every element starts as its own parent. `[0] * n` makes a list of n zeros. `a, b = b, a` swaps two variables in one line. Methods can call each other through `self.method(...)`. A function can return `True` or `False` to report success." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class UnionFind:\n", " def __init__(self, n):\n", " self.parent = list(range(n)) # initially each element is its own root\n", " self.rank = [0] * n # upper bound on tree height\n", "\n", " def find(self, x):\n", " # Walk up to the root, then flatten the path on the way back.\n", " if self.parent[x] != x:\n", " self.parent[x] = self.find(self.parent[x]) # path compression\n", " return self.parent[x]\n", "\n", " def union(self, x, y):\n", " rx, ry = self.find(x), self.find(y)\n", " if rx == ry:\n", " return False # already in same group\n", " # union by rank: attach shorter tree under taller tree\n", " if self.rank[rx] < self.rank[ry]:\n", " rx, ry = ry, rx # make rx the taller (or equal) root\n", " self.parent[ry] = rx # attach ry under rx\n", " if self.rank[rx] == self.rank[ry]:\n", " self.rank[rx] += 1 # heights equal \u2192 resulting tree is one taller\n", " return True\n", "\n", "uf = UnionFind(5) # 5 elements, all isolated\n", "uf.union(0, 1)\n", "uf.union(2, 3)\n", "uf.union(1, 2) # now 0,1,2,3 all in one group\n", "\n", "print(\"0 and 3 connected?\", uf.find(0) == uf.find(3)) # True\n", "print(\"0 and 4 connected?\", uf.find(0) == uf.find(4)) # False\n", "print(\"parent array:\", uf.parent) # see the flattened tree structure" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Try this \u2014 counting groups.** Use Union-Find to count separate\n", "friend circles given a list of friendships." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **Python in this cell:** `{expr for x in iterable}` is a set comprehension \u2014 like a list comprehension but builds a set (no duplicates). We use it to collect all distinct group roots." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def count_groups(num_people, friendships):\n", " uf = UnionFind(num_people)\n", " for a, b in friendships: # each friendship is a (person_a, person_b) pair\n", " uf.union(a, b) # merge their groups\n", " roots = {uf.find(i) for i in range(num_people)} # set of distinct group roots\n", " return len(roots)\n", "\n", "# 6 people (numbered 0..5), friendships listed as (a, b) pairs\n", "friendships = [(0, 1), (1, 2), (3, 4)]\n", "# Groups: {0,1,2}, {3,4}, {5} \u2192 3 separate groups\n", "print(f\"{count_groups(6, friendships)} separate groups\")" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python", "version": "3.x" } }, "nbformat": 4, "nbformat_minor": 5 }