Week 13 Coding Lab: The Lost-and-Found Tag Finder

Part 1 — The Big Picture

This week you learned that linear search checks items one at a time from the front and works on any list, that binary search compares the target with the middle item of a sorted list and throws away half on each pass, that a comparison counter measures work the same way on every machine, that selection sort swaps the smallest remaining item forward on every pass, and that Big-O names how a step count grows when the list doubles. In this lab you put those ideas to work for an illustrative campus lost-and-found that files its items by tag number. You predict what six short programs print, run them, and study every gap between your prediction and the run. Then you read three broken searches, fix each with the smallest change that works, write a short program that shows how binary search's work grows, and check a chatbot's answers to the same questions by running the code, because a chatbot predicts likely text and does not run your program.

Time budget: Plan for about 90 minutes.

Part 2 — The Task

Guiding question: For the lost-and-found's tag lists, which of these six predictions about searching and sorting will you get wrong, and how will each run show you whether a search found the tag, how many comparisons it made, and whether the list met binary search's sorted-list precondition?

Workshop data: Lost-and-found tag numbers: six programs to trace, three broken searches, and a growth program

Source: Six short Python programs, three broken programs, and one program you write, all about an illustrative campus lost-and-found and printed in full in Part 4; the lost-and-found and its tag numbers are invented and describe no real place or person.

• Rows: 10 programs in all: 6 programs to trace in the first table, 3 broken programs in the second table, and 1 program you write for the third table
• Lists: a sorted list of 10 tag numbers and an unsorted list of 6 tag numbers, both printed in full in the programs
• Language: Python 3, run in a free browser runner; no file to download and nothing to install

Part 3 — Materials & Procedure

Tools and materials

• A free browser-based Python runner (an online editor that runs Python 3 with no account and nothing to install), Python Tutor at pythontutor.com for step-by-step visualization, the official Python documentation at docs.python.org, and one approved chatbot used as a pair-programmer whose code the student runs before trusting

Ways of working

• write-run-and-verify
• trace-and-predict-output
• find-and-fix-the-bug

Procedure

