Week 13 — The Search That Missed a Part — Traditional alternative (no AI)

Instructors: publish this instead of the adaptive version if you prefer, and unpublish or delete the adaptive one.

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 week you learned that linear search checks items from the front and works on any list, that binary search halves a sorted list and can miss an item when the list is not sorted, that a comparison counter measures work the same way on every machine, and that selection sort's comparisons roughly quadruple when its list doubles. In this assignment you trace four short problems, run each one to check your prediction, run one more program that shows what the fast search does on an unsorted list, and explain a real mix-up to someone who has never programmed. This builds on Week 9's lists and Week 6's nested loops. This week's lecture tutorial, quiz, discussion, and Coding Lab practise the same ideas from other angles.

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.

Show your traces. A reader should be able to follow every prediction step by step and see the actual output of your run beside it, without guessing which index the search checked or which item each pass moved.

Deliverables

Submit a single report containing:

• the four answers, each with your prediction, the step-by-step trace, the actual output of your run, and the brief interpretation the task names for that problem;
• the run of your friend's binary search on the unsorted parts list for part 9, with what printed; and
• your message to your friend, explaining why the fast search said part 9 was missing, what to do about it, and one limit.

Keep it to roughly one page. Clear and correct beats long.

Choose how you show it. Present your report as written text, or as a recorded audio or video explanation of about three minutes with a transcript, or as labelled screen captures of your runs with a short note for each. Every form is graded by the same scoring criteria. 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.

How you'll be graded

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

Academic integrity and AI use

This version is designed to be completed without AI: make the predictions, run the code, and write the interpretations and the message yourself, without any AI tool. You may use a free browser Python runner, Python Tutor, and the official Python documentation. Submitting AI-generated work as your own, or copying another student's work, is an integrity violation under the course policy.

Built with The Course Maker · samples.thecoursemaker.com