Week 13 — The Search That Missed a Part

Assignment 12 of the term — search a list two ways, count the work, sort it pass by pass, see how the work grows, and explain it all to someone who has never programmed.

This adaptive assignment uses a coaching dialogue to help you turn a first attempt into a clear, evidence-based report. You remain the author. The coach asks questions, checks the reasoning you show, and waits for you to revise before it produces the required report. This builds on Week 9's lists and Week 6's nested loops: every search here walks a list by its index, and selection sort is a loop inside a loop. This week's lecture tutorial, quiz, discussion, and Coding Lab practise the same ideas from other angles; this assignment is where you put them together.

The task

A friend who keeps the parts bin for a campus robotics club wrote a "fast search" to find part numbers in the club's list. The list is kept in the order the parts arrived:

parts = [52, 17, 88, 34, 61, 9, 45, 70]

Your friend's fast search is this week's binary search. They ran it to look for part 9, and it said the part was not there, even though part 9 was sitting in the bin. Your friend asks: "Why did the fast search say part 9 was missing, and should I sort the list every time I search?" Your job is to check what Python really did, the way a programmer would: predict each output before you run it, run it in a free browser Python runner, and explain what happened. All four problems are illustrative. Use the counting versions of linear search, binary search, and selection sort from Chapter 13.

Work these four problems. For each one, write your prediction first, then run the code and write the actual output beside your prediction:

1. The club's parts list holds 52, 17, 88, 34, 61, 9, 45, 70 in the order the parts arrived; a linear search that counts comparisons looks for part 9. How many comparisons does it make?
2. The same parts list is sorted first, giving 9, 17, 34, 45, 52, 61, 70, 88; a binary search that counts comparisons looks for part 70. How many comparisons does it make?
3. Selection sort with a comparison counter sorts the club's 8 parts. How many comparisons does it make?
4. The club's list doubles to 16 parts, and selection sort with a comparison counter sorts them. How many comparisons does it make?

Beside each answer, add one brief interpretation:

• Problem 1: run your friend's binary search on the unsorted parts list for part 9, report what it prints, and explain why linear search found the part while the binary search did not.
• Problem 2: name the middle values the binary search checked, in order, and explain why sorting the list first made the search trustworthy.
• Problem 3: compare the sort's comparisons with the comparisons linear search made in Problem 1, and explain when sorting first pays off for the club.
• Problem 4: say about how many times as much work the doubled list cost, and name selection sort's growth class.

Explain it to a non-programmer

Write a message of three to five sentences to your friend that explains, in everyday words, why the fast search said part 9 was missing and what to do about it. Use the idea that halving only works when the list is in order, and name one limit or caveat, such as what sorting costs or when the plain search is the better choice. Explain any technical term in everyday words. More than one good message is possible.

For a different, ungraded example, imagine a cousin who keeps recipe cards in a box, filed in the order the recipes were collected, and who tried to find a card by opening the box in the middle. Model message: "Opening in the middle works only when the cards are filed in order, like a phone book. Your cards are in the order you collected them, so the card you want could be on either side of the middle, and the halving trick can skip right past it. If you file the cards alphabetically, the middle trick works every time. The catch is that filing them takes a while, so it is worth it only if you look things up often."

Use that pattern for your friend's question, with your own wording and evidence.

Part 1 — Student instructions

1. Draft all four predictions, the four actual outputs, the four brief interpretations, and your message to your friend before opening a chatbot. Run every program yourself in a browser Python runner.
2. Open any course-approved chatbot. Copy the entire Coach Prompt box, including its first and last marker lines, and paste it as one message. The coach will ask for your draft and then work one question at a time.
3. Answer in your own words. Show your traces when asked. Use the coach's feedback to revise at least one trace or explanation, even if your first attempt was correct.
4. Continue until the prompt's exit condition is met.
5. Save the chat's share link and copy the final report exactly as the coach gives it.

The chatbot is a coach, not a ghostwriter. It must draw out your reasoning rather than write the work for you, and it does not run your code; your own runs settle every output.

Coach Prompt

COPY EVERYTHING BELOW THIS LINE
ROLE: You are a careful learning coach for an introductory computer science course taught in Python 3. Draw out and challenge MY thinking about linear search, binary search and its sorted-list precondition, counting comparisons, selection sort, and how a step count grows. Do not write my assignment for me, do not invent work I did not show, never invent a statistic, a study, or a quotation, never give a timing in seconds, and never tell me what a line of code prints or how many comparisons it makes: ask me to run it in my own browser Python runner and tell you what appeared.

ASSIGNMENT: Work through these four problems in order, one at a time. Do not invent, replace, or reorder a problem. All four are illustrative. For each one I write a prediction first, then run the code and report the actual output beside it.
PROBLEM P1: The club's parts list holds 52, 17, 88, 34, 61, 9, 45, 70 in the order the parts arrived; a linear search that counts comparisons looks for part 9. How many comparisons does it make?
PROBLEM P2: The same parts list is sorted first, giving 9, 17, 34, 45, 52, 61, 70, 88; a binary search that counts comparisons looks for part 70. How many comparisons does it make?
PROBLEM P3: Selection sort with a comparison counter sorts the club's 8 parts. How many comparisons does it make?
PROBLEM P4: The club's list doubles to 16 parts, and selection sort with a comparison counter sorts them. How many comparisons does it make?
After the four answers, I must briefly interpret each one: for P1, run the friend's binary search on the unsorted parts list for part 9, say what it prints, and say why linear search found the part while the binary search did not; for P2, name the middle values the search checked, in order, and say why sorting first made the search trustworthy; for P3, compare the sort's comparisons with linear search's comparisons in P1 and say when sorting first pays off; for P4, say about how many times as much work the doubled list cost and name selection sort's growth class. I must then write a message of three to five sentences to a friend whose fast search missed a part, explaining in everyday words why it happened and what to do, and naming one limit or caveat. I must explain technical terms in everyday words.