1. Open a free browser Python runner in one tab and Python Tutor at pythontutor.com in another. In the runner, delete any sample code so the editor is blank. Type the counting linear search, the counting binary search, and the selection sort exactly as Chapter 13 prints them, with four spaces for each level of indentation, and keep them at the top of the editor for the whole lab. Tool: A free browser-based Python runner (an online editor that runs Python 3 with no account and nothing to install), Python Tutor at pythontutor.com for step-by-step visualization, the official Python documentation at docs.python.org, and one approved chatbot used as a pair-programmer whose code the student runs before trusting. Check: An editor holding the three functions, with a Run button and a separate output panel; pressing Run prints nothing yet.
2. In the first table in Part 4, write your prediction for each of the six programs before you run anything. Then add each program's lines below the functions, press Run, and copy the output into the Actual output column. Tool: A free browser-based Python runner (an online editor that runs Python 3 with no account and nothing to install), Python Tutor at pythontutor.com for step-by-step visualization, the official Python documentation at docs.python.org, and one approved chatbot used as a pair-programmer whose code the student runs before trusting. Check: Six actual outputs, one per row, each copied character for character from the output panel; at least one is likely to differ from your prediction.
3. Type each broken program from the second table into a blank editor and press Run. For an error, scroll to the bottom of the error message and copy the error type from its last line. For a program that runs, compare what it printed with what its description says it should print. Tool: A free browser-based Python runner (an online editor that runs Python 3 with no account and nothing to install), Python Tutor at pythontutor.com for step-by-step visualization, the official Python documentation at docs.python.org, and one approved chatbot used as a pair-programmer whose code the student runs before trusting. Check: The second table shows what each broken program printed, or the error type on its last line; two of the three run without any error but print the wrong thing.
4. Fix each broken program with the smallest change that makes it do what its description in Part 4 says, run the fixed version on every tag in the list and on one tag that is missing, and record the new output. Tool: A free browser-based Python runner (an online editor that runs Python 3 with no account and nothing to install), Python Tutor at pythontutor.com for step-by-step visualization, the official Python documentation at docs.python.org, and one approved chatbot used as a pair-programmer whose code the student runs before trusting. Check: Each fixed program runs without an error, finds every tag that is in the list at its correct index, and returns -1 for the missing tag.
5. Paste the counting binary search and row 2 of the first table into Python Tutor, click the button to visualize it, and step forward one line at a time. Write down lo, hi, and mid on every pass of the while loop. Tool: A free browser-based Python runner (an online editor that runs Python 3 with no account and nothing to install), Python Tutor at pythontutor.com for step-by-step visualization, the official Python documentation at docs.python.org, and one approved chatbot used as a pair-programmer whose code the student runs before trusting. Check: Python Tutor shows lo and hi closing in on the tag 42, with a new value of mid on each pass until the comparison matches.
6. Write your own short program: a for loop over the list sizes 25, 50, and 100 that builds the list 1 to that size and prints the size beside the counting binary search's result for the last item. Predict each printed line, run it, and fill in the third table. Tool: A free browser-based Python runner (an online editor that runs Python 3 with no account and nothing to install), Python Tutor at pythontutor.com for step-by-step visualization, the official Python documentation at docs.python.org, and one approved chatbot used as a pair-programmer whose code the student runs before trusting. Check: Three printed lines, one per list size, with your predicted and actual comparison counts side by side.
7. Open your approved chatbot, paste the critique prompt from Part 6 as one message, then check each of its claims by running the code it talks about. If you are using the equivalent route, mark up the printed flawed analysis in the same way. Tool: A free browser-based Python runner (an online editor that runs Python 3 with no account and nothing to install), Python Tutor at pythontutor.com for step-by-step visualization, the official Python documentation at docs.python.org, and one approved chatbot used as a pair-programmer whose code the student runs before trusting. Check: The fourth table lists each chatbot claim, what your run showed, and a correction wherever the two disagree.

Fallback route

When to use it: Use this route if your browser Python runner will not open or will not run code.

Run every program in Python Tutor instead, which also runs Python 3 in the browser: paste each program with the functions it needs, click the button to visualize it, and step to the end to read its output or its error. Complete every table, analysis question, and the critique step, and submit the same items for equal credit.

This route earns the same credit as the primary route.

Part 4 — The Scaffold

Predict first and run second, so the gap between the two columns is your own evidence of how each search and sort behaves.

Student scaffold table 1

Program	Your prediction	Actual output from the run	Same or different?
tags = [11, 19, 23, 30, 36, 42, 47, 55, 61, 68], then print(linear_search(tags, 42))
The same tags, then print(binary_search(tags, 42))
The same tags, then print(linear_search(tags, 50))
The same tags, then print(binary_search(tags, 11))
mixed = [42, 11, 61, 23, 55, 30], then print(binary_search(mixed, 23))
The same mixed, then print(selection_sort(mixed)); predict the line for pass 2 and the last line

Read each broken program from its run before you change a single character.

Student scaffold table 2

Broken program and what it should do	What printed, or the error type on the last line	Your one-change fix	Output after the fix
Bug 1, should print 5 for 42 and -1 for the missing tag 70: the counting-free binary search that starts with hi = len(items) and loops while lo <= hi:, then print(binary_search(tags, 42)) and print(binary_search(tags, 70))
Bug 2, should find every tag in tags: the counting-free binary search that starts with hi = len(items) - 1 but loops while lo < hi:, run on each of the ten tags with a for loop
Bug 3, should print 5 for 42: a linear search whose loop body is if items[i] == target: with return i, then else: with return -1, then print(linear_search(tags, 42))

Write your own growth program, then let the run confirm or correct the counts you expected.

Student scaffold table 3

List size	Comparisons you expected for the last item	Line the run printed
25
50
100

Check every chatbot claim against a run so the run, not the chatbot, has the last word.

Student scaffold table 4

Chatbot claim, quoted	What your run showed	Correct as stated, or your correction

