{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "---\n",
    "title: \"Notebook 7: Algorithms, Complexity & the Limits of Computation\"\n",
    "subtitle: \"COMP 1150 — Computer Science Concepts\"\n",
    "author: \"Brendan Shea, PhD\"\n",
    "date: last-modified\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_header": true
   },
   "source": [
    "<!-- COLAB-BADGE -->\n",
    "[![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/brendanpshea/computing_concepts_python/blob/main/v2/notebooks/COMP1150_NB07_SearchingSorting.ipynb)  \n",
    "[Download .ipynb](https://raw.githubusercontent.com/brendanpshea/computing_concepts_python/main/v2/notebooks/COMP1150_NB07_SearchingSorting.ipynb) · [View on GitHub](https://github.com/brendanpshea/computing_concepts_python/blob/main/v2/notebooks/COMP1150_NB07_SearchingSorting.ipynb)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "📺 **Lecture video:** *(link coming soon)*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Learning Outcomes\n",
    "\n",
    "By the end of this notebook, you will be able to:\n",
    "\n",
    "- **Perform** a **linear search** over a list and explain when it is the only option.\n",
    "- **Perform** a **binary search** over a *sorted* list, and explain why the list must be sorted first.\n",
    "- **Reason** informally about **running time** using Big-O names — `O(n)`, `O(log n)`, `O(n²)`, `O(n log n)` — to describe how work grows as data grows.\n",
    "- **Hand-code** one simple sorting algorithm (selection sort) and **describe** how a faster one (merge sort) works.\n",
    "- **Use** Python's built-in `sorted()` and `.sort()` with a `key=` function to sort numbers, strings, and objects.\n",
    "- **Describe** a **Turing machine** as a thought experiment and say what it means for a problem to be **computable**.\n",
    "- **Explain** the **halting problem** and what it means for a problem to be **undecidable**.\n",
    "- **Discuss** **P vs. NP** as the cultural idea \"easy to check, hard to solve,\" and connect these limits to what modern AI / LLMs can and cannot do *in principle*.\n",
    "\n",
    "*Maps to course LOs: 4, 13*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Problem: The Queen Wants It *Found*, and *Now*\n",
    "\n",
    "The Queen of Hearts keeps an enormous, hopelessly shuffled deck. Every card is a guest, a gardener, or a tart in her ledger. When she wants a particular Knave, she expects him produced *instantly* — and \"Off with their heads!\" is the penalty for being slow.\n",
    "\n",
    "**Alice** has been handed the deck and told to make it *findable*. The **White Rabbit**, forever checking his pocket-watch and muttering \"no time, no time!\", will be our guide to the question that haunts every search: *how many steps did that take?*\n",
    "\n",
    "But by the end of this notebook a stranger question appears, whispered by the **Cheshire Cat** from his branch: are there tasks that **no** algorithm — and **no** computer, ever — can finish at all?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Roadmap\n",
    "\n",
    "This notebook comes in two halves.\n",
    "\n",
    "**Part 1 — Making things fast.** We start with the two ways to *find* a card: checking every one (**linear search**) versus repeatedly cutting the deck in half (**binary search**). Binary search only works on a *sorted* deck, so we learn to **sort**. Along the way the White Rabbit teaches us to *count steps* with **Big-O notation**.\n",
    "\n",
    "**Part 2 — What can't be made fast, or done at all.** Some problems are merely slow (the Queen's impossible puzzles — **P vs. NP**). Others can *never* be solved by any program, no matter how clever (the **halting problem** and **undecidability**). We close by asking what all this means for modern **AI and large language models**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 1 — Searching, Sorting & How Long It Takes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linear Search: Check Every Card\n",
    "\n",
    "Alice's deck is **shuffled** — no order at all. She is told to find the **Knave of Hearts**. With a random pile, she has no shortcut: she must turn over the top card, check it, and if it is not the Knave, move to the next. She keeps going until she finds him or runs out of cards.\n",
    "\n",
    "That is a **linear search**: walk through the items one at a time, in order, comparing each to your target."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Syntax of a Linear Search\n",
    "\n",
    "A search function takes the *collection* to look through and the *target* to look for. It returns **where** the target is (its index) or a signal that it is not there.\n",
    "\n",
    "What should that \"not there\" signal be? You will often see `-1` in textbooks — a habit borrowed from languages like C and Java. **Be careful: in Python, `-1` is a perfectly valid index** (`items[-1]` is the *last* item). So if a caller forgets to check and writes `items[result]`, a `-1` \"not found\" will silently hand them the last card instead of an error. The safer, more Pythonic choices are:\n",
    "\n",
    "- **`return None`** — there is no `items[None]`, so a misuse fails loudly and immediately.\n",
    "- **raise an error** — this is what the built-in `list.index()` does (it raises `ValueError`).\n",
    "\n",
    "We will use `None`.\n",
    "\n",
    "```python\n",
    "def linear_search(items, target):\n",
    "    for index in range(len(items)):\n",
    "        if items[index] == target:\n",
    "            return index        # found it — report the position\n",
    "    return None                 # checked everything — not here\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def linear_search(items, target):\n",
    "    \"\"\"Return the index of target in items, or None if it is not present.\"\"\"\n",
    "    for index in range(len(items)):\n",
    "        if items[index] == target:\n",
    "            return index\n",
    "    return None\n",
    "\n",
    "\n",
    "# Alice's shuffled deck of guests (no order at all)\n",
    "guests = [\"March Hare\", \"Dormouse\", \"Knave of Hearts\",\n",
    "          \"Duchess\", \"Mad Hatter\", \"Gryphon\"]\n",
    "\n",
    "print(linear_search(guests, \"Knave of Hearts\"))   # found at index 2\n",
    "print(linear_search(guests, \"Cheshire Cat\"))      # not invited -> None\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Understanding the Code\n",
    "\n",
    "- `for index in range(len(items))` walks the positions `0, 1, 2, …` in order.\n",
    "- `if items[index] == target` compares the card at that position to the one we want.\n",
    "- The moment we find a match we `return index` — we stop early, we do not keep looking.\n",
    "- If the loop finishes without ever matching, we fall through to `return None`. That `None` is our **sentinel value**: a special return that means \"not found.\" (As noted above, `None` is safer here than `-1`, which Python would accept as the last index.)\n",
    "\n",
    "Notice the cost: if the Knave is near the *bottom* of the deck, Alice turns over nearly every card. If he is not in the deck at all, she turns over **every single one**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 🔮 Predict Before You Run\n",
    "\n",
    "The deck has **12** guests. Before running the next cell, predict:\n",
    "\n",
    "1. If the target is the **last** guest, how many comparisons does `linear_search` make?\n",
    "2. If the target is **not in the deck at all**, how many comparisons does it make?\n",
    "3. On average, for a random target that *is* present, roughly how many?"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "deck12 = [f\"Card {i}\" for i in range(1, 13)]   # \"Card 1\" ... \"Card 12\"\n",
    "\n",
    "def linear_search_counting(items, target):\n",
    "    comparisons = 0\n",
    "    for index in range(len(items)):\n",
    "        comparisons += 1\n",
    "        if items[index] == target:\n",
    "            return index, comparisons\n",
    "    return None, comparisons\n",
    "\n",
    "print(\"last item:   \", linear_search_counting(deck12, \"Card 12\"))   # 12 comparisons\n",
    "print(\"missing item:\", linear_search_counting(deck12, \"Card 99\"))   # 12 comparisons\n",
    "print(\"first item:  \", linear_search_counting(deck12, \"Card 1\"))    # 1 comparison\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**The pattern:** worst case is *n* comparisons for a deck of *n* cards. Best case is 1 (lucky first card). On average, about *n*/2. The thing that matters most is that the work **grows in step with the size of the deck** — double the deck, double the worst-case work. Hold that thought; the White Rabbit will name it soon."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ✏️ Your Turn — Alice's Linear Search\n",
    "\n",
    "Alice has an **unsorted** guest list. Complete `find_guest(guests, name)` so it returns the *position* of a guest, or the string `\"not invited\"` if the name is absent. Test it on a hit and a miss."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "#| eval: false\n",
    "guests = [\"Dormouse\", \"Mad Hatter\", \"March Hare\", \"Gryphon\", \"Mock Turtle\"]\n",
    "\n",
    "def find_guest(guests, name):\n",
    "    # TODO: walk the list; return the index if found, else \"not invited\"\n",
    "    pass\n",
    "\n",
    "print(find_guest(guests, \"Gryphon\"))      # expected: 3\n",
    "print(find_guest(guests, \"Cheshire Cat\")) # expected: not invited"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Search: Cut the Deck in Half (Again and Again)\n",
    "\n",
    "The White Rabbit is appalled at all this card-turning. \"There's a faster way!\" he insists — *but only if the deck is already sorted.*\n",
    "\n",
    "Think about how you find a word in a dictionary. You do not start at \"aardvark\" and read every word. You flip to the **middle**, see whether your word is earlier or later, and throw away the half it cannot be in. Then you repeat on what remains. Each look **halves** the search.\n",
    "\n",
    "That is **binary search**, and it requires the data to be **in order**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Syntax of a Binary Search\n",
    "\n",
    "We track the slice of the deck still in play with two markers: `low` and `high`. We look at the `mid`dle card. If it is our target, done. If our target is *bigger*, the answer must be in the upper half, so we move `low` past `mid`. If it is *smaller*, we move `high` below `mid`. As with linear search, we return `None` when the card is not there.\n",
    "\n",
    "```python\n",
    "def binary_search(sorted_items, target):\n",
    "    low = 0\n",
    "    high = len(sorted_items) - 1\n",
    "    while low <= high:\n",
    "        mid = (low + high) // 2\n",
    "        if sorted_items[mid] == target:\n",
    "            return mid\n",
    "        elif sorted_items[mid] < target:   # target is in the upper half\n",
    "            low = mid + 1\n",
    "        else:                              # target is in the lower half\n",
    "            high = mid - 1\n",
    "    return None\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def binary_search(sorted_items, target):\n",
    "    \"\"\"Return the index of target in a SORTED list, or None if not present.\n",
    "    Prints each step so we can watch the search space shrink.\"\"\"\n",
    "    low = 0\n",
    "    high = len(sorted_items) - 1\n",
    "    while low <= high:\n",
    "        mid = (low + high) // 2\n",
    "        print(f\"  looking in positions {low}..{high}, checking position {mid} ({sorted_items[mid]!r})\")\n",
    "        if sorted_items[mid] == target:\n",
    "            return mid\n",
    "        elif sorted_items[mid] < target:\n",
    "            low = mid + 1\n",
    "        else:\n",
    "            high = mid - 1\n",
    "    return None\n",
    "\n",
    "\n",
    "def report(sorted_items, target):\n",
    "    \"\"\"Search and print a clear, non-contradictory result.\"\"\"\n",
    "    result = binary_search(sorted_items, target)\n",
    "    if result is None:\n",
    "        print(f\"  -> {target!r} is not in the deck\")\n",
    "    else:\n",
    "        print(f\"  -> found {target!r} at index {result}\")\n",
    "\n",
    "\n",
    "# The deck must be SORTED first\n",
    "sorted_guests = sorted([\"March Hare\", \"Dormouse\", \"Knave of Hearts\",\n",
    "                        \"Duchess\", \"Mad Hatter\", \"Gryphon\"])\n",
    "print(\"Sorted deck:\", sorted_guests)\n",
    "\n",
    "print(\"\\nSearching for 'Mad Hatter':\")\n",
    "report(sorted_guests, \"Mad Hatter\")\n",
    "\n",
    "print(\"\\nSearching for 'Cheshire Cat':\")\n",
    "report(sorted_guests, \"Cheshire Cat\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Understanding the Code\n",
    "\n",
    "- `low` and `high` mark the **range still worth searching**. Everything outside it has been ruled out.\n",
    "- `mid = (low + high) // 2` picks the middle position (integer division throws away the remainder).\n",
    "- The three branches: **equal** → found; **mid is too small** → answer must be to the right, so `low = mid + 1`; **mid is too big** → answer is to the left, so `high = mid - 1`.\n",
    "- `while low <= high` keeps going until the range is empty. When `low` passes `high`, there is nothing left, so we `return None`.\n",
    "- The little `report` helper checks `if result is None` so the printout never says the contradictory \"found at index None\" — it says plainly that the card is not in the deck.\n",
    "\n",
    "Run the printed steps again: each line throws away *half* of what remained. A deck of 1,000 cards is found in about **10** steps, not 1,000."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Picture It: Halving the Search Space\n",
    "\n",
    "Binary search on 16 cards needs at most 4 steps, because 16 halves to 8, to 4, to 2, to 1. The diagram below shows that shrinking range."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "#| echo: false\n",
    "#@title 🔍 Binary search halving — diagram code (click to show)\n",
    "from graphviz import Digraph\n",
    "\n",
    "g = Digraph()\n",
    "g.attr(rankdir=\"LR\")\n",
    "g.attr(\"node\", shape=\"box\", style=\"filled\", fillcolor=\"#e3f2fd\", fontname=\"Helvetica\")\n",
    "steps = [\"16 cards left\", \"8 cards left\", \"4 cards left\", \"2 cards left\", \"1 card — found\"]\n",
    "for s in steps:\n",
    "    g.node(s, s)\n",
    "for a, b in zip(steps, steps[1:]):\n",
    "    g.edge(a, b, label=\"  toss half\")\n",
    "g\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A Trap: Binary Search on an *Unsorted* List\n",
    "\n",
    "Binary search trusts that the deck is sorted. Give it a shuffled deck and it will happily rule out the *wrong* half — and report \"not found\" for a card that is sitting right there. It fails **silently**, which is the worst kind of failure."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "shuffled = [\"March Hare\", \"Dormouse\", \"Knave of Hearts\",\n",
    "            \"Duchess\", \"Mad Hatter\", \"Gryphon\"]   # NOT sorted\n",
    "\n",
    "# The Knave IS in the list, but binary search may not find him:\n",
    "result = binary_search(shuffled, \"Knave of Hearts\")\n",
    "print(\"\\nResult on the unsorted deck:\", result, \"(should have been found!)\")\n",
    "print(\"Lesson: always sort before you binary-search.\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ✏️ Your Turn — The Caterpillar's Binary Search\n",
    "\n",
    "The Caterpillar hands you a **sorted** list and asks you to implement `binary_search(nums, target)` from scratch — return the index, or `None` if it's absent. Keep two markers, `low` and `high`, and check the middle each pass. (Stuck on the `low`/`high` updates? That's the classic off-by-one — trace it by hand on a small list until it clicks.)"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "#| eval: false\n",
    "sorted_nums = [1, 3, 4, 7, 9, 12, 15, 20, 25]\n",
    "\n",
    "def binary_search(nums, target):\n",
    "    # TODO: implement binary search; return the index, or None if not found\n",
    "    pass\n",
    "\n",
    "print(binary_search(sorted_nums, 12))   # expected: 5\n",
    "print(binary_search(sorted_nums, 8))    # expected: None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Why Order Matters: Counting the Rabbit's Steps\n",
    "\n",
    "The White Rabbit does not care about *seconds* — those depend on whose computer you use. He cares about **how the number of steps grows as the deck grows**. Computer scientists write this with **Big-O notation**. You can read `O(...)` as *\"on the order of...\"*\n",
    "\n",
    "The four you will meet most often, from wonderful to dreadful:\n",
    "\n",
    "| Big-O | Name | What it means | Our example |\n",
    "|---|---|---|---|\n",
    "| `O(1)` | constant | same work no matter the size | grabbing the top card |\n",
    "| `O(log n)` | logarithmic | each step throws away a *fraction* | **binary search** |\n",
    "| `O(n)` | linear | work grows in step with size | **linear search** |\n",
    "| `O(n log n)` | \"n log n\" | a good sort's cost | **merge sort**, `sorted()` |\n",
    "| `O(n²)` | quadratic | work grows with the *square* | **selection sort** (next) |\n",
    "\n",
    "Big-O ignores constants and small terms. We do not say \"3n + 7 steps\"; we say `O(n)`. The point is the **shape of the growth**, not the exact count."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "print(f\"{'deck size n':>14} | {'linear O(n)':>12} | {'binary O(log n)':>16}\")\n",
    "print(\"-\" * 48)\n",
    "for n in [16, 1024, 1_000_000, 1_000_000_000]:\n",
    "    linear = n                       # worst-case comparisons\n",
    "    binary = math.ceil(math.log2(n)) # worst-case comparisons\n",
    "    print(f\"{n:>14,} | {linear:>12,} | {binary:>16,}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Look at the bottom row. To find a card among a **billion**, linear search may check a billion; binary search checks about **30**. That gap is the whole reason we bother to sort."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Picture It: How Work Grows\n",
    "\n",
    "The same idea as a shape. As *n* grows, `O(n²)` shoots up, `O(n)` rises steadily, and `O(log n)` barely lifts off the floor."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "#| echo: false\n",
    "#@title 📈 Growth curves — diagram code (click to show)\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "ns = list(range(1, 31))\n",
    "fig, ax = plt.subplots(figsize=(6, 4))\n",
    "ax.plot(ns, [math.log2(n) for n in ns], label=\"O(log n)\")\n",
    "ax.plot(ns, ns, label=\"O(n)\")\n",
    "ax.plot(ns, [n * math.log2(n) for n in ns], label=\"O(n log n)\")\n",
    "ax.plot(ns, [n * n for n in ns], label=\"O(n²)\")\n",
    "ax.set_xlabel(\"input size n\")\n",
    "ax.set_ylabel(\"steps\")\n",
    "ax.set_title(\"How the work grows\")\n",
    "ax.set_ylim(0, 300)\n",
    "ax.legend()\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ✏️ Your Turn — Counting Steps, On Paper *(no coding)*\n",
    "\n",
    "You have a sorted list of **16** guests. In the **worst case**:\n",
    "\n",
    "1. How many comparisons does **linear search** make?\n",
    "2. How many does **binary search** make? (Hint: how many times can you halve 16?)\n",
    "3. In two or three sentences, explain *why* binary search needs so many fewer — and what the deck must have that linear search did not require."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 💭 Think About It — When Does Speed Actually Matter?\n",
    "\n",
    "You've now counted how the work grows as the input gets bigger — linear search checks every card, binary search cuts the deck in half.\n",
    "\n",
    "- For a small list, linear and binary search both feel instant. At what scale does the difference start to actually matter? Think of real systems where the list is enormous.\n",
    "- A faster algorithm sometimes needs extra setup — binary search requires a *sorted* list. When is it worth paying that setup cost, and when would you just do the slow-but-simple thing?\n",
    "- Where in your own life have you felt the difference between something that scales well and something that grinds to a halt as it gets bigger — a line, a website, a group chat?\n",
    "\n",
    "There are no single right answers here — share a sentence or two on each."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sorting: Putting the Deck in Order\n",
    "\n",
    "Binary search needed a *sorted* deck. So how does Alice sort one in the first place? There are many sorting algorithms; we will write one by hand and *describe* a faster one.\n",
    "\n",
    "The hand-written one is **selection sort**, and its idea is exactly what it sounds like: *find the smallest card and put it first; from what's left, find the next smallest and put it second; repeat until the deck is in order.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Syntax of a Selection Sort\n",
    "\n",
    "The outer loop walks the position we are currently *filling*. The inner loop scans everything *after* it to find the smallest remaining card. Then one **swap** drops that card into place.\n",
    "\n",
    "```python\n",
    "def selection_sort(items):\n",
    "    for i in range(len(items)):\n",
    "        smallest = i\n",
    "        for j in range(i + 1, len(items)):\n",
    "            if items[j] < items[smallest]:\n",
    "                smallest = j\n",
    "        items[i], items[smallest] = items[smallest], items[i]   # swap into place\n",
    "    return items\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def selection_sort(items):\n",
    "    \"\"\"Sort items in place using selection sort, printing each pass.\"\"\"\n",
    "    for i in range(len(items)):\n",
    "        smallest = i\n",
    "        for j in range(i + 1, len(items)):\n",
    "            if items[j] < items[smallest]:\n",
    "                smallest = j\n",
    "        items[i], items[smallest] = items[smallest], items[i]\n",
    "        print(f\"  after pass {i + 1}: {items}\")\n",
    "    return items\n",
    "\n",
    "\n",
    "ranks = [7, 2, 10, 4, 1]\n",
    "print(\"start:        \", ranks)\n",
    "selection_sort(ranks)\n",
    "print(\"sorted:       \", ranks)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Understanding the Code\n",
    "\n",
    "- The outer loop variable `i` is the **slot being filled**: first the position that should hold the smallest card, then the next, and so on.\n",
    "- `smallest` starts as a *guess* (`i`) and the inner loop updates it whenever it finds something smaller in the unsorted tail.\n",
    "- The line with two assignments at once is a **swap**: Python lets you write `a, b = b, a` to exchange two values without a temporary variable.\n",
    "- Watch the printed passes: after each one, the front of the list is sorted and growing.\n",
    "\n",
    "**The cost:** for each of *n* slots, we scan the rest of the deck. That is roughly *n* × *n* work — `O(n²)`. Fine for a handful of cards, painful for millions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 🔮 Predict Before You Run\n",
    "\n",
    "Given the list `[5, 3, 8, 1, 9]`, what will it look like **after the first pass** of selection sort (after the smallest card is placed in slot 0)? Write down your guess, then run the cell."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "demo = [5, 3, 8, 1, 9]\n",
    "selection_sort(demo)   # watch only the FIRST printed pass to check your prediction\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ✏️ Your Turn — The Hatter's Selection Sort\n",
    "\n",
    "The tea party seats guests by **arrival time** (smaller number = arrived earlier). Use selection sort to order the list, printing it after each pass so the Hatter can watch it tidy itself."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "#| eval: false\n",
    "arrivals = [4, 1, 3, 2, 5]   # arrival times\n",
    "\n",
    "def selection_sort(items):\n",
    "    # TODO: selection sort, printing the list after each pass\n",
    "    pass\n",
    "\n",
    "selection_sort(arrivals)\n",
    "print(\"seated in order:\", arrivals)   # expected: [1, 2, 3, 4, 5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A Faster Idea: Merge Sort (Described, Not Coded)\n",
    "\n",
    "Selection sort is `O(n²)`. For a deck of a million, that is a *trillion* comparisons. Real systems use smarter sorts that run in `O(n log n)` — and the classic example is **merge sort**. We will *describe* it rather than code it, because the idea matters more than the implementation here.\n",
    "\n",
    "Merge sort uses **divide and conquer**:\n",
    "\n",
    "1. **Divide.** Split the deck into two halves. Split each half again. Keep splitting until every pile is a single card — and a single card is already \"sorted.\"\n",
    "2. **Conquer (merge).** Take two sorted piles and **merge** them into one sorted pile by repeatedly comparing the top card of each and taking the smaller. Merging two sorted piles is cheap and easy.\n",
    "3. **Combine upward.** Merge the small sorted piles into bigger sorted piles, and those into bigger ones, until the whole deck is one sorted pile.\n",
    "\n",
    "Why is it faster? There are about `log n` levels of splitting (you can only halve *n* about `log n` times), and each level does `O(n)` work to merge everything — so the total is `O(n log n)`. That is why `sorted()` can sort a million items in well under a second while selection sort would crawl."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Picture It: Divide and Merge\n",
    "\n",
    "Merge sort splits all the way down, then merges back up."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "#| echo: false\n",
    "#@title 🧩 Merge sort divide & merge — diagram code (click to show)\n",
    "from graphviz import Digraph\n",
    "\n",
    "g = Digraph()\n",
    "g.attr(\"node\", shape=\"box\", style=\"filled\", fillcolor=\"#fde8c8\", fontname=\"Helvetica\")\n",
    "# divide\n",
    "g.node(\"a\", \"[7, 2, 10, 4]\")\n",
    "g.node(\"b\", \"[7, 2]\")\n",
    "g.node(\"c\", \"[10, 4]\")\n",
    "g.node(\"d\", \"[7]\"); g.node(\"e\", \"[2]\"); g.node(\"f\", \"[10]\"); g.node(\"h\", \"[4]\")\n",
    "g.edge(\"a\", \"b\", label=\"split\"); g.edge(\"a\", \"c\", label=\"split\")\n",
    "g.edge(\"b\", \"d\"); g.edge(\"b\", \"e\"); g.edge(\"c\", \"f\"); g.edge(\"c\", \"h\")\n",
    "# merge\n",
    "g.attr(\"node\", fillcolor=\"#dff0d8\")\n",
    "g.node(\"m1\", \"[2, 7]\"); g.node(\"m2\", \"[4, 10]\"); g.node(\"m3\", \"[2, 4, 7, 10]\")\n",
    "g.edge(\"d\", \"m1\", label=\"merge\"); g.edge(\"e\", \"m1\")\n",
    "g.edge(\"f\", \"m2\", label=\"merge\"); g.edge(\"h\", \"m2\")\n",
    "g.edge(\"m1\", \"m3\", label=\"merge\"); g.edge(\"m2\", \"m3\")\n",
    "g\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Practical Tool: `sorted()` and `key=`\n",
    "\n",
    "In real programs nobody hand-writes selection sort. Python ships a fast `O(n log n)` sort built in. You meet it two ways: `sorted(items)` returns a **brand-new** sorted list, while `items.sort()` sorts the list **in place**. The real power comes from `key=`, which lets you sort by a *computed* value instead of the items themselves."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Syntax of `sorted()` with a Key\n",
    "\n",
    "```python\n",
    "sorted(items)                       # ascending order, returns a NEW list\n",
    "sorted(items, reverse=True)         # descending order\n",
    "items.sort()                        # sorts in place, returns None\n",
    "sorted(items, key=some_function)    # sort by what some_function returns for each item\n",
    "```\n",
    "\n",
    "A `key` function receives **one** item and returns the value to sort *by*. A `lambda` is a tiny one-line function, handy here: `lambda c: c.rank` means \"given a card `c`, sort by its `rank`.\"\n"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Numbers and strings: the obvious cases\n",
    "print(sorted([7, 2, 10, 4, 1]))                 # [1, 2, 4, 7, 10]\n",
    "print(sorted([\"Hatter\", \"Alice\", \"Duchess\"]))   # alphabetical\n",
    "print(sorted([7, 2, 10, 4, 1], reverse=True))   # [10, 7, 4, 2, 1]\n",
    "\n",
    "\n",
    "# Sorting OBJECTS with key= (a Card class, picking up where Notebook 6 left off)\n",
    "class Card:\n",
    "    def __init__(self, name, rank):\n",
    "        self.name = name\n",
    "        self.rank = rank\n",
    "    def __repr__(self):\n",
    "        return f\"{self.name}({self.rank})\"\n",
    "\n",
    "hand = [Card(\"Knave\", 11), Card(\"Two\", 2), Card(\"Queen\", 12), Card(\"Seven\", 7)]\n",
    "\n",
    "print(\"\\nby rank: \", sorted(hand, key=lambda c: c.rank))   # 2, 7, 11, 12\n",
    "print(\"by name: \", sorted(hand, key=lambda c: c.name))     # alphabetical by name\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Understanding the Code\n",
    "\n",
    "- `sorted(...)` hands back a **new** list and leaves the original untouched; `.sort()` rearranges the original and returns `None` (a common beginner bug: writing `x = mylist.sort()` and getting `None`).\n",
    "- `reverse=True` flips the order.\n",
    "- `key=lambda c: c.rank` tells `sorted` *what to compare*. Python calls that function on each card, gets back a rank number, and sorts by those numbers — without losing track of which whole card each number came from.\n",
    "- This is the everyday tool: you almost never implement a sort, but you constantly choose *what to sort by*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Picture It: Which Method, When?\n",
    "\n",
    "| Tool | Needs sorted input? | Changes the list? | Big-O | Reach for it when… |\n",
    "|---|---|---|---|---|\n",
    "| **Linear search** | no | no | `O(n)` | data is unsorted or tiny |\n",
    "| **Binary search** | **yes** | no | `O(log n)` | data is sorted and you search a lot |\n",
    "| **Selection sort** | no | sorts in place | `O(n²)` | learning / very small lists |\n",
    "| **Merge sort** | no | returns sorted | `O(n log n)` | you need a guaranteed-fast sort |\n",
    "| **`sorted()` / `.sort()`** | no | new list / in place | `O(n log n)` | real code — almost always |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ✏️ Your Turn — Sorting the Knave's Tarts with `key=`\n",
    "\n",
    "The Knave has a list of `Tart` objects, each with a `flavor` (string) and a `count` (int). Use `sorted(..., key=...)` to produce **two** orderings: one by `count` (most tarts last), and one alphabetically by `flavor`. Use the built-in — don't write your own sort."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "#| eval: false\n",
    "class Tart:\n",
    "    def __init__(self, flavor, count):\n",
    "        self.flavor = flavor\n",
    "        self.count = count\n",
    "    def __repr__(self):\n",
    "        return f\"{self.flavor}x{self.count}\"\n",
    "\n",
    "tarts = [Tart(\"strawberry\", 12), Tart(\"apple\", 3), Tart(\"plum\", 7)]\n",
    "\n",
    "by_count  = None   # TODO: sorted(tarts, key=...) ascending by count\n",
    "by_flavor = None   # TODO: sorted(tarts, key=...) alphabetically by flavor\n",
    "\n",
    "print(\"by count: \", by_count)\n",
    "print(\"by flavor:\", by_flavor)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 2 — The Limits of Computation\n",
    "\n",
    "So far, every problem has had a fast-enough answer: search smarter, sort first, count the steps. Now the **Cheshire Cat** fades into view, all grin, and asks a different kind of question. Not *\"how long will it take?\"* but: **\"Are there questions a machine can never answer at all — no matter how clever the algorithm, no matter how fast the computer?\"**\n",
    "\n",
    "The astonishing answer, proved in 1936 by a mathematician named **Alan Turing**, is **yes**. This part is about *ideas*, not code. Read it like a set of philosophy puzzles."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A Machine Made of Almost Nothing: The Turing Machine\n",
    "\n",
    "Before there were computers, Turing asked: *what is the simplest possible device that could carry out any calculation a human follows by rote?* His answer was a machine so simple it sounds like a toy:\n",
    "\n",
    "- An endless **tape** divided into squares (imagine the Caterpillar's ribbon, unrolling forever).\n",
    "- A **head** that sits over one square and can **read** the symbol there, **write** a new symbol, and move one square **left** or **right**.\n",
    "- A tiny **rulebook**: \"if you are in state A and you read a 1, write a 0, move right, and switch to state B.\" A handful of such rules.\n",
    "\n",
    "That is the whole machine. No screen, no memory chips — just a tape, a head, and a list of if-then rules.\n",
    "\n",
    "Here is the shocking part. This ribbon-and-rulebook gadget can compute **anything** that your laptop, a supercomputer, or any future computer can compute. The claim that \"anything computable can be computed by a Turing machine\" is called the **Church–Turing thesis**. It is the reason we can talk about *computation* as a single universal idea, instead of a different idea for every brand of machine."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Picture It: The Tape, the Head, the Rulebook"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "#| echo: false\n",
    "#@title ⚙️ A Turing machine — diagram code (click to show)\n",
    "from graphviz import Digraph\n",
    "\n",
    "g = Digraph()\n",
    "g.attr(rankdir=\"LR\")\n",
    "g.attr(\"node\", shape=\"box\", style=\"filled\", fillcolor=\"#eef4ff\", fontname=\"Helvetica\")\n",
    "# the tape\n",
    "cells_tape = [\"...\", \"1\", \"0\", \"1\", \"1\", \"0\", \"...\"]\n",
    "for i, sym in enumerate(cells_tape):\n",
    "    fill = \"#fff3cd\" if i == 3 else \"white\"   # head over the middle cell\n",
    "    g.node(f\"t{i}\", sym, fillcolor=fill)\n",
    "for i in range(len(cells_tape) - 1):\n",
    "    g.edge(f\"t{i}\", f\"t{i+1}\", arrowhead=\"none\")\n",
    "g.node(\"head\", \"HEAD\\n(read / write / move)\", fillcolor=\"#fde8c8\")\n",
    "g.edge(\"head\", \"t3\")\n",
    "g.node(\"rules\", \"RULEBOOK\\nif state A & read 1\\n-> write 0, move R, go to B\", shape=\"note\", fillcolor=\"#dff0d8\")\n",
    "g\n"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# A tiny illustrative Turing machine: flip every bit on the tape, left to right.\n",
    "def run_tiny_tm(tape):\n",
    "    \"\"\"Move right across the tape, flipping 1<->0, until we run off the end.\"\"\"\n",
    "    tape = list(tape)\n",
    "    head = 0\n",
    "    while head < len(tape):\n",
    "        tape[head] = \"0\" if tape[head] == \"1\" else \"1\"   # write\n",
    "        head += 1                                        # move right\n",
    "    return \"\".join(tape)\n",
    "\n",
    "print(\"before:\", \"110100\")\n",
    "print(\"after: \", run_tiny_tm(\"110100\"))   # every bit flipped\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 💬 Discussion\n",
    "\n",
    "1. Why would anyone study such a slow, silly machine instead of a real computer? What do we *gain* by stripping computation down to a tape and a rulebook?\n",
    "2. The Church–Turing thesis says every computer is, deep down, \"just\" a Turing machine. Does that match your intuition about your phone? What would it mean if it were true?\n",
    "3. If a Turing machine can compute anything any computer can, what *kind* of question could possibly be off-limits to it? (We are about to find one.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Halting Problem: A Question No Program Can Answer\n",
    "\n",
    "The White Rabbit is forever running. Alice wonders: *will he ever stop, or run forever?* For a program, this is a real and important question. Some programs finish (they **halt**); some get stuck in a loop and run forever. Wouldn't it be wonderful to have a tool that, given **any** program and its input, always told you the truth: *\"this one halts\"* or *\"this one loops forever\"*?\n",
    "\n",
    "Call that dream tool `halts(program, input)`. Turing proved it **cannot exist**. Not \"we haven't built it yet\" — it *cannot* exist, ever. Here is the idea, in plain English:\n",
    "\n",
    "Suppose `halts` existed. Then we could build a mischievous program, call it **Contrary**, that does this: *\"Ask `halts` what I would do. If `halts` says I halt, then loop forever. If `halts` says I loop forever, then halt immediately.\"* Now run **Contrary** on itself. Whatever `halts` predicts, Contrary does the **opposite** — so `halts` is wrong. Since we built Contrary using only `halts`, the only escape is that `halts` never existed in the first place.\n",
    "\n",
    "This is the same self-referential trick as \"This sentence is false.\" The halting problem is **undecidable**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What \"Undecidable\" Really Means\n",
    "\n",
    "Be careful: **undecidable does not mean hard.** A hard problem is one we can solve, just slowly. An *undecidable* problem is one for which **no algorithm can ever give the right answer in every case** — not with a faster chip, not with more memory, not with a cleverer programmer.\n",
    "\n",
    "The halting problem is not a lonely exception. Many real questions reduce to it. *\"Will this program ever crash?\"* *\"Does this code contain a virus that will eventually trigger?\"* *\"Will these two programs always produce the same output?\"* In full generality, **no** program can answer these for all inputs. The best real tools (antivirus, type checkers, verifiers) settle for being *usually* right, or right on a *restricted* set of cases."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 💬 Discussion\n",
    "\n",
    "1. In your own words, what is the difference between *\"impossible for now\"* and *\"impossible in principle\"*? Give a non-computing example of each.\n",
    "2. Imagine you are writing the autograder for this course, and you want it to detect any student program that has an infinite loop. Why does the halting problem mean you can never make that detector perfect? What could you do instead?\n",
    "3. The proof relies on a program asking about *itself*. Where else have you seen self-reference create a paradox?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## P vs. NP: Easy to Check, Hard to Solve\n",
    "\n",
    "Not every limit is about *impossibility*. Some problems are perfectly solvable but seem to require a hopeless amount of work. The Queen empties a sack of a thousand jigsaw pieces and roars, \"Assemble it — perfectly — or off with your head!\"\n",
    "\n",
    "Notice two very different jobs:\n",
    "\n",
    "- **Checking** a finished puzzle is *easy*: glance at it, see that every piece fits. Quick.\n",
    "- **Finding** the solution from scratch may be *brutal*: in the worst case you try an astronomical number of arrangements.\n",
    "\n",
    "Computer scientists capture this with two groups of problems:\n",
    "\n",
    "- **P** — problems we can **solve** quickly (in a reasonable, `O(n^k)`-ish number of steps). Searching and sorting live here.\n",
    "- **NP** — problems where we can **check** a proposed answer quickly, even if *finding* it might be slow. The jigsaw, scheduling 500 classes without conflicts, packing a truck optimally, solving a giant Sudoku.\n",
    "\n",
    "The famous open question is: **does P = NP?** That is, if you can *check* an answer fast, can you always *find* one fast too? Almost everyone believes **P ≠ NP** (finding is genuinely harder than checking), but **nobody has proved it.** It is one of the seven Millennium Prize Problems — there is a literal **\\$1,000,000** waiting for a proof either way."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 💬 Discussion\n",
    "\n",
    "1. Describe an everyday task that is **hard to do but easy to check** that it was done right. Why does that gap feel familiar?\n",
    "2. Much of modern encryption relies on a problem being hard to *solve* but easy to *check*. If someone proved **P = NP** tomorrow with a practical method, why might a lot of internet security suddenly break?\n",
    "3. \"Hard for any computer\" (P vs. NP) and \"impossible for any computer\" (the halting problem) sound similar but are *not* the same. In your own words, what is the difference?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What This Means for AI and LLMs\n",
    "\n",
    "It is tempting to think a powerful enough AI will eventually solve *everything*. The limits in this notebook say otherwise — and the distinction is worth getting right.\n",
    "\n",
    "- **An LLM is still computation.** A large language model runs on ordinary computers, so it cannot escape undecidability. There is **no** AI, however large, that can correctly decide whether *any* program halts. That limit is mathematical, not a matter of training data or model size.\n",
    "- **Some limits are about impossibility; others are about cost.** P vs. NP–style problems are *allowed* to have solutions — they are just expensive. An AI might find good *approximate* answers fast (and often does), but \"found a decent schedule\" is not the same as \"proved this is the best possible one.\"\n",
    "- **Be precise about what LLMs are bad at.** It is easy to blur two very different things:\n",
    "  - *Impossible in principle* — e.g., a perfect universal halting-detector. No program, AI or not, can do this.\n",
    "  - *Hard or unreliable in practice* — e.g., guaranteeing a proof is correct, never hallucinating a fact, or producing a genuinely optimal solution. These are real weaknesses, but they are engineering and reliability problems, not mathematical impossibilities.\n",
    "\n",
    "The healthy stance is neither hype nor despair: AI is a remarkable tool *within* the space of computable, tractable problems, and the theory tells us exactly where the hard walls are."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 💬 Discussion\n",
    "\n",
    "1. A headline claims, \"AI will soon solve any problem we throw at it.\" Using the halting problem and P vs. NP, write a careful one-paragraph response.\n",
    "2. What is the difference between a task an LLM is merely **bad at** and a task that is **mathematically impossible** for *any* program? Give one example of each.\n",
    "3. Where, in your own use of AI tools, should you stay skeptical of the assumption that \"the AI will just figure it out\"?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 💬 Discussion — The Cheshire Cat's Riddle\n",
    "\n",
    "The Cheshire Cat grins: *\"Some of my riddles are merely slow to answer. One of them can never be answered at all.\"*\n",
    "\n",
    "In your own words, and with an everyday analogy of your choosing, explain the difference between:\n",
    "\n",
    "- a problem that is **undecidable** (like the halting problem), and\n",
    "- a problem that is merely **hard** (an NP problem like the giant jigsaw).\n",
    "\n",
    "Then name **one place this distinction should change how much we trust an AI system**. There's no single right answer — share your analogy and reasoning, and respond to a classmate whose analogy differs from yours."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ✏️ Capstone — The Great Wonderland Race (AI-Assisted)\n",
    "\n",
    "Time to put the last two notebooks into one small game. You'll build a **race**: several characters, each with their own stats, run against each other; you **bet** on a winner; then the results are shown as a **leaderboard, sorted fastest to slowest**. It reviews **objects** (Notebook 6 — each racer is an object with attributes) and the star skill of *this* notebook (**`sorted()` with `key=`**, to rank the finishers).\n",
    "\n",
    "The default is a Wonderland race — the White Rabbit, the Mad Hatter, the Cheshire Cat — but **pick your own**: horses, robots, snails, your friends as superheroes, anything that can race.\n",
    "\n",
    "**How the game works, start to finish:**\n",
    "\n",
    "1. Each **racer is an object** with a few stats — say `speed`, `stamina`, and a dash of `luck`.\n",
    "2. Each racer's **finish time** is computed from those stats — give faster racers an edge, but let luck shake things up so the same one doesn't always win.\n",
    "3. The player **bets** on a racer by name.\n",
    "4. The finishers are **sorted by time** with `sorted(..., key=...)` and printed as a leaderboard.\n",
    "5. The game says whether the bet paid off.\n",
    "\n",
    "**Step 1 — Design it first (before the AI).** In a markdown cell, jot down: your theme, your 3–5 racers and their stats, how a racer's finish time is computed from its stats, and how the bet wins or loses.\n",
    "\n",
    "**Step 2 — Turn your design into a prompt.** Fill the blanks and send it to Gemini (or Claude / ChatGPT):\n",
    "\n",
    "> *Write a small race game in Python for Google Colab. Theme: **[your theme]**. Define a `Racer` class with a name and these stats: **[your stats]**. Create a list of **[number]** racers. Give each racer a method that computes its finish time from its stats plus a little randomness. Ask the player to bet on one racer by name. Run the race, then use `sorted(..., key=...)` to print a leaderboard from first place to last, and say whether the bet won. Keep it short and beginner-readable, with a comment on each part.*\n",
    "\n",
    "**Step 3 — Get the bones working, then test.** Paste it into the cell below and **run it now**. Get the simplest version working first — two racers, a finish time each, sorted into an order — and check the leaderboard by hand before adding more.\n",
    "\n",
    "**Step 4 — Add the bells and whistles.** Once a basic race runs, add **one or two**, testing after each: a `luck` stat that can upset the favourite, different racer *types* via a subclass (a `Sprinter` that starts fast, a `Stayer` with high stamina — that's inheritance from Notebook 6), payout odds on the bet, or a best-of-three series.\n",
    "\n",
    "**Step 5 — Check your work.** Run it a few times. Does the **leaderboard always come out in the right order** (the slowest time should be last)? Try an empty racer list, or a bet on a name that isn't running — does the game cope, or crash?\n",
    "\n",
    "**Step 6 — Reflect.** In a markdown cell, write 2–3 sentences: which Notebook 6 idea (an object? a method? inheritance?) made the racers easy to build, and where did `sorted(key=...)` save you from writing a sort by hand?\n",
    "\n",
    "Remember the course rule: *AI is a fast first draft. You verify.*"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "#| eval: false\n",
    "# ✏️ Paste your AI-built race game here, then run it and fix what's broken."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Key Terms\n",
    "\n",
    "- **Algorithm** — a step-by-step procedure for solving a problem.\n",
    "- **Linear search** — checking items one by one; `O(n)`.\n",
    "- **Binary search** — repeatedly halving a *sorted* list; `O(log n)`.\n",
    "- **Sentinel value** — a special return (we use `None`) meaning \"not found.\" Avoid `-1` in Python, since it is a valid (negative) index.\n",
    "- **Big-O notation** — a description of how an algorithm's work grows with input size.\n",
    "- **`O(1)`, `O(log n)`, `O(n)`, `O(n log n)`, `O(n²)`** — constant, logarithmic, linear, \"n log n,\" and quadratic growth.\n",
    "- **Selection sort** — a simple `O(n²)` sort: repeatedly select the smallest remaining item.\n",
    "- **Merge sort** — a fast `O(n log n)` divide-and-conquer sort.\n",
    "- **Swap** — exchanging two values, e.g. `a, b = b, a`.\n",
    "- **In-place** — rearranging a list without making a new one.\n",
    "- **Key function** — a function passed to `sorted(..., key=...)` that returns the value to sort by.\n",
    "- **Turing machine** — a minimal tape-and-rulebook model of computation.\n",
    "- **Church–Turing thesis** — the idea that anything computable can be computed by a Turing machine.\n",
    "- **Computable** — solvable by some algorithm.\n",
    "- **Halting problem** — deciding whether an arbitrary program halts; proven impossible.\n",
    "- **Undecidable** — no algorithm can solve every case, even in principle.\n",
    "- **P** — problems solvable quickly.\n",
    "- **NP** — problems whose answers can be *checked* quickly.\n",
    "- **P vs. NP** — the open question of whether fast-to-check implies fast-to-solve.\n",
    "- **Intractable** — solvable in principle but requiring impractically much work."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Summary\n",
    "\n",
    "**Part 1 — speed.** Finding something is slow if you check everything (**linear search**, `O(n)`) and fast if the data is **sorted** and you halve it each step (**binary search**, `O(log n)`). Sorting is what makes that speed possible: we hand-coded **selection sort** (`O(n²)`) and described the faster **merge sort** (`O(n log n)`), then met the real-world tool, `sorted()` with `key=`. **Big-O** lets us compare strategies by how their work *grows*.\n",
    "\n",
    "**Part 2 — limits.** Some problems are merely expensive: **NP** problems are easy to *check* but seem hard to *solve*, and whether **P = NP** is a famous open question. Other problems are *impossible* for any program: the **halting problem** is **undecidable**, a wall no computer — and no AI — can ever cross. Knowing the difference between \"slow,\" \"intractable,\" and \"impossible\" is part of thinking clearly about what computers, and AI, can really do."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What's Next\n",
    "\n",
    "**Notebook 8 — Software Engineering: SDLC, Git & AI-Assisted Development.** How real software gets built: the development lifecycle, Waterfall vs. Agile, using Git and GitHub from Colab, AI-assisted workflows (spec → code → test → review), and the basics of testing."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.13.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}