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.

⚙️ 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.

⚙️ 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

⚙️ 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², n³, …).
• Unreasonable: time grows exponentially (2ⁿ, n!, …) — quickly impossible to run.

A 30-element problem that needs to try every subset (2³⁰ ≈ 1 billion) is borderline. At 50 elements (2⁵⁰ ≈ 10¹⁵), no realistic computer finishes in your lifetime.

⚙️ 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.

⚙️ 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).