Algorithms

⚙️ Algorithms

Part 1 of 7 — Sequencing, Selection, Iteration, and Algorithm Analysis

What Is an Algorithm?

An algorithm is a finite set of step-by-step instructions for solving a problem or accomplishing a task. Every algorithm is built from three fundamental building blocks:

🔑 Any computable problem can be solved using just these three building blocks. This is a fundamental principle of computer science.

Algorithm Efficiency

Not all algorithms solve a problem equally fast. Efficiency measures how the number of steps grows as the input size grows.

Reasonable algorithms run in polynomial time (n, n squared, n cubed). Unreasonable algorithms run in exponential or factorial time (2^n, n!).

Concept Check 🎯

Searching Algorithms

Linear Search

Check each element one by one from start to end.

PROCEDURE linearSearch(list, target)
{
    FOR EACH item IN list
    {
        IF (item = target)
        {
            RETURN true
        }
    }
    RETURN false
}

• Works on any list (sorted or unsorted)
• Worst case: check all n items

Binary Search

Repeatedly divide a SORTED list in half.

PROCEDURE binarySearch(sortedList, target)
{
    low ← 1
    high ← LENGTH(sortedList)
    REPEAT UNTIL (low > high)
    {
        mid ← (low + high) / 2
        IF (sortedList[mid] = target)
            RETURN mid
        ELSE IF (target < sortedList[mid])
            high ← mid - 1
        ELSE
            low ← mid + 1
    }
    RETURN -1
}

• Requires a sorted list
• Each step eliminates half the remaining items
• Much faster for large datasets

Decidable vs Undecidable Problems

• Decidable: An algorithm exists that always produces a correct yes/no answer
• Undecidable: No algorithm can solve it for ALL possible inputs (e.g., the Halting Problem)

Applied Recall ✍️

1. Binary search requires the list to be _______ before searching.

2. An algorithm that takes 2^n steps for n inputs is classified as _______ (reasonable or unreasonable).

3. A problem for which no algorithm can produce a correct answer for ALL inputs is called _______.

Compare Algorithms 🔍

AP Exam Strategy: Algorithms

• Know the difference between linear search (unsorted, n steps) and binary search (sorted, log2(n) steps)
• Reasonable = polynomial (n, n squared). Unreasonable = exponential or factorial (2^n, n!)
• Heuristic algorithms find "good enough" solutions when optimal is unreasonable
• The Halting Problem is the key example of an undecidable problem — no program can determine if another program will halt for ALL inputs
• Every algorithm uses sequencing, selection, and/or iteration

AP-Style Application 🎯

⚙️ Algorithms

Part 2 of 7 — Key Processes

How Algorithms Execute Step by Step

An algorithm is a finite, ordered sequence of unambiguous steps. On the AP CSP exam you will trace pseudocode by hand. Master three control flows and you can trace anything.

AP pseudocode rule: assignment uses a ← 5. Comparison uses =. Lists are 1-indexed.

Concept Check 🎯

Tracing a Loop by Hand

    n ← 4     total ← 0     REPEAT n TIMES {       total ← total + n       n ← n − 1     }     DISPLAY(total)

Key trick: the loop count for REPEAT n TIMES is fixed when the loop starts (n = 4), even if n changes inside.

DISPLAY shows 10.

Selection With Compound Conditions

    IF (score ≥ 90 AND attendance ≥ 0.8) {       grade ← "A"     } ELSE IF (score ≥ 80 OR bonus = true) {       grade ← "B"     } ELSE {       grade ← "C"     }

AND requires both; OR requires at least one. NOT flips a Boolean.

Applied Recall ✍️

1. The three core control structures are sequence, selection, and _______.

2. AP pseudocode assignment uses the symbol _______ (write the name).

3. In REPEAT n TIMES, n is evaluated _______ times during the loop.

Targeted Practice 🔍

AP Exam Strategy: Reading Algorithms

• Trace with a table: one column per variable, one row per iteration. This catches off-by-one errors.
• For REPEAT N TIMES the count is fixed at the start; modifying the counter inside doesn't change how many times the block runs.
• For REPEAT UNTIL (cond) the block runs at least once and exits when cond becomes true after a pass.
• DeMorgan: NOT (A AND B) = (NOT A) OR (NOT B). The exam tests this.
• When in doubt, plug in boundary values (0, 1, n−1, n) — they are where bugs live.

