Compare search strategies, scaling, heuristics, simulation, and the limits of computation.
5 lessons10 estimated blocksAP topics 3.11, 3.15–3.1815 original exam questions
Unit overview
Use these lessons like the Algebra II and Physics pages: read the notes, learn the vocabulary, follow a worked example, attempt the quick checks before revealing solutions, and make a prediction before running the investigation.
10 blocks85-minute blocks, approximately 10–11 in the 16-week map
5 lessonsNotes, examples, vocabulary and quick checks
15 questionsFilterable exam-style bank
Success criteria
Trace linear and binary search.
Compare linear, quadratic, exponential growth.
Compare exact and heuristic solutions.
Create a model with input assumptions.
Contrast unreasonable runtime with undecidability.
Course model: CodeHS for targeted coding, this page for conceptual understanding, and AP Classroom for official aligned assessment. This is an original supplementary resource, not an official College Board publication.
Lesson map
Lesson numbering on this page is site-specific. CodeHS uses a different lesson numbering system.
Linear search checks candidates one by one. Binary search repeatedly halves an ordered search interval, but only if the data is sorted appropriately. Be precise about whether a count measures comparisons, loop iterations, or elapsed time.
Vocabulary
linear search inspect items sequentially
binary search discard half an ordered interval
sorted ordered according to a rule
Worked example
Looking for 12 in [2,5,8,12,20,25,30] can use binary search: check 12 at the middle and finish with one comparison.
Try it · Check your understanding
1. Can binary search reliably work on an unsorted list?Show solution
No; discarding half the data would not be justified.
2. Worst-case linear search in a list of n items?Show solution
CodeHS: CodeHS 17.1 Preparation; supplementary conceptual practice
Learning targets
Compare linear, quadratic, exponential growth.
Distinguish measured time from operation counts.
Core notes
Algorithmic efficiency describes resource use as input size grows. Count a representative operation for consistent comparison. Linear growth is proportional to n, quadratic to n², exponential to 2^n. AP CSP distinguishes polynomial reasonable-time from exponential/factorial unreasonable-time growth; formal Big-O proofs are enrichment.
Vocabulary
input size amount of data provided
operation count number of measured steps
polynomial growth bounded by a polynomial
exponential growth such as 2^n
Worked example
At n=10, n²=100 but 2^n=1024. At n=20, n²=400 and 2^n=1,048,576.
Try it · Check your understanding
1. When n doubles, what happens to n²?Show solution
It becomes four times larger.
2. Is every polynomial algorithm equally fast?Show solution
No. Both n and n³ are polynomial, but their scaling differs.
CodeHS: Supplement to CodeHS (no direct required lesson)
Learning targets
Compare exact and heuristic solutions.
Evaluate why speed may come at the expense of optimality.
Core notes
Optimization seeks the best solution according to an objective. Exhaustive methods can become impractical as combinations explode. A heuristic applies a useful rule of thumb to obtain a candidate solution efficiently but is not guaranteed optimal. Evaluate both solution quality and computation required.
Vocabulary
heuristic practical rule not guaranteed optimal
optimal best according to objective
exhaustive checks all candidates
objective quantity to minimize/maximize
Worked example
Nearest-neighbor routing chooses the nearest remaining stop. It is fast to explain and run, but a locally shortest move can produce a longer total trip.
Try it · Check your understanding
1. Can a heuristic ever find the optimal solution?Show solution
Yes, sometimes; it simply does not guarantee doing so.
2. Does a fast answer guarantee accuracy or optimality?Show solution
Simulation models a system through a computational process. Random values can model uncertainty; repeated trials estimate outcomes but do not guarantee future events. Compare the model’s assumptions with the real system and identify limitations. An outcome from a simulation is evidence about the model, not proof about reality.
Vocabulary
simulation computational model of process
randomness unpredictability in outcome
trial single run of experiment
assumption simplification built into model
Worked example
A fair coin simulation run 20 times might show 13 heads. This does not show the coin is biased; chance variation remains possible.
Try it · Check your understanding
1. Why increase the number of trials?Show solution
Aggregate proportions often stabilize and random variation becomes easier to study.
2. Can a simulation be flawed even if coded correctly?Show solution
Yes, if its assumptions do not reflect the real system.
Contrast unreasonable runtime with undecidability.
Recognize that no general algorithm solves every possible problem.
Core notes
Some tasks have algorithms that are too slow to be practical for large inputs. Other tasks are undecidable: no algorithm can guarantee a correct yes/no answer for every possible instance. The halting problem is the classic example. A heuristic may help with hard optimization but cannot make an undecidable general problem decidable.
Vocabulary
undecidable no always-correct algorithm for all inputs
halting problem deciding whether arbitrary programs halt
intractable impractically costly to compute
Worked example
Factoring a small number can be solved; checking every route through thousands of cities can be astronomically slow; deciding whether any arbitrary program halts is undecidable.
Try it · Check your understanding
1. Is “takes a billion years” the same as undecidable?Show solution
No. Extremely slow computations may still be algorithmically solvable.
2. Why cannot testing a few programs settle the halting problem?Show solution
It does not guarantee an answer for every arbitrary program and input.
Core video selection: The matching CodeHS lesson video and AP Daily topic video for each lesson. Direct AP Daily videos are accessed inside the school's AP Classroom enrollment and may not have public URLs.
Lesson 5.1: Searching, sortedness and correctness. Watch the matched CodeHS lesson video and the corresponding AP Daily topic video for 3.11; pause to answer the notes prompt before the interactive lab. AP Daily requires student login.
Lesson 5.2: Counting operations and growth. Watch the matched CodeHS lesson video and the corresponding AP Daily topic video for 3.17; pause to answer the notes prompt before the interactive lab. AP Daily requires student login.
Lesson 5.3: Heuristics and optimization. Watch the matched CodeHS lesson video and the corresponding AP Daily topic video for 3.17; pause to answer the notes prompt before the interactive lab. AP Daily requires student login.
Lesson 5.4: Simulation and randomness. Watch the matched CodeHS lesson video and the corresponding AP Daily topic video for 3.15–3.16; pause to answer the notes prompt before the interactive lab. AP Daily requires student login.
Lesson 5.5: Undecidable problems and limits. Watch the matched CodeHS lesson video and the corresponding AP Daily topic video for 3.18; pause to answer the notes prompt before the interactive lab. AP Daily requires student login.
Video selections are topic- and platform-matched. Teachers should check account availability and assign individual CodeHS/AP Daily clips from their course dashboards.
Make a prediction, manipulate the model, record observations, and explain whether your original thinking was correct.
Student lab record: Before you start, write your prediction and reasoning. Afterward, record at least two trials and an evidence-based conclusion. This model is illustrative and its limitations should be noted.
Investigation A · Algorithm growth and search
Predict how comparison counts change as the list size grows. Counts illustrate worst-case linear search and the approximate worst-case number of binary-search comparisons in a sorted list.
Linear worst case 64
Binary worst case 7
Quadratic n² 4096
List size is 2 raised to the slider value. Binary search assumes a sorted collection.
Investigation B · Coin-flip simulation
Predict the proportion of heads in 20 trials, then compare with 200 and 2,000 trials. Different outcomes are expected.
No simulation run yet.
Reflection prompt & explanation
The proportion should tend to be near 0.5 over many trials, but no finite run guarantees exactly 50%. A simulation models a fair coin; it does not prove a physical coin is fair.
Investigation record
Lab responses stay in this page; they are not uploaded or stored on a server.
AP-style practice & self-check
Original multiple-choice questions focus on reasoning, not just coding. Filter by lesson and difficulty. Show explanations in practice mode or hide them in exam mode.
Mastery target: 80% on mixed original questions, plus a clear written explanation on one unfamiliar scenario. Treat the bank as practice, not a secure test.
Teacher lesson specifications & implementation
Teacher-facing scope, exact learning goals, CodeHS alignments, and assessment requirements. This section can be hidden or separated before student publishing.
Pacing and lesson allocation
10 × 85-minute blocks. Shorten or extend CodeHS programming time based on prior experience and how many blocks actually meet; all lessons are supplemental to the main CodeHS course.
Default block: 10 min retrieval · 20 min notes/video · 20 min inquiry · 25 min selected CodeHS/independent practice · 10 min quick assessment.
40 points: 20 original AP-style multiple-choice questions (1 point each), four short-answer reasoning prompts (3 points each), and one 8-point novel investigation/analysis. Mix current-unit and prior-unit topics. Use AP Classroom separately for official question practice.
Assessment and feedback strategy
Independent predictions precede each simulation.
Students justify one wrong multiple-choice distractor in writing.
Teacher verifies model limitations, not just numeric answers.
Repeat key pseudocode and binary ideas in later units.