{ "cells": [ { "cell_type": "markdown", "id": "d356f945", "metadata": {}, "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_04_the_notebook.ipynb)\n\n", "# Lab 4: The Notebook\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": "54e1b19c", "metadata": {}, "source": [ "*Accompanies Chapter 4. The chapter caught a correct recursion wasting its life on repetition, and tore the exponential down with a notebook. In this lab the waste is counted call by call, the notebook is built, and your own Chapter 2 greedy is put on trial against a changer that cannot lose.*\n", "\n", "## 1. The amnesiac, counted\n", "\n", "The staircase recursion, plus the counting trick from Lab 3 — each call reports the *total number of calls* it caused, alongside its answer, as a two-item list `[answer, calls]`:" ] }, { "cell_type": "code", "execution_count": null, "id": "9d72332a", "metadata": {}, "outputs": [], "source": [ "def ways_count(n):\n", " if n <= 2:\n", " return [n, 1] # ways(1)=1, ways(2)=2; one call\n", " a = ways_count(n - 1)\n", " b = ways_count(n - 2)\n", " return [a[0] + b[0], a[1] + b[1] + 1]\n", "\n", "print(ways_count(6))\n", "print(ways_count(10))" ] }, { "cell_type": "markdown", "id": "35291170", "metadata": {}, "source": [ "Check ways(6) against the chapter's hand count — and check the call count against your drawing of the tree (the chapter said fifteen boxes; does the machine agree?). Now the audit, in the house style:" ] }, { "cell_type": "code", "execution_count": null, "id": "19d61e12", "metadata": {}, "outputs": [], "source": [ "for n in [10, 15, 20, 25, 30]:\n", " result = ways_count(n)\n", " print(n, \"ways:\", result[0], \" calls:\", result[1])" ] }, { "cell_type": "markdown", "id": "47a2f274", "metadata": {}, "source": [ "Read the calls column the way you read every table in this book: n goes up by 5 each row — what happens to the calls? This is not Chapter 1's logarithm and not even Chapter 3's doubling-per-step; measure its gait (each row is roughly *how many times* the previous?). Run n = 34 and *feel* the pause before the answer — the first time in this book the machine has kept you waiting. The answer is a seven-digit number you could extend by hand in seconds. All that waiting was repetition.\n", "\n", "## 2. The notebook\n", "\n", "Python's notebook is the **dictionary**: like a list, but indexed by *question* rather than by position. Three moves to learn, all visible here:" ] }, { "cell_type": "code", "execution_count": null, "id": "e73483ae", "metadata": {}, "outputs": [], "source": [ "memo = {} # an empty notebook\n", "memo[7] = 13 # write: next to question 7, answer 13\n", "print(7 in memo) # ask: is question 7 already answered?\n", "print(memo[7]) # read the answer" ] }, { "cell_type": "markdown", "id": "f494cf83", "metadata": {}, "source": [ "Now the chapter's fix, verbatim — look it up, or compute-and-write:" ] }, { "cell_type": "code", "execution_count": null, "id": "9ccb4776", "metadata": {}, "outputs": [], "source": [ "memo = {1: 1, 2: 2} # the floor, pre-written\n", "\n", "def ways_memo(n):\n", " if n in memo:\n", " return memo[n]\n", " answer = ways_memo(n - 1) + ways_memo(n - 2)\n", " memo[n] = answer\n", " return answer\n", "\n", "print(ways_memo(30))" ] }, { "cell_type": "markdown", "id": "07fd495c", "metadata": {}, "source": [ "Same recursion, same floor, same answers — verify a few against §1. The only new behavior: no question is ever *computed* twice.\n", "\n", "## 3. The collapse, measured\n", "\n", "Count the memoized version's calls (the counter rides along in a one-item list — a small trick: numbers passed to functions don't come back changed, but a list's *contents* do, so we keep the count in a box and pass the box):" ] }, { "cell_type": "code", "execution_count": null, "id": "9098b9f7", "metadata": {}, "outputs": [], "source": [ "memo = {1: 1, 2: 2}\n", "calls = [0]\n", "\n", "def ways_memo_count(n):\n", " calls[0] = calls[0] + 1\n", " if n in memo:\n", " return memo[n]\n", " answer = ways_memo_count(n - 1) + ways_memo_count(n - 2)\n", " memo[n] = answer\n", " return answer\n", "\n", "ways_memo_count(30)\n", "print(\"memoized calls for n=30:\", calls[0])" ] }, { "cell_type": "markdown", "id": "7aa25d7f", "metadata": {}, "source": [ "Set it beside §1's number for n = 30. Millions against dozens, identical answers. Now the gait check: reset the notebook (rerun the cell after changing 30 to 40, but reset `memo` and `calls` first — why must you reset? predict what the count reports if you *don't*) and confirm the memoized call count grows like n itself: the straight line that replaced the explosion.\n", "\n", "## 4. Sevenia on trial\n", "\n", "The chapter's recurrence, as a program — for *any* coin system. The notebook here must be reset per problem, so we wrap the whole trial in one function that builds a fresh memo, then defines the recursive worker inside (a function defined inside a function: new sight, no new idea — the inner worker simply gets to use the outer function's `memo` and `coins`):" ] }, { "cell_type": "code", "execution_count": null, "id": "054d1256", "metadata": {}, "outputs": [], "source": [ "def fewest_coins(coins, amount):\n", " memo = {0: 0} # the floor: no debt, no coins\n", "\n", " def best(a):\n", " if a in memo:\n", " return memo[a]\n", " options = []\n", " for c in coins:\n", " if c <= a:\n", " options.append(best(a - c))\n", " answer = 1 + min(options) # min: the cheapest priced future\n", " memo[a] = answer\n", " return answer\n", "\n", " return best(amount)\n", "\n", "print(fewest_coins([10, 7, 1], 14))" ] }, { "cell_type": "markdown", "id": "8acad0cd", "metadata": {}, "source": [ "Two. The wound closes on your screen. (`min` of a list is what it says; it has been waiting in Python all along for this chapter.)\n", "\n", "Now the full trial — your Chapter 2 greedy versus the table method, every amount to 100. Retype your greedy from Lab 2 (or paste it from your notebook there):" ] }, { "cell_type": "code", "execution_count": null, "id": "e16b3c6b", "metadata": {}, "outputs": [], "source": [ "def greedy_change(coins, amount):\n", " used = []\n", " for coin in coins:\n", " while amount >= coin:\n", " amount = amount - coin\n", " used.append(coin)\n", " return used\n", "\n", "for amount in range(1, 101):\n", " g = len(greedy_change([10, 7, 1], amount))\n", " d = fewest_coins([10, 7, 1], amount)\n", " if g != d:\n", " print(amount, \"greedy:\", g, \" table:\", d)" ] }, { "cell_type": "markdown", "id": "b8f24e6e", "metadata": {}, "source": [ "Compare the verdict list with your Lab 2 audit (which used brute force as the truth). Same failures, same truth — but notice what changed *about the truth-machine*: Lab 2's three nested loops tried everything; this one prices each amount once. The notebook replaced the brute force. Confirm the new machine's reach: `fewest_coins([10, 7, 1], 900)` — instant, where three nested loops would grind.\n", "\n", "## 5. The same table, bottom-up\n", "\n", "The chapter promised the notebook can be filled by a plain loop, floor upward, no recursion at all:" ] }, { "cell_type": "code", "execution_count": null, "id": "c0126b67", "metadata": {}, "outputs": [], "source": [ "def fewest_coins_table(coins, amount):\n", " best = [0] # best[0] = 0; the table grows rightward\n", " for a in range(1, amount + 1):\n", " options = []\n", " for c in coins:\n", " if c <= a:\n", " options.append(best[a - c])\n", " best.append(1 + min(options))\n", " return best\n", "\n", "table = fewest_coins_table([10, 7, 1], 14)\n", "print(table)\n", "print(\"best(14) =\", table[14])" ] }, { "cell_type": "markdown", "id": "53bff3da", "metadata": {}, "source": [ "Read the printed list against the chapter's hand-built table — entry by entry, they must agree (the table *is* the method; the two routes merely fill it in different orders). This version climbs to any height without a call stack: try amount 5,000, then try the same in §4's recursive version and witness which one meets Lab 3's old enemy.\n", "\n", "## Break it\n", "\n", "Predict first. Run second. Explain any gap third.\n", "\n", "**1.** In §2's `ways_memo`, delete only the line `memo[n] = answer` (keep everything else). Predict: still correct? still fast? one or the other? Run §3's count with the line gone. Which single line of this lab was the entire chapter?\n", "\n", "**2.** Sabotage by sharing: move §4's `memo = {0: 0}` *outside* the function (one notebook for all trials), then run `fewest_coins([10, 7, 1], 14)` followed by `fewest_coins([25, 10, 5, 1], 14)`. Predict both outputs first. The second answer is wrong — wrong *how*, and in whose favor? State the moral as one sentence about what a notebook entry silently assumes. (This bug, in grown-up systems, is called cache poisoning, and it has caused real outages; you have now caused one in eleven lines.)\n", "\n", "**3.** Hops of {2, 3} only: adapt `ways_memo` for a staircase where you may hop 2 or 3 steps. The floor needs care — decide what ways(0) and ways(1) should *be* (is \"do nothing\" a way to climb zero steps? is 1 climbable at all?), write your floor, and test against hand counts for n = 2, 3, 4, 5. Then break a classmate's floor: find the n where a plausible-but-wrong floor (say, ways(0) = 0) first gives a wrong count. Floors are where recursions are won and lost.\n", "\n", "**4.** In §5's bottom-up changer, feed it a kingdom without the 1-coin: `fewest_coins_table([10, 7], 11)`. Predict the failure mode precisely — wrong answer, error, or silence? — and read what actually happens to its last line. Then repair the design: unpayable amounts need an answer that survives `min` and `+ 1` honestly (the chapter's Problem 3.5 is circling this same hole). Propose a fix, implement it, and verify amount 11 reports \"impossible\" while 17 reports 2.\n", "\n", "\n", "\n", "
" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python", "version": "3" } }, "nbformat": 4, "nbformat_minor": 5 }