Part 5 — Analysis Questions

1. Which of your six predictions in the first table differed from the run? For each one, write the step-by-step trace that reaches the actual output and name the rule that explains the gap, such as a missing tag costing linear search every comparison, binary search starting in the middle, or the sorted-list precondition.
2. For row 2 of the first table, what were lo, hi, and mid on each pass of the while loop in Python Tutor in step 5? Explain why the loop stopped when it did.
3. Bug 1 stops with an error, while Bugs 2 and 3 run and print the wrong thing. Name the error type Bug 1 raised and why, explain why Bugs 2 and 3 are logic errors, and say which tags Bug 2 failed to find and why its loop stopped one pass early.
4. Choose one: (a) use your growth program's three lines to name binary search's growth class, and say what you expect the count to be if the list doubled again; or (b) explain how a chatbot's claim about a search could be checked by testing the first tag, the last tag, and missing tags on each side, using one claim from your critique as the example.
5. Every list in this lab was short and held whole numbers with no repeats. Name one thing these runs could not tell you about searching, such as which index a search returns when a tag appears twice or how the counts behave on a much longer list, and say how you would check it by running more cases.

Part 6 — AI-Critique Moment

Choose one equal-credit critique route. Route A: ask an approved AI tool to critique your completed work, then check its response against your own evidence. Route B is the no-AI equivalent printed below.

Approved tools: Claude, Gemini, ChatGPT, Grok, Microsoft Copilot.

Prompt to paste:

I'm doing a beginner Python lab about the tag numbers in a campus lost-and-found, written for a class activity. Please do seven things, and keep each answer short. First, predict exactly how many comparisons a selection sort that counts every comparison makes on the six tags mixed = [42, 11, 61, 23, 55, 30]. Second, a binary search that returns (index, comparisons) is run as binary_search(mixed, 23) on that same unsorted list; predict what it prints and explain in one sentence why. Third, write a Python binary search that returns the index of a target in a sorted list, or -1 if it is missing, and say what it returns for 70 in tags = [11, 19, 23, 30, 36, 42, 47, 55, 61, 68]. Fourth, write a linear search that returns the index of a target or -1 when the target is missing, and tell me whether it works. Fifth, if I write sorted(mixed) on a line by itself and then run the binary search on mixed, will it find 23 now? Sixth, what does the counting binary search print when the list is empty, as in binary_search([], 5)? Seventh, this binary search stops with an IndexError for 70 because it starts with hi = len(items); fix it with the smallest change you can.

Test the response for these likely failures:

• Chatbots often answer 36, six times six, treating selection sort as if every tag were compared with every tag including itself.
• A chatbot may give the right output, (-1, 2), but explain that 23 is not in the list, although 23 sits at index 3.
• A chatbot may start its search with hi = len(items) and keep while lo <= hi:, one past the last index.
• A chatbot may put return -1 in an else inside the loop and call the linear search working without running it.
• A chatbot may claim that sorted(mixed) on its own line sorts mixed in place.
• A chatbot may say the search raises an error on an empty list, or never consider the empty list at all.
• A chatbot may keep hi = len(items) and change the loop test to while lo < hi:, which removes the IndexError.

Write 2-3 sentences that name one thing the chatbot got right and at least one claim you corrected, and for each correction give the output or error type your own run showed.

Equivalent route (no AI required)

No AI account is required for this lab. Instead of the chatbot, critique this flawed analysis, printed here in full: “Selection sort compares every tag with every tag, so on the six mixed tags it makes 36 comparisons. binary_search(mixed, 23) prints (-1, 2) because 23 is not one of the tags. Here is a binary search that works: it starts with hi = len(items) and loops while lo <= hi:, and it returns -1 for 70. Here is a working linear search: inside the loop, if items[i] == target: returns i, and an else: returns -1. Writing sorted(mixed) on its own line sorts mixed, so the search finds 23 afterward. On an empty list the search crashes with an IndexError. To fix the search that crashes on 70, change the loop test to while lo < hi: and keep everything else; now it never crashes.” Mark it up: quote each flawed sentence, run the code it describes in your browser Python runner, and write the corrected claim beside it with the run's output or error type as evidence. This route assesses the same objectives as the chatbot critique, namely tracing linear search, binary search, and selection sort with a comparison counter, keeping binary search's sorted-list precondition, finding an off-by-one in a loop's bounds, and checking every claim about code by running it (Objective 8 and Objective 4), and it takes comparable effort, about 20 minutes of the lab. It is scored by the same rubric for the same credit, and its marked-up analysis replaces the chatbot report and share link in your submission. You do not need to say which route you chose.

