{ "cells": [ { "cell_type": "markdown", "id": "3494b0f2", "metadata": { "id": "3494b0f2" }, "source": [ "[![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/MeiraDavidson/compute_module1/blob/main/notebooks/lab_03_the_visible_staircase.ipynb)\n\n", "# Lab 3: The Visible Staircase\n", "\n", "*From* **A First Taste of Algorithms — and the Machines That Learn** *(The Curious Family Library). A computational lab: run the cells in order. A few labs end with a deliberately broken “Break it” cell — that one is meant to fail, and seeing how is the point.*" ] }, { "cell_type": "markdown", "id": "b54cfa9d", "metadata": { "id": "b54cfa9d" }, "source": [ "*Accompanies Chapter 3. The chapter legitimized a strange object — a procedure that calls itself — and read its cost off a tree. In this lab the strange object runs on a real machine, the hidden staircase of calls becomes visible on the screen, and the n log₂ n bill gets audited.*\n", "\n", "## 1. A first self-call\n", "\n", "Before towers, the smallest possible recursion — a countdown:" ] }, { "cell_type": "code", "execution_count": 1, "id": "16cf45f6", "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "16cf45f6", "executionInfo": { "status": "ok", "timestamp": 1782336894598, "user_tz": 240, "elapsed": 8, "user": { "displayName": "Meira Davidson", "userId": "09448014842742744623" } }, "outputId": "72e7d793-91f8-4a88-849a-65e97a3f7009" }, "outputs": [ { "output_type": "stream", "name": "stdout", "text": [ "5\n", "4\n", "3\n", "2\n", "1\n", "liftoff\n" ] } ], "source": [ "def countdown(n):\n", " if n == 0:\n", " print(\"liftoff\")\n", " return\n", " print(n)\n", " countdown(n - 1)\n", "\n", "countdown(5)" ] }, { "cell_type": "markdown", "id": "b6301dae", "metadata": { "id": "b6301dae" }, "source": [ "Read it against the chapter's two rescue conditions. The self-call goes strictly *downward* (`n - 1`). The descent has a *floor* (`n == 0`, where the procedure acts alone and returns). Both present: legitimate. Run it, then trace it in your head the slow way: `countdown(5)` prints 5 and asks `countdown(4)` to do the rest, which prints 4 and asks `countdown(3)`... Every call trusts the smaller call completely. That trust is the whole technique.\n", "\n", "## 2. Hanoi in seven lines\n", "\n", "The chapter's three-line plan — clear, cross, restack — translated nearly word for word:" ] }, { "cell_type": "code", "execution_count": 2, "id": "e6e46f3f", "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "e6e46f3f", "executionInfo": { "status": "ok", "timestamp": 1782336902021, "user_tz": 240, "elapsed": 4, "user": { "displayName": "Meira Davidson", "userId": "09448014842742744623" } }, "outputId": "713baead-72e3-49c2-d95b-234c3dbd4684" }, "outputs": [ { "output_type": "stream", "name": "stdout", "text": [ "disk 1: A -> C\n", "disk 2 : A -> B\n", "disk 1: C -> B\n", "disk 3 : A -> C\n", "disk 1: B -> A\n", "disk 2 : B -> C\n", "disk 1: A -> C\n" ] } ], "source": [ "def hanoi(n, source, target, spare):\n", " if n == 1:\n", " print(\"disk 1:\", source, \"->\", target)\n", " return\n", " hanoi(n - 1, source, spare, target) # clear the way (note: spare is the goal)\n", " print(\"disk\", n, \":\", source, \"->\", target) # the big crossing\n", " hanoi(n - 1, spare, target, source) # restack on top\n", "\n", "hanoi(3, \"A\", \"C\", \"B\")" ] }, { "cell_type": "markdown", "id": "d6183c33", "metadata": { "id": "d6183c33" }, "source": [ "Run it and check the seven moves against the solution your hands found with coins. Then the only part of this program that ever confuses anyone: the *peg arguments swap roles* at each call. In the first self-call, the spare peg is the destination — clearing the way means parking the small tower *out of* the way. Trace `hanoi(2, \"A\", \"B\", \"C\")` (just that call) on paper and confirm the pegs land where the plan demands.\n", "\n", "How big a tower dares the machine? First predict from the chapter's table how many moves `hanoi(20, ...)` would print, then *don't print them* — counting wants a different version:" ] }, { "cell_type": "code", "execution_count": 3, "id": "08b5f7a1", "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "08b5f7a1", "executionInfo": { "status": "ok", "timestamp": 1782336988592, "user_tz": 240, "elapsed": 80455, "user": { "displayName": "Meira Davidson", "userId": "09448014842742744623" } }, "outputId": "494afc1d-ffa3-4bad-ab8c-0b5c4d1ade8f" }, "outputs": [ { "output_type": "stream", "name": "stdout", "text": [ "1023\n", "1048575\n", "1073741823\n" ] } ], "source": [ "def hanoi_moves(n):\n", " if n == 1:\n", " return 1\n", " return hanoi_moves(n - 1) + 1 + hanoi_moves(n - 1)\n", "\n", "print(hanoi_moves(10))\n", "print(hanoi_moves(20))\n", "print(hanoi_moves(30))" ] }, { "cell_type": "markdown", "id": "4d486b61", "metadata": { "id": "4d486b61" }, "source": [ "Check all three against 2ⁿ − 1. Then read the function once more: it is the recurrence M(n) = 2M(n−1) + 1, alive. The chapter's cost *equation* and this cost *program* are the same sentence in two grammars.\n", "\n", "## 3. Making the staircase visible\n", "\n", "Every call in §2 ran at some *depth* — Hanoi-for-3 paused while Hanoi-for-2 worked, which paused for Hanoi-for-1. The machine keeps the paused calls on its stack; let's print the stack's shape directly. Pass the depth along, and indent by it:" ] }, { "cell_type": "code", "execution_count": 4, "id": "aee0cf32", "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "aee0cf32", "executionInfo": { "status": "ok", "timestamp": 1782336988609, "user_tz": 240, "elapsed": 13, "user": { "displayName": "Meira Davidson", "userId": "09448014842742744623" } }, "outputId": "8be65bee-ed69-4f6b-95be-6f6b87a23557" }, "outputs": [ { "output_type": "stream", "name": "stdout", "text": [ " want 3 disks: A -> C\n", " want 2 disks: A -> B\n", " want 1 disks: A -> C\n", " move disk 1\n", " move disk 2\n", " want 1 disks: C -> B\n", " move disk 1\n", " move disk 3\n", " want 2 disks: B -> C\n", " want 1 disks: B -> A\n", " move disk 1\n", " move disk 2\n", " want 1 disks: A -> C\n", " move disk 1\n" ] } ], "source": [ "def hanoi_trace(n, source, target, spare, depth):\n", " print(\" \" * depth, \"want\", n, \"disks:\", source, \"->\", target)\n", " if n == 1:\n", " print(\" \" * depth, \"move disk 1\")\n", " return\n", " hanoi_trace(n - 1, source, spare, target, depth + 1)\n", " print(\" \" * depth, \"move disk\", n)\n", " hanoi_trace(n - 1, spare, target, source, depth + 1)\n", "\n", "hanoi_trace(3, \"A\", \"C\", \"B\", 0)" ] }, { "cell_type": "markdown", "id": "6795dddd", "metadata": { "id": "6795dddd" }, "source": [ "(`\" \" * depth` is a small Python kindness: a string times a number repeats it.) Run it and *read the left margin*: the indentation breathes in and out, deeper as work is delegated, shallower as delegations finish. That margin **is** the call stack — the deep-water box made of whitespace. Draw the same shape by hand for `hanoi_trace(2, ...)` before believing the machine's.\n", "\n", "## 4. Merge sort, audited\n", "\n", "The chapter sorted cards: split, sort each half somehow, merge. The merge first — it is where all real work happens:" ] }, { "cell_type": "code", "execution_count": 5, "id": "336735be", "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "336735be", "executionInfo": { "status": "ok", "timestamp": 1782336988631, "user_tz": 240, "elapsed": 19, "user": { "displayName": "Meira Davidson", "userId": "09448014842742744623" } }, "outputId": "f6f2ee40-af43-4ee9-fd09-c6768e343da0" }, "outputs": [ { "output_type": "stream", "name": "stdout", "text": [ "[2, 4, 5, 9, 11, 12, 28, 30]\n" ] } ], "source": [ "def merge(left, right):\n", " result = []\n", " i = 0 # finger on left pile\n", " j = 0 # finger on right pile\n", " while i < len(left) and j < len(right):\n", " if left[i] <= right[j]:\n", " result.append(left[i])\n", " i = i + 1\n", " else:\n", " result.append(right[j])\n", " j = j + 1\n", " while i < len(left): # one pile ran dry; sweep the other in\n", " result.append(left[i])\n", " i = i + 1\n", " while j < len(right):\n", " result.append(right[j])\n", " j = j + 1\n", " return result\n", "\n", "print(merge([2, 9, 11, 30], [4, 5, 12, 28]))" ] }, { "cell_type": "markdown", "id": "20861913", "metadata": { "id": "20861913" }, "source": [ "Two fingers, two piles, always take the smaller top card — the code is your hands from the chapter. Now the recursion around it, with one new piece of notation: `items[:mid]` is the list *up to* position mid, and `items[mid:]` is the rest. Splitting is the idea; the colon is just its spelling." ] }, { "cell_type": "code", "execution_count": 6, "id": "bf2a0869", "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "bf2a0869", "executionInfo": { "status": "ok", "timestamp": 1782336988661, "user_tz": 240, "elapsed": 9, "user": { "displayName": "Meira Davidson", "userId": "09448014842742744623" } }, "outputId": "df649a3b-f1f9-4806-ab89-5ea54b5b4722" }, "outputs": [ { "output_type": "stream", "name": "stdout", "text": [ "[1, 2, 3, 4, 6, 7, 8, 9]\n" ] } ], "source": [ "def merge_sort(items):\n", " if len(items) <= 1: # the floor: tiny piles are born sorted\n", " return items\n", " mid = len(items) // 2\n", " left = merge_sort(items[:mid])\n", " right = merge_sort(items[mid:])\n", " return merge(left, right)\n", "\n", "print(merge_sort([7, 3, 9, 1, 8, 2, 6, 4]))" ] }, { "cell_type": "markdown", "id": "44270f55", "metadata": { "id": "44270f55" }, "source": [ "Eight lines around a merge. Test it on your own lists — include an empty list, a one-item list, a list with repeats, a list already sorted backward. (Testing the *edges* first is a habit worth stealing from professionals; Chapter 1's human moment is the reason the habit exists.)\n", "\n", "## 5. The bill, audited\n", "\n", "The chapter promised C(n) ≈ n log₂ n in the currency of element-steps — one step per card the merge touches. Send the count climbing back up the recursion alongside the sorted list; the function now returns a two-item list, `[sorted, steps]`:" ] }, { "cell_type": "code", "execution_count": null, "id": "f6ac9dba", "metadata": { "id": "f6ac9dba" }, "outputs": [], "source": [ "def merge_sort_count(items):\n", " if len(items) <= 1:\n", " return [items, 0]\n", " mid = len(items) // 2\n", " left = merge_sort_count(items[:mid])\n", " right = merge_sort_count(items[mid:])\n", " merged = merge(left[0], right[0])\n", " steps = left[1] + right[1] + len(merged) # this merge touches every card once\n", " return [merged, steps]" ] }, { "cell_type": "markdown", "id": "64ea6afb", "metadata": { "id": "64ea6afb" }, "source": [ "Now the audit, in the style of Lab 1's race — and watch the *per-item* column:" ] }, { "cell_type": "code", "execution_count": null, "id": "d8164373", "metadata": { "id": "d8164373" }, "outputs": [], "source": [ "for n in [1000, 10000, 100000, 1000000]:\n", " items = list(range(n, 0, -1)) # n, n-1, ..., 1: sorted backward\n", " result = merge_sort_count(items)\n", " steps = result[1]\n", " print(n, steps, \"steps;\", steps / n, \"per item\")" ] }, { "cell_type": "markdown", "id": "560a88ff", "metadata": { "id": "560a88ff" }, "source": [ "The left column multiplies by 10; the per-item column climbs by a little over 3 each row. You have seen that gait before — it is the logarithm's, from Chapter 1's table, now appearing as the *per-item* price of sorting. Total steps ≈ n × (log₂ n-ish per item): the tree's level-count, measured in the wild. Check one row against arithmetic: for n = 1,000,000, is steps close to 20 million?\n", "\n", "## Break it\n", "\n", "Predict first. Run second. Explain any gap third.\n", "\n", "**1.** Starve `countdown` of its floor: delete the `if n == 0:` block (keep the rest) and call `countdown(5)`. Predict precisely what the machine will do — forever? crash? something else? — then run it and *read the error to its last line*. The number it complains about (Python's recursion limit, near a thousand) is the deep-water box's claim that the stack is physical, demonstrated. How is this failure different in kind from Sevenia's in Lab 2 — which lab's program was *wrong*, and which was *exhausted*?\n", "\n", "**2.** In `hanoi`, swap the two recursive calls (clear-the-way and restack trade places). Predict: will the printed moves still be *legal* — no large disk onto a small one? Then run it for n = 3 and *audit the move list with your coins*, move by move. Find the first illegal moment and describe which trust was betrayed.\n", "\n", "**3.** In `merge_sort_count`, change `mid = len(items) // 2` to `mid = 1`: every split now peels a single card off the front instead of halving. Two predictions before running: is the output still *correct*? and what happens to the cost — per-item column flat-ish like the logarithm, or growing with n? Audit the lopsided version on sizes 200, 400, 800 (not the big sizes — you'll discover why in a moment) and look at the *total* steps as n doubles. Doubling the input does what to the bill? Connect it to the chapter's closing sentence: *where a recursion sends its work is the whole game*. You have just met, in your own code, the difference between n log n and n² — Chapter 6 makes it official. Then, deliberately, run size 2,000 and read the error to its last line: the lopsided tree is n calls deep where the balanced tree was log₂ n deep, and the machine's stack — Break-it 1's discovery — just refused the architecture, not the arithmetic.\n", "\n", "**4.** In `merge`, change `<=` to `<`. Predict whether any list of *numbers* can ever come out unsorted. Run your tests; they should all pass. So the character changed nothing? To find out, sort things that can genuinely *tie*. Make each item a [score, name] pair and — one more edit — make the merge compare **scores only**: change the comparison line to `if left[i][0] <= right[j][0]:`. Now sort `[[3, \"Ada\"], [1, \"Hua\"], [3, \"Noether\"]]` with the `<=` version and the `<` version and compare the outputs. What happened to the two score-3 students, and which version keeps tied items in their original order? (Chapter 6 names this property; you have discovered it early. And a side puzzle: why did the experiment *need* the scores-only edit — what was Python quietly doing with the pairs before it?)\n", "\n", "\n", "\n", "
" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python", "version": "3" }, "colab": { "provenance": [] } }, "nbformat": 4, "nbformat_minor": 5 }