AP-Style Application 🎯

⚙️ Algorithms

Part 3 of 7 — Patterns & Examples

Common Algorithmic Patterns

You will see the same building blocks again and again. Recognize them and tracing becomes pattern-matching.

Concept Check 🎯

Worked Example: Filter + Count

Goal: from prices, count how many are above 50 AND build a list of those prices.

    prices ← [42, 73, 51, 18, 99, 50]     count ← 0     expensive ← []     FOR EACH p IN prices {       IF (p > 50) {         count ← count + 1         APPEND(expensive, p)       }     }

Trace: 73 ✓, 51 ✓, 99 ✓. (50 fails because the test is strict >.) Output: 3 and [73, 51, 99].

Worked Example: Min Index, Not Just Min

Tracking the position of the minimum, not just the value.

    nums ← [8, 3, 6, 1, 9, 4]     minIdx ← 1     FOR i ← 2 TO LENGTH(nums) {       IF (nums[i] < nums[minIdx]) { minIdx ← i }     }

minIdx evolves: 1 → 2 (3 < 8) → 4 (1 < 3). Output: 4 (1-indexed position of the smallest value).

Applied Recall ✍️

1. A variable that builds up a running total is called an _______.

2. To pick out elements meeting a condition into a new list, use the _______ pattern.

3. To replace every element with f(element) without filtering, use the _______ pattern.

Targeted Practice 🔍

AP Exam Strategy: Pattern Recognition

• Skim pseudocode for the shape: is there a counter? An accumulator? A min/max comparison?
• Watch for strict vs. non-strict comparisons (> vs ≥). They change boundary results.
• Watch the starting value of an accumulator — wrong identity is a frequent FRQ deduction.
• For "first occurrence" patterns, remember to break/exit or guard with a flag so you don't overwrite a found index later.

AP-Style Application 🎯

⚙️ Algorithms

Part 4 of 7 — Connections & Interactions

How Algorithms Connect to Other CSP Topics

Algorithms don’t live in isolation. An efficient sort matters because of data size. A good search matters because the internet delivers gigabytes of records. The AP exam loves cross-topic questions.

Concept Check 🎯

Linear vs. Binary Search

For 1,000,000 items, linear can need a million comparisons; binary needs about 20. The connection: data structure (sortedness) directly determines which algorithm you can use.

