Week 13 — Coding Lab / Programming Studio · "Count the Steps"

Course: Introduction to Computer Science — CS1 / Programming Fundamentals in Python (CSCI 1101) · Silver Oak University (fictional sample) · Prof. Okafor
Objective: Objective 8 — implement & count steps in search and sort · SLO A (write & run) + SLO B (trace & debug)
Worth 50 points · Coding Labs group = 15% of the grade · Coding Lab 13
Format: a hands-on programming studio in a free online Python environment — you'll (a) write, (b) trace code and predict its output, and (c) find and fix a bug — then catch the AI's mistake.

Everything runs in your browser — nothing to install. The habit: run it and read what Python actually prints.

Part 1 — The Big Picture

This week you learned that two programs can get the same answer at very different speeds. This lab makes that concrete: you'll implement linear and binary search, count the comparisons each makes, watch one win 13-to-4, sort a list, and fix the classic binary-search-on-unsorted bug.

Your tools: 🔗 https://www.online-python.com/ (write & run) and 🔗 https://pythontutor.com/ (visualize).

Part 2 — (a) Write

Write each program, run it, and paste your code + output.
1. Linear search with a counter. Write linear_search(lst, target) that returns (index, comparisons). Run it on [4, 8, 15, 16, 23, 42] for targets 16, 42, and 7. Report the comparisons for each.
2. Binary search with a counter. Write binary_search(lst, target) (sorted list) that returns (index, comparisons). Run it on the same list for 16 and 4.
3. Head-to-head. Build the sorted list list(range(1, 17)) (that's 1..16). Find 13 with BOTH searches and print the comparison counts side by side.

Part 3 — (b) Trace: Predict, Then Run

Predict each output first (don't run yet!), then run each and fill in "Actual."

Hint for #3 vs #4: the answer (index 12) is the same — but watch the comparison counts. That gap is the whole point of binary search.

Part 4 — (c) Find & Fix the Bug

A student runs binary search on an unsorted list and it lies. Run this, then write (i) what it prints, (ii) why it's wrong, and (iii) a one-line fix.

data = [8, 4, 23, 16, 42, 15]   # NOT sorted
print(binary_search(data, 4))   # 4 is in the list, at index 1...

Part 5 — Analysis Questions

1. In #3 vs #4, both searches found 13 — but how many comparisons did each take? What does that say about how they'll behave on a list of 1,000,000 items?
2. Why does binary search take so many fewer steps than linear search?
3. Why does binary search require a sorted list? (Use your Part 4 result.)
4. Selection sort has a loop inside a loop. In Big-O terms, is it O(n), O(log n), or O(n²) — and why?
5. Connect it: you measured speed by counting comparisons, with no stopwatch. Why is counting operations a more reliable way to compare algorithms than timing them?

Part 6 — AI-Critique Moment (required — this is the BYOAI step)

Bring in your approved chatbot and check its work.
1. Ask it: "How many comparisons does binary search take to find 13 in the sorted list 1 to 16? And does binary search work on an unsorted list?"
2. Run an instrumented version and check: did it say the run-verified 4 comparisons (chatbots often say 3 or 5)? Did it correctly say binary search does not work on unsorted data?
3. Write 2–3 sentences on what it got right and one thing you had to correct or verify by running it.

The habit: the tool drafts, you run it and judge. Catching the AI's slip — by running the code — is the point.

Part 7 — What to Submit

Your Part 2 programs + outputs; your completed Part 3 trace table; your Part 4 bug answers; your Part 5 answers; and your Part 6 AI-critique paragraph. Due Sunday, Nov 29, 11:59 p.m. (50 points).

Instructor answer key & model outputs — REMOVE BEFORE PUBLISHING TO STUDENTS

Execution gate: PASS — every output below was produced by running the code.

Part 2 (model, run-verified): (1) linear_search on [4,8,15,16,23,42]: 16→(3, 4); 42→(5, 6); 7→(-1, 6). (2) binary_search on the same: 16→(3, 3); 4→(0, 2). (3) on 1..16, finding 13: linear = 13 comparisons, binary = 4 comparisons (same index 12).

Part 3 trace table (run-verified):

Part 4 bug (run-verified): (i) prints -1 (not found) — (ii) wrong because the list isn't sorted, so binary search discarded the half that actually contained 4 (it's at index 1); (iii) fix: print(binary_search(sorted(data), 4)) → finds 4 at index 0 (or use linear search).

Part 5 (expected): (1) on a million items, linear ~ up to 1,000,000 comparisons while binary ~ 20 — the gap explodes with size. (2) binary halves the search range each step (O(log n)) instead of checking one at a time (O(n)). (3) it uses order to decide which half to keep; without sorting it discards the wrong half. (4) O(n²) — for each of n positions it scans the rest. (5) counting comparisons is deterministic and machine-independent, while timing varies with hardware, load, and language.

Grading rubric — 50 points

Quality gate (self-checked): every model output above was produced by running the code — execution gate: PASS.