Week 13 — Quiz (auto-graded) · Algorithms: Searching & Sorting + Intro to Complexity

Course: Introduction to Computer Science — CS1 / Programming Fundamentals in Python (CSCI 1101) · Silver Oak University (fictional sample) · Prof. Okafor
Objective tested: Objective 8 — search, sort, comparison counts, and Big-O (intuitive).
Points: 10 (1 each) · Assignment group: Quizzes (10% of grade) · Due: end of Module 13.

Human-readable quiz with its vetted answer key. Import-ready Classic QTI in F-quiz-week-13-qti.xml (parses with 10 items, one correct per single-answer item). Execution gate: PASS — every keyed output/result was produced by running the code.

Questions, key, and feedback

Q1 (MC). Linear search checks one item at a time. To find a value at the END of a list of 6 items, about how many comparisons does it make?
- A. 1
- B. 3
- C. 6 ✅
- D. 0
Feedback: Linear search checks each item up to the target, so the last item of a 6-item list costs 6 comparisons. (Run-verified: finding the last item of a 6-element list = 6.)

Q2 (MC). Binary search can be used on which kind of list?
- A. any list
- B. only a SORTED list ✅
- C. only a list of strings
- D. only a short list
Feedback: Binary search decides which half to discard based on order, so it requires a sorted list (Programiz states this outright).

Q3 (MC). On the sorted list 1..16, binary search finds 13 in how many comparisons?
- A. 1
- B. 4 ✅
- C. 13
- D. 16
Feedback: Halving 16 → 8 → 4 → 2 → 1 is about log₂(16) = 4 steps. (Run-verified: 4.)

Q4 (MC). On that same sorted list 1..16, LINEAR search finds 13 in how many comparisons?
- A. 4
- B. 8
- C. 13 ✅
- D. 1
Feedback: Linear search checks 1, 2, 3, ..., 13 in order — 13 comparisons. (Run-verified.) The same answer that binary got in 4 steps shows why binary wins as lists grow.

Q5 (MC). What does this print?

def linear_search(lst, target):
    for i in range(len(lst)):
        if lst[i] == target:
            return i
    return -1
print(linear_search([4, 8, 15, 16, 23, 42], 16))

• A. 16
• B. 3 ✅
• C. 4
• D. -1
  Feedback: It returns the index where 16 is found — index 3 (not the value 16, and not the comparison count 4). (Run-verified.)

Q6 (Multiple answer — select all that apply). Which statements are true?
- A. Binary search requires a sorted list ✅
- B. Binary search is always faster than linear search on every list
- C. Linear search works on an unsorted list ✅
- D. Selection sort uses a loop inside a loop ✅
- E. Big-O gives the exact number of steps a program takes
Feedback: Binary needs sorted input (A); linear works on any list (C); selection sort is a loop-in-a-loop (D). B is false — on a tiny or unsorted list linear can win. E is false — Big-O describes how work grows, not an exact count.

Q7 (Matching). Match each operation to its Big-O time complexity.
| Operation | Big-O |
|---|---|
| Linear search | O(n) |
| Binary search | O(log n) |
| Selection sort | O(n squared) |
| Direct index lst[5] | O(1) |
Feedback: Linear grows with the list (O(n)); binary halves (O(log n)); selection sort is a loop-in-a-loop (O(n²)); a direct index is O(1) — constant.

Q8 (True / False). "Binary search always gives the correct answer even on an unsorted list."
- True
- False ✅
Feedback: False. On an unsorted list binary search can discard the half that holds the value and report "not found." (Run-verified: searching the unsorted [8,4,23,16,42,15] for 4 returns −1, though 4 is at index 1.)

Q9 (MC). A selection sort sorts ascending. What does this print?

# selection_sort returns a new sorted list
print(selection_sort([5, 2, 9, 1, 7]))

• A. [5, 2, 9, 1, 7]
• B. [1, 2, 5, 7, 9] ✅
• C. [9, 7, 5, 2, 1]
• D. [1, 2, 7, 5, 9]
  Feedback: Selection sort returns the list in ascending order: [1, 2, 5, 7, 9]. (Run-verified.)

Q10 (MC). A student runs binary search on the UNSORTED list [8, 4, 23, 16, 42, 15] to find 4, and it reports "not found" even though 4 is in the list. What is the fix?
- A. Add a semicolon to the loop
- B. Sort the list first (or use linear search) — binary search requires sorted input ✅
- C. Change the target from 4 to 8
- D. Nothing — 4 is not really in the list
Feedback: The precondition was violated. Sort the list first (sorted(...)) or use linear search. (Run-verified: after sorting, binary search finds 4 at index 0.)

Answer key (quick reference)

Quality gate (self-checked): each single-answer item has exactly one correct option; the multiple-answer item keys are exact; the matching item pairs one-to-one. Execution gate: PASS — the comparison counts (Q1 6; Q3 4; Q4 13), the search index (Q5 3), the sort output (Q9), and the unsorted-bug behavior (Q8, Q10) were each produced by running instrumented code in Python.

Canvas placement block

canvas_object   = Quizzes::Quiz
title           = "Week 13 Quiz — Algorithms: Searching & Sorting + Intro to Complexity"
assignment_group = "Quizzes"
points_possible = 10
grading_type    = points
due_offset_days = 6
published       = true
shuffle_answers = true
ai_permitted    = false
provenance      = "~ Prof. Okafor's edition · Fall 2026 · built with thecoursemaker.com"