{ "cells": [ { "cell_type": "markdown", "id": "d519042d", "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_01_counting_steps.ipynb)\n\n", "# Lab 1: Counting Steps\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": "0a58d873", "metadata": {}, "source": [ "*Accompanies Chapter 1. The chapter asked two questions of every algorithm: does it give the right answer, and what does the answer cost? This lab is about measuring cost — not with a stopwatch, but by counting.*\n", "\n", "## 1. Looking through a list is a loop\n", "\n", "Chapter 1's first algorithm was the obvious one: to find a name in an unsorted list, check the first entry, then the second, and keep going until you find it or run out. Written in Python, the algorithm and the sentence describing it are nearly the same thing:" ] }, { "cell_type": "code", "execution_count": null, "id": "e22c548e", "metadata": {}, "outputs": [], "source": [ "names = [\"Ada\", \"Erdos\", \"Gauss\", \"Hua\", \"Noether\", \"Ramanujan\"]\n", "\n", "for name in names:\n", " if name == \"Hua\":\n", " print(\"found it\")" ] }, { "cell_type": "markdown", "id": "1682df86", "metadata": {}, "source": [ "The new construct is the `for` loop. The line `for name in names:` means: take each entry of the list in turn, call it `name`, and run the indented lines below for it. The loop is not a programming trick bolted onto the algorithm. The loop *is* the algorithm — \"check each one in turn\" — written in a notation the machine accepts. (The other new construct, `if`, does what it says: run the indented line only when the condition holds. It will earn a fuller treatment in Chapter 2, where an algorithm's whole character turns on a single `if`.)\n", "\n", "## 2. Make the cost visible\n", "\n", "The program above finds Hua but keeps its effort secret. Add the counter from Lab 0:" ] }, { "cell_type": "code", "execution_count": null, "id": "950241c0", "metadata": {}, "outputs": [], "source": [ "names = [\"Ada\", \"Erdos\", \"Gauss\", \"Hua\", \"Noether\", \"Ramanujan\"]\n", "\n", "steps = 0\n", "for name in names:\n", " steps = steps + 1\n", " if name == \"Hua\":\n", " print(\"found after\", steps, \"steps\")\n", " break" ] }, { "cell_type": "markdown", "id": "f389b7b1", "metadata": {}, "source": [ "(`break` means: stop the loop now. Without it, the loop would keep checking names after finding Hua — correct, but wasteful, and we are in the business of counting waste.)\n", "\n", "Run it. Then move `\"Hua\"` to the front of the list and run it again. Then to the back. Three runs, three costs. The cost of this algorithm is not a number; it depends on where the target sits. When we say *linear search takes up to n steps on a list of n items*, the \"up to\" is doing honest work — it is the worst case, the only promise the algorithm can keep no matter where the target hides.\n", "\n", "## 3. Searching for what isn't there\n", "\n", "Searching real lists, you don't know in advance whether the target is present. Predict before running: what does the program in §2 print if you search for `\"Euler\"`?\n", "\n", "It prints nothing. The loop ends, no message, silence. The program is not wrong, exactly — but silence is a poor answer to a question. Here is a version that always answers, packaged so we can reuse it:" ] }, { "cell_type": "code", "execution_count": null, "id": "140377b2", "metadata": {}, "outputs": [], "source": [ "def linear_search(items, target):\n", " steps = 0\n", " for item in items:\n", " steps = steps + 1\n", " if item == target:\n", " return steps\n", " return -steps # negative means: not found, after this many steps" ] }, { "cell_type": "markdown", "id": "e890d999", "metadata": {}, "source": [ "Two new things. `def` gives the procedure a name so we can call it on any list and any target without retyping it — that is all `def` means for now, though in Chapter 3 the ability to name a procedure will turn out to be more powerful than it looks. And `return` hands a value back to whoever called. Try it:" ] }, { "cell_type": "code", "execution_count": null, "id": "15a0d609", "metadata": {}, "outputs": [], "source": [ "print(linear_search([\"Ada\", \"Erdos\", \"Gauss\", \"Hua\"], \"Hua\"))\n", "print(linear_search([\"Ada\", \"Erdos\", \"Gauss\", \"Hua\"], \"Euler\"))" ] }, { "cell_type": "markdown", "id": "1f4ab5f8", "metadata": {}, "source": [ "Notice what a miss costs: the *full* n steps, every time. You cannot declare something absent until you have looked everywhere. Absence is expensive — unless the list has structure. Which brings us to the chapter's main event.\n", "\n", "## 4. Binary search, measured\n", "\n", "Chapter 1's claim: if the list is *sorted*, you can find any target — or certify its absence — by repeatedly checking the middle and discarding half. Here is the claim as a program:" ] }, { "cell_type": "code", "execution_count": null, "id": "0a9a7e9b", "metadata": {}, "outputs": [], "source": [ "def binary_search(items, target): # items must be sorted\n", " steps = 0\n", " lo = 0\n", " hi = len(items) - 1\n", " while lo <= hi:\n", " steps = steps + 1\n", " mid = (lo + hi) // 2 # // divides and drops the remainder\n", " if items[mid] == target:\n", " return steps\n", " if items[mid] < target:\n", " lo = mid + 1 # target can only be in the right half\n", " else:\n", " hi = mid - 1 # ... or the left half\n", " return -steps" ] }, { "cell_type": "markdown", "id": "5d87d0bb", "metadata": {}, "source": [ "Fifteen lines, and three small novelties: `items[mid]` picks out the entry at position `mid` (positions start at 0); `len(items)` is the length of the list; and `while` is a loop that runs as long as its condition holds — here, as long as the stretch between `lo` and `hi` hasn't shrunk to nothing. The pair `lo, hi` marks the region where the target could still be. Every pass through the loop, one of the last two lines cuts that region roughly in half. That sentence is the entire algorithm; the code is just the sentence with its sleeves rolled up.\n", "\n", "Before running anything, do one search entirely by hand. Take the sorted list 2, 5, 8, 13, 21, 34, 55, 89 and search for 21, writing down `lo`, `hi`, and `mid` at every step. Then run the code and check that the machine agrees with your hand. If it doesn't, one of you is wrong, and finding out which is the best exercise in this lab.\n", "\n", "## 5. The race\n", "\n", "Now the measurement this lab has been building toward. We race the two searches on lists of increasing size, searching each time for the *last* element — the worst case for linear search:" ] }, { "cell_type": "code", "execution_count": null, "id": "00f62e13", "metadata": {}, "outputs": [], "source": [ "for n in [10, 100, 1000, 10000, 100000, 1000000]:\n", " items = list(range(n)) # the sorted list 0, 1, ..., n-1\n", " target = n - 1 # the last element\n", " print(n, linear_search(items, target), binary_search(items, target))" ] }, { "cell_type": "markdown", "id": "19e0e402", "metadata": {}, "source": [ "Run it and look at the table. The left column multiplies by 10 each row. The middle column does the same — linear search's cost grows in step with the list, which is what \"linear\" means. The right column barely moves. A million items, about twenty steps.\n", "\n", "Now sit with the table for a minute, because it is saying something strange. Each tenfold growth in the list adds the same *small, fixed* number of steps to binary search — roughly three or four per row. Multiplying the problem *adds* to the cost. You met a function with exactly this character in Book 2: the logarithm, the function that turns multiplication into addition. Binary search costs about log₂ n steps because each step halves the region, and \"how many halvings from n down to 1\" is precisely what log₂ n counts.\n", "\n", "**Deeper water.** Extend the table in your head: at this rate, how many steps would binary search need on a *trillion* items? Write down your estimate, then test the rule \"tenfold the items, add three or four steps\" against it. Later, when you can prove the cost is ⌈log₂(n+1)⌉ exactly, check your estimate again. (And a question to keep: linear search never needed the list sorted. Binary search does. Sorting itself costs something — Chapter 6 asks how much, and whether the toll is worth paying. Spoiler: it depends on how many searches you plan to do, which is the kind of answer cost questions usually have.)\n", "\n", "## Break it\n", "\n", "Predict first. Run second. Explain any gap third.\n", "\n", "1. In `binary_search`, change `lo = mid + 1` to `lo = mid`. Search the list 2, 5, 8, 13 for 21. Predict what happens before you run it — and be patient with your prediction. (When you understand what went wrong, you have understood why the `+ 1` is load-bearing, and you have met the most common way binary search is written incorrectly by professionals.)\n", "2. Run `binary_search` on an *unsorted* list, searching for an element that is genuinely in it. Does it find it? Sometimes? Always? Never? Try several lists before answering. What exactly did sortedness buy?\n", "3. In the race of §5, change the target from the last element to the *first* (`target = 0`). Predict both columns. Which algorithm's cost changed, and what does that tell you about worst-case versus best-case as ways of describing an algorithm?\n", "4. (Harder.) Modify `linear_search` so that instead of returning step counts it returns the *position* of the target, or `-1` if absent. Then do the same for `binary_search`. You now have the two functions every programmer carries; Python's own `in` and `index` are these, in dress clothes.\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 }