SCORING CRITERIA: Score only evidence I supply: correct traces (40 points), reasoning about searching, sorting, and growth (32 points), clarity for a non-programmer (16 points), and showing the trace and the run (12 points). For each of P1-P4, give 2, 1, or 0 evidence units per criterion; one unit is worth 5 trace points, 4 reasoning points, 2 clarity points, or 1.5 showing points. Sum all four problems within each criterion. Count my final message only with P4, not again with P1-P3.
TRACE UNITS: A reported value that matches the run, including equivalent notation = 2; the right values and steps with only an arithmetic slip = 1; a missing value or the wrong values or steps = 0. Do not penalize an alternative valid way of showing the trace.
REASONING UNITS: For P1-P3 separately, an interpretation that meets both parts named for that problem = 2; exactly one part = 1; neither = 0. For P4, how many times as much work the doubled list cost AND the growth class AND a friend message with the cause, the fix, and a named limit = 2. If full P4 evidence is absent but at least one accurate substantive part appears, give 1. No accurate reasoning = 0; naming a term alone does not earn a unit. An arithmetic slip alone is not a reasoning error.
CLARITY UNITS: For each problem, labeled evidence understandable to someone who has never programmed, with technical terms explained = 2; intelligible evidence that needs rereading because of ambiguity or jargon = 1; absent or unintelligible evidence = 0. Include the final message with P4 if submitted. Missing reasoning alone does not lower clarity for otherwise clear submitted work.
SHOWING UNITS: For each problem, a step-by-step trace plus the reported output of an actual run = 2; a relevant but incomplete step or run output = 1; a final value alone or no trace = 0. A visible trace stays checkable despite an arithmetic slip.

Do NOT invent grading rules.

DIALOGUE RULES: Ask exactly one question per message and wait for my answer. Start by asking for my complete first attempt. Build each next question from my exact words. Probe an unsupported claim and ask me to examine its evidence, usually by running the program again or by writing out each pass. Keep the conversation focused on questions rather than completed work.

ENGAGEMENT GUARDS: A greeting, copied prompt, yes/no reply, or one-word answer is not a substantive exchange. Do not flatter or accept agreement as evidence. Praise only a concrete move I made. If evidence is missing, say what is missing and ask for it. Require a real revision plus a short reflection on why the revision is better. Do not issue the report early.

EXIT CONDITION: Continue until at least five substantive exchanges have occurred AND I have supplied all four answers with their runs and brief interpretations AND written my message to the friend AND revised at least one trace or explanation AND reflected on the revision. Stop only after whichever requirement happens last.

REPORT: After the exit condition is satisfied, output exactly these labelled lines in this order. Replace X with the exact earned score; it may end in .5 and must not be rounded to a whole number. Base every line only on evidence in this chat; write "Not supplied" for missing evidence and never raise the score for polished chatbot prose.
STUDENT'S SCORE: X/100
EVIDENCE FOR THE SCORE: [specific evidence from my traces, runs, and reasoning]
REVISION MADE: [what I changed and why]
STRENGTH: [one earned strength]
NEXT STEP: [one concrete improvement]
Then tell me to submit this report, my revised work, and the share link.
COPY EVERYTHING ABOVE THIS LINE

Deliverables

Submit these three items in the assignment entry:

• your revised work with all four predictions and actual outputs, their brief interpretations, the run of your friend's binary search on the unsorted list, and your message to your friend — written, or recorded as audio or video with a transcript, or as a labelled screen capture of your runs with a short note for each; every form is graded by the same scoring criteria;
• the coach's five-line report; and
• the conversation share link.

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.

Equivalent route (no AI required)

This route assesses the same Week 13 skills — tracing linear search and binary search with a comparison counter, keeping binary search's sorted-list precondition, counting selection sort's comparisons, and naming how a step count grows when the list doubles — for comparable time and effort, about 60 to 90 minutes, the same as the coached route. Complete the same four problems with your predictions and runs, the four brief interpretations, the run of your friend's binary search on the unsorted list, and the message to your friend. Then audit your own first draft against the attached scoring criteria, criterion by criterion, and write a second draft. Add a revision memo of about 150 to 200 words that names one trace or explanation you changed, the evidence that prompted the change (for example, a run that disagreed with your prediction), and one question you still have. Submit the revised work, your completed criteria checklist, and the revision memo in the assignment entry; together they replace the share link and the coach's report. This route uses the same scoring criteria and the same points, with no penalty for choosing it.

How you'll be graded

The full analytic rubric is attached to this assignment in Canvas.

Academic integrity and AI use

The predictions, runs, reasoning, revision, and final report must be your own. Do not ask the chatbot to create the assignment, to tell you what a program prints, or to add evidence you did not produce. Submit an honest share link from your own dialogue. The equivalent route keeps the same workload and evidence and requires no AI account.

Built with The Course Maker · samples.thecoursemaker.com