Welch Teaching & CoachingComputer Science · AP CSP
← AP CSP Unit Hub
AP COMPUTER SCIENCE PRINCIPLES · UNIT 5

Algorithms, Efficiency & Simulation

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.

Site lessonOfficial AP topicsSelected CodeHS lessons
5.1 Searching, sortedness and correctness3.117.5 Simulation; CodeHS 17.1 Preparation (supplement)
5.2 Counting operations and growth3.17CodeHS 17.1 Preparation; supplementary conceptual practice
5.3 Heuristics and optimization3.17Supplement to CodeHS (no direct required lesson)
5.4 Simulation and randomness3.15–3.164.9 Random Numbers; 7.5 Simulation
5.5 Undecidable problems and limits3.18CodeHS 17.1 Preparation (supplement)

Content notes, vocabulary & worked examples

Each lesson ends with two quick checks. Open each answer only after attempting the problem.

Lesson 5.1 · AP 3.11 · 1–2 blocks

Searching, sortedness and correctness

CodeHS: 7.5 Simulation; CodeHS 17.1 Preparation (supplement)

Learning targets

  • Trace linear and binary search.
  • Explain why binary search needs sorted data.

Core notes

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
Up to n comparisons.
Lesson 5.2 · AP 3.17 · 1–2 blocks

Counting operations and growth

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.
Lesson 5.3 · AP 3.17 · 1–2 blocks

Heuristics and optimization

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
No.
Lesson 5.4 · AP 3.15–3.16 · 1–2 blocks

Simulation and randomness

CodeHS: 4.9 Random Numbers; 7.5 Simulation

Learning targets

  • Create a model with input assumptions.
  • Interpret variation in repeated trials.

Core notes

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.
Lesson 5.5 · AP 3.18 · 1–2 blocks

Undecidable problems and limits

CodeHS: CodeHS 17.1 Preparation (supplement)

Learning targets

  • 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.

Lesson videos & resources

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.

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.

Additional concept resources

Video selections are topic- and platform-matched. Teachers should check account availability and assign individual CodeHS/AP Daily clips from their course dashboards.

Interactive inquiry · Search race & stochastic models

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.

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.

LessonAPCodeHSMeasurable targetsAssessment specifications
5.1 Searching, sortedness and correctness3.117.5 Simulation; CodeHS 17.1 Preparation (supplement)Trace linear and binary search.; Explain why binary search needs sorted data.2 quick checks + 3 exam-bank items; lab discussion / exit ticket
5.2 Counting operations and growth3.17CodeHS 17.1 Preparation; supplementary conceptual practiceCompare linear, quadratic, exponential growth.; Distinguish measured time from operation counts.2 quick checks + 3 exam-bank items; lab discussion / exit ticket
5.3 Heuristics and optimization3.17Supplement to CodeHS (no direct required lesson)Compare exact and heuristic solutions.; Evaluate why speed may come at the expense of optimality.2 quick checks + 3 exam-bank items; lab discussion / exit ticket
5.4 Simulation and randomness3.15–3.164.9 Random Numbers; 7.5 SimulationCreate a model with input assumptions.; Interpret variation in repeated trials.2 quick checks + 3 exam-bank items; lab discussion / exit ticket
5.5 Undecidable problems and limits3.18CodeHS 17.1 Preparation (supplement)Contrast unreasonable runtime with undecidability.; Recognize that no general algorithm solves every possible problem.2 quick checks + 3 exam-bank items; lab discussion / exit ticket

Summative assessment blueprint

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.

Source and alignment notes

Continue through the course