{ "cells": [ { "cell_type": "markdown", "id": "5754b8a3", "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_02_the_cost_of_confidence.ipynb)\n\n", "# Lab 2: The Cost of Confidence\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": "48c60bfc", "metadata": {}, "source": [ "*Accompanies Chapter 2. The chapter introduced a strategy — at every step, take the option that looks best right now — and claimed it is sometimes perfect and sometimes confidently wrong. In this lab you build both outcomes with your own hands.*\n", "\n", "## 1. The cashier's algorithm\n", "\n", "Chapter 2 opened behind a cash register: owe someone 63 cents, and your hands know the algorithm — give a quarter, another quarter, a dime, three pennies. Take the biggest coin that fits; repeat. Here it is in Python:" ] }, { "cell_type": "code", "execution_count": null, "id": "8a4cecdc", "metadata": {}, "outputs": [], "source": [ "def greedy_change(coins, amount): # coins listed largest first\n", " used = []\n", " for coin in coins:\n", " while amount >= coin:\n", " amount = amount - coin\n", " used.append(coin)\n", " return used\n", "\n", "print(greedy_change([25, 10, 5, 1], 63))" ] }, { "cell_type": "markdown", "id": "0c8c04a2", "metadata": {}, "source": [ "One new tool: `used.append(coin)` adds an item to the end of the list `used` — the program is keeping a record of its decisions, which is what `used = []` (an empty list, a blank ledger) is for. Everything else you own already: the `for` walks the coin types from largest down; the `while` spends each coin type as long as it still fits.\n", "\n", "Run it on a few amounts. Six coins for 63. Count by hand and check: can you beat six?\n", "\n", "You can't — with these coins, the greedy answer is the best answer, for 63 and for every other amount. (That this is *true* is believable; *why* it's true is genuinely subtle, and the chapter was honest that we are not proving it. We are about to see why such a proof would have to exist: because the same instinct, on different coins, fails.)\n", "\n", "## 2. The kingdom of Sevenia\n", "\n", "Chapter 2's kingdom mints three coins: 1, 7, and 10. You owe 14. Before running anything, do it greedily in your head — and then do it *well* in your head." ] }, { "cell_type": "code", "execution_count": null, "id": "371c1fbe", "metadata": {}, "outputs": [], "source": [ "print(greedy_change([10, 7, 1], 14))" ] }, { "cell_type": "markdown", "id": "fca95507", "metadata": {}, "source": [ "Five coins, says your program, with complete confidence. The right answer is two: 7 + 7. The code is not buggy. It did exactly what greedy means — and greedy is wrong here. The grab-the-biggest instinct took the 10 because the 10 looked best *at that moment*, and taking it destroyed the 7 + 7 future that was quietly available. Greedy never looks back, and never apologizes.\n", "\n", "## 3. Catching every failure\n", "\n", "One failure could be a fluke. Let's audit Sevenia completely. For three-coin systems we can find the *true* best answer by sheer brute force — trying every possible combination. This is \"doing all the work,\" the thing algorithms exist to avoid, and we do it here deliberately, as a measuring stick:" ] }, { "cell_type": "code", "execution_count": null, "id": "6653f07d", "metadata": {}, "outputs": [], "source": [ "def best_change_3(c1, c2, c3, amount): # c3 must be 1\n", " best = amount # amount pennies always works\n", " for a in range(amount // c1 + 1):\n", " for b in range(amount // c2 + 1):\n", " for c in range(amount // c3 + 1):\n", " if a*c1 + b*c2 + c*c3 == amount:\n", " if a + b + c < best:\n", " best = a + b + c\n", " return best\n", "\n", "print(best_change_3(10, 7, 1, 14))" ] }, { "cell_type": "markdown", "id": "bb380aff", "metadata": {}, "source": [ "Three loops, one inside another: every count of 10s, against every count of 7s, against every count of 1s. Nothing escapes. Now the audit — every amount from 1 to 30, greedy versus truth:" ] }, { "cell_type": "code", "execution_count": null, "id": "9131da9f", "metadata": {}, "outputs": [], "source": [ "for amount in range(1, 31):\n", " g = len(greedy_change([10, 7, 1], amount))\n", " b = best_change_3(10, 7, 1, amount)\n", " if g != b:\n", " print(amount, \"greedy:\", g, \"best:\", b)" ] }, { "cell_type": "markdown", "id": "a692d6ff", "metadata": {}, "source": [ "Run it and read the list of amounts where greedy loses. Look for a pattern in them before the Break-it section asks you about it. This little audit loop — confident method versus exhaustive truth on every small case — is a tool you will use for the rest of your life, and not only on coins.\n", "\n", "> A note for later: the brute force was affordable here because the kingdom was small. Watch what `best_change_3` costs as amounts grow — three nested loops multiply. Chapter 4 will find the best answer *without* trying everything, and will do it using the failure you just catalogued. The wound stays open until then.\n", "\n", "## 4. Scheduling a day\n", "\n", "The chapter's second arena: from a pile of events that may overlap, attend as many as possible. The winning rule was *earliest finish first* — always take the event that ends soonest among those you can still attend. To build it we store each event as a two-item list `[finish, start]`, finish *first*, for one sneaky reason: Python's `.sort()` arranges a list of pairs by their first entries, so putting the finish time first makes plain sorting line the events up exactly the way the rule wants. (`.sort()` itself is a sealed instrument for now — Chapter 6 opens the box and asks what it costs.)" ] }, { "cell_type": "code", "execution_count": null, "id": "3f5b4746", "metadata": {}, "outputs": [], "source": [ "def schedule(events): # each event is [finish, start]\n", " events.sort() # earliest finish now comes first\n", " chosen = []\n", " free_at = 0\n", " for e in events:\n", " finish = e[0]\n", " start = e[1]\n", " if start >= free_at: # does it begin after I'm free?\n", " chosen.append([start, finish])\n", " free_at = finish\n", " return chosen" ] }, { "cell_type": "markdown", "id": "ac749d14", "metadata": {}, "source": [ "Try it on the chapter's example day — times are hours on a 24-hour clock, and each event is `[finish, start]`:" ] }, { "cell_type": "code", "execution_count": null, "id": "48aca0b4", "metadata": {}, "outputs": [], "source": [ "day = [[10, 9], [11, 9], [12, 11], [13, 10], [14, 12], [16, 13], [15, 14]]\n", "print(schedule(day))" ] }, { "cell_type": "markdown", "id": "7f0c70c0", "metadata": {}, "source": [ "Trace the result against a drawing of the seven events on a timeline (really draw it — the timeline is the proof's natural habitat, and you'll want it for the Diamond).\n", "\n", "Now the real assignment: write out *your own actual week* — classes, practices, the things you do — as `[finish, start]` pairs, and run the scheduler on it. Then deliberately overbook a fantasy Saturday with twelve overlapping events and see what the rule salvages.\n", "\n", "## Break it\n", "\n", "Predict first. Run second. Explain any gap third.\n", "\n", "**1.** In §1, hand `greedy_change` the coins *smallest first*: `greedy_change([1, 5, 10, 25], 63)`. Predict the exact output before running. What does the result say about the phrase \"take the best-looking option\" — best-looking *according to whom*?\n", "\n", "**2.** From your §3 audit of Sevenia: extend the range to 100 and collect every amount where greedy loses. State a pattern (\"greedy fails exactly when the amount looks like ___\") and then *test your pattern* by predicting the failures between 100 and 130 before running that range.\n", "\n", "**3.** US coins minus the nickel: a country with only `[25, 10, 1]`. Predict — does greedy stay perfect, or fail somewhere? Commit to an answer and a reason, then audit amounts 1 to 100. (If it fails, find the smallest failure and explain, in the style of Sevenia's 14, exactly which future the greedy choice destroyed.)\n", "\n", "**4.** In `schedule`, change `start >= free_at` to `start > free_at` and rerun your week. Predict what kind of event pair gets wrongly rejected. One character — what real-world scheduling assumption does it encode?\n", "\n", "**5.** Sabotage the rule itself: store events as `[start, finish]` so that `.sort()` lines them up by *start* time, adjust the two indexing lines to match, and rerun the chapter's example day. Predict the output first. You have just built, in working code, one of the counterexamples from the chapter — say which one.\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 }