Part 7 — What to Submit

• All four completed scaffold tables
• Written answers to all five analysis questions
• Your growth program with its run output
• The chatbot critique report with its share link, or the equivalent route's marked-up flawed analysis

Deliverable:

A short Coding Lab report on an illustrative campus lost-and-found: four completed tables (six predictions beside their runs, three broken searches read and fixed, your own growth program, and the checked chatbot claims), written answers to five analysis questions, and a critique of a chatbot's answers to the same questions, or, on the equivalent route, a marked-up correction of the printed flawed analysis. Submit in any accessible file type or as a link; a recorded response may be submitted as audio or video with a transcript, or as text. Choose a written, recorded, or visual form for your answers, such as screen captures of your runs with a short note for each; every form is graded by the same rubric.

Rubric

The rubric below shows how each submitted part is evaluated; bands are full, partial, or none.

Workshop evaluation criteria

Criterion	Full	Partial	None
Predicting and running the six programs	All six predictions are recorded before the runs, and all six actual outputs match what the programs print, copied character for character, including both numbers of every tuple such as an index and its comparison count.	The table is mostly complete, but an actual output is missing or miscopied, or predictions appear to have been filled in after running.	No predictions or runs are recorded, or the outputs are invented rather than run.
Explaining the gaps between prediction and run	Every prediction that differed from its run is traced step by step to the actual output, with the governing rule named, such as a missing tag costing every comparison, the middle-first order of binary search, or the sorted-list precondition.	The gaps are listed, but a trace is missing or the rule behind a gap is not named.	No gap is explained, or the response blames the runner instead of the rule.
Finding and fixing the three bugs	Each bug is read correctly from its run: what printed or the error type, a one-change fix, and the fixed program's output on every tag and a missing tag, with Bug 1 fixed by starting hi one lower, Bug 2 by restoring the less-than-or-equal loop test, and Bug 3 by moving the not-found return after the loop.	Two of the three bugs are read and fixed correctly, or all three are fixed but an error type or the run evidence on every tag is missing.	The bugs are not attempted, or errors are named without running the programs.
Writing, running, and verifying a growth program	The growth program runs without an error, prints one line for each of the three list sizes, records the expected and actual comparison counts side by side, and names the growth class the counts show.	The program runs but misses one requirement, such as a list size or the growth class, or the expected or actual counts are not recorded.	No program is submitted, or it was not run.
Critiquing the AI analysis or the printed flawed analysis	The chatbot's answers, or on the equivalent route the printed flawed analysis, are quoted and at least two claims are corrected with evidence from the student's own runs.	The critique names errors but corrects only one, or corrects without run evidence, on either route.	No critique is submitted on either route, or chatbot or flawed text is pasted without any checking.
Reflection and limitation	The chosen reflection option is answered with a specific example from this lab, and the limitation answer names something these runs cannot show and a sensible way to check it.	The reflection or the limitation is general, without an example from this lab or a way to check it.	The reflection and limitation questions are not answered.

Quality Gate

• Every prediction in the first table was written before its program was run.
• Every actual output, comparison count, and error type is copied from your own run, never from memory or a chatbot.
• Each error is named by its type from the last line of the error message, not by the wording after the colon.
• Each fix changes as little as possible, and its fixed program was run on every tag and on one missing tag.
• No output, count, timing, or claim is invented anywhere in the submission.
• The critique quotes the chatbot or the flawed analysis and corrects at least two claims with evidence from your runs.