Procedures Hide Algorithms

    PROCEDURE find(list, target) {       // body could be linear or binary search;       // callers don't need to know.     }

This is abstraction: callers call find without caring which algorithm runs inside. You can swap the implementation later for a faster one without changing any caller.

Algorithms and Impact

A recommendation algorithm that always returns the most-clicked content reinforces popularity bias — small differences compound into large gaps over millions of users. Algorithm choice has social consequences.

Applied Recall ✍️

1. Binary search requires the input list to be _______.

2. Hiding the implementation of an algorithm behind a procedure name is an example of _______.

3. Switching from an $n^{2}$ algorithm to an n algorithm is an example of an _______ improvement.

Targeted Practice 🔍

AP Exam Strategy: Cross-Topic Reasoning

• "Most efficient" almost always means lowest growth rate (n vs $n^{2}$ vs log n).
• If the question mentions a sorted list, binary search is on the table.
• If two algorithms produce identical output, the question is about efficiency, not correctness.
• Watch for cross-topic framing: "the algorithm runs on a server" hints at scalability; "the algorithm assigns loans" hints at bias/impact.

AP-Style Application 🎯

⚙️ Algorithms

Part 5 of 7 — Change Over Time

How Algorithms Scale

A "fast enough" algorithm at n = 100 may be unusable at n = 10,000,000. The AP exam tests whether you understand how running time grows with input size.

Concept Check 🎯

Reasonable vs. Unreasonable Algorithms

The CED uses two key terms:

• Reasonable: time grows polynomially (constant, log, linear, $n^{2}$, $n^{3}$, …).
• Unreasonable: time grows exponentially ($2^{n}$, n!, …) — quickly impossible to run.

A 30-element problem that needs to try every subset $(2^{30} \approx 1 billion)$ is borderline. At 50 elements $(2^{50} \approx 10^{15})$, no realistic computer finishes in your lifetime.

Heuristics: When Exact Is Too Slow

When an exact algorithm is unreasonable, we often use a heuristic — an approach that finds a good enough answer quickly without guaranteeing optimality.

Trade-off: speed vs. guaranteed optimality.

Decidable vs. Undecidable

Some problems can't be solved by any algorithm for all inputs (e.g., the Halting Problem). These are undecidable. Most exam-relevant problems are decidable; the question is whether they're tractable in reasonable time.

Applied Recall ✍️

1. An algorithm whose running time grows polynomially is called _______.

2. An algorithm that finds a good but not necessarily optimal solution faster is called a _______.

3. A problem that no algorithm can solve for all inputs is _______.

Targeted Practice 🔍

AP Exam Strategy: Scaling Questions

• For "how long does it take on 10× input?" multiply by the growth factor: linear → 10×, $n^{2}$ → 100×, log → tiny constant change.
• "Reasonable" = polynomial. "Unreasonable" = exponential.
• A heuristic ≠ a guarantee. If the answer must be optimal, a heuristic alone can't promise it.
• The Halting Problem is the canonical undecidable problem the exam might mention.

AP-Style Application 🎯

⚙️ Algorithms

Part 6 of 7 — Problem-Solving Workshop

Algorithms Workshop

Walk through end-to-end problems that combine sequence, selection, iteration, lists, and procedures — exactly the style of CED FRQs.

Concept Check 🎯

Worked Problem: Average Skipping Zeros

    PROCEDURE averageNonzero(scores) {       total ← 0       count ← 0       FOR EACH s IN scores {         IF (s ≠ 0) { total ← total + s; count ← count + 1 }       }       IF (count = 0) { RETURN 0 }       RETURN total / count     }

Test traces:

Worked Problem: Detecting a Pattern

Goal: return TRUE if a list contains two consecutive equal elements.

    PROCEDURE hasRun(list) {       FOR i ← 2 TO LENGTH(list) {         IF (list[i] = list[i − 1]) { RETURN TRUE }       }       RETURN FALSE     }

Why start at 2? list[i − 1] would be list[0] when i = 1, which doesn’t exist in 1-indexed pseudocode.

Applied Recall ✍️

1. When dividing two integers, you must guard against the divisor being _______.

2. When indexing list[i − 1] in a loop, the loop should start at _______ to avoid an out-of-range index in 1-indexed pseudocode.

3. A procedure that returns a Boolean usually starts with the verb _______ or "has".

Targeted Practice 🔍

AP Exam Strategy: FRQ-Style Tracing

• Build a trace table with one column per variable and one row per iteration before answering anything.
• Identify the pattern (accumulator? counter? min/max?) before chasing line-by-line logic.
• Always check edge cases: empty list, single element, all-the-same, all-zeros, negatives.
• For procedures that return a value, note whether RETURN exits early — this changes the trace.

AP-Style Application 🎯

⚙️ Algorithms

Part 7 of 7 — AP Review

AP Exam Recap — Algorithms

Cheat sheet for exam day. Match each construct to its AP-pseudocode shape and the most common bug.

Concept Check 🎯

Quick-Reference: Constructs and Pitfalls

Quick-Reference: Boolean Logic

• A AND B → both true.
• A OR B → at least one true.
• NOT (A AND B) = (NOT A) OR (NOT B) (DeMorgan).
• NOT (A OR B) = (NOT A) AND (NOT B).

Quick-Reference: Efficiency

• Polynomial = reasonable. Exponential = unreasonable.
• Linear search: O(n). Binary search (sorted): O(log n).
• Doubling input on $O(n^{2})$ → 4×; on O(log n) → +1 step.

Applied Recall ✍️

1. AP pseudocode lists are _______-indexed.

2. A REPEAT UNTIL loop runs the block at least _______ time(s) before checking the condition.

3. $\log_{2}$(1,048,576) equals approximately _______.

Targeted Practice 🔍

Final Exam Tips

• Always trace loops with a table; don’t eyeball them.
• Watch the boundaries: > vs ≥, list[1] vs list[0], REPEAT UNTIL post-test.
• Distinguish correctness (does it produce the right output?) from efficiency (how fast / how much memory?).
• For pseudocode FRQs, write at least one example trace in your scratch space.
• "Most appropriate" usually means efficient AND correct AND simplest — eliminate options that fail any one.

AP-Style Application 🎯