Unit 4 · Algorithms & Simulation · Lesson 4.14 · Test

Test Day

You take the Unit 4 test in class today. This page is everything you can do before it — what’s on it, the traps, and practice that isn’t on the real test. There are no test questions here.

Big Idea 3 — Algorithms & ProgrammingAssessment — review only

Before this lesson

No new reading. Everything on the test comes from 4.1–4.13. The fastest revision is the 4.13 three-way sort, not re-reading.

Where We Are

People→ Bits→ Programs→ Internet→ Security→ Big Data→ Impact

A checkpoint on the Algorithms region of Programs. Nothing here is new. After the test: the flex day, then the semester final.

What’s on the Test

70 points. Eighteen multiple-choice questions (2 points each), six short responses (3 each), and one written response (16) that explains an algorithm’s efficiency in plain language. Several questions are in AP Pseudocode only. No computer; count on paper, and show your counting on the short and written responses — that’s where partial credit lives.

Where the points are — study to this map:

What it tests	From	Roughly
Binary search: the sorted precondition and step counts	4.4–4.5	4–5 Q
Linear search: how many elements are checked	4.3	1–2 Q
Counting steps, nested loops, “same result?”, which is more efficient	4.2, 4.6	4–5 Q
Reasonable vs unreasonable time	4.7	2 Q
Heuristics: what’s traded for what	4.8	3 Q
Undecidable vs unreasonable — the three-way sort	4.9, 4.13	3 Q
Simulations: why, randomness, what’s left out, trial count	4.10–4.12	5 Q

How to Review — the Last 20 Minutes

The 20-minute plan

1. Say the unit in a breath (2 min). Count steps to compare; efficient / unreasonable / undecidable; simulations simplify.

2. Run the six traps (5 min). Below.

3. Redo the three-way sort (5 min). 4.13 — until you file every card right.

4. Take the practice set (8 min). Section 4 — fresh questions, none on the real test.

The six traps

Don’t confuse	The one-line difference
binary vs linear requirements	Binary search needs sorted data. Linear search works on anything.
halvings vs checks	A list of 2^k items halves k times — binary search makes k + 1 checks. Count the last one.
nested vs sequential loops	A loop inside a loop multiplies (n × n). One loop after another adds (n + n).
unreasonable vs undecidable	Unreasonable: an algorithm exists but can’t finish. Undecidable: no algorithm can exist.
heuristic vs guaranteed	A heuristic is fast and good-enough; it may miss the best answer.
one trial vs many	One simulation run isn’t evidence. And every simulation leaves details out.

Practice Set

Six mixed questions in AP format. None is on the real test — they’re for calibration.

0 of 6 answered

Written-Response Practice

Explain an algorithm’s efficiency, the way it’s scored

Prompt. This procedure checks a list for duplicates. (a) If the list has 100 items and no duplicates, how many times does the IF run? Show how you got it. (b) What happens to that number if the list grows to 200 items? (c) Does this algorithm run in reasonable time? Explain.

PROCEDURE hasDuplicate(list)
{
    i ← 1
    REPEAT LENGTH(list) TIMES
    {
        j ← 1
        REPEAT LENGTH(list) TIMES
        {
            IF (i ≠ j AND list[i] = list[j]) { RETURN (true) }
            j ← j + 1
        }
        i ← i + 1
    }
    RETURN (false)
}

Write your answer before opening the checklist.

Connections

Came from all of Unit 4 — a shaky row in the section 2 table is the lesson to reopen now.

Next in 4.15 — debrief, then “how long would this actually take?”

Then the semester final — Units 0–4.

Returns on the AP exam — efficiency, undecidability, and simulation questions are short and very learnable. These are points you should never give away.