AP Computer Science Principles · Unit 3 · 30-35% of the exam · about 120 minutes

Unit 3: Algorithms and Programming

By the end: Read, trace and write Exam Reference Sheet pseudocode with variables, expressions, strings, Booleans, conditionals, loops, lists and procedures; use linear and binary search, random values and simulations; and judge an algorithm's efficiency and whether a problem can be solved at all.

Mr. Thompkins
  1. 3.1 Variables and assignments · 8 min

    One name, one value at a time

    • A variable holds one value at a time: the most recent value assigned.
    • x ← expression: evaluate the right side with current values, then store it in x.
    • Assignment copies a value. Changing one variable later doesn't change another.
  2. 3.3 Mathematical expressions · 8 min

    Arithmetic, order, and the remainder operator

    • An algorithm is a finite set of steps. Every algorithm uses sequencing, selection and iteration.
    • An expression produces one value. Operators: +, -, *, /, MOD.
    • a MOD b is the remainder of a ÷ b. Same priority as * and /, before + and -.
  3. 3.4 Strings · 6 min

    Joining and cutting text

    • A string is an ordered sequence of characters in quotes. "42" is text, not a number.
    • Concatenation joins strings end to end, adding nothing between them.
    • A substring is part of a string. Exam questions define their own string procedures.
  4. 3.5 Boolean expressions · 8 min

    True, false, AND, OR, NOT

    • A Boolean is true or false. Relational operators: =, ≠, >, <, ≥, ≤.
    • AND: both true. OR: at least one true. NOT: flips.
    • Inside a range: AND. Outside a range: OR.
  5. 3.6 and 3.7 Conditionals and nested conditionals · 9 min

    Choosing a path

    • IF runs its block only when the condition is true. IF/ELSE runs exactly one of two blocks.
    • Nested conditionals: an IF inside an IF or ELSE, for decisions that depend on earlier ones.
    • Separate IFs are each checked; a later true IF can overwrite an earlier one. Order matters.
  6. 3.8 Iteration · 10 min

    Two loops, and exactly when they stop

    • REPEAT n TIMES: exactly n passes.
    • REPEAT UNTIL: checks before every pass; stops at the first true. It can run 0 times.
    • If the condition never becomes true, the loop is infinite.
  7. 3.9 Developing algorithms · 10 min

    Many ways to solve it, and the robot

    • Different algorithms can solve the same problem; similar-looking ones can give different results.
    • Check equivalence on every case, especially boundaries and ties.
    • Know the building blocks: max/min, sum/average, divisibility (MOD), robot paths.
  8. 3.2 and 3.10 Data abstraction and lists · 10 min

    Many values under one name

    • A list is an ordered sequence of elements. Indexes go from 1 to LENGTH(aList); others are errors.
    • INSERT and REMOVE shift later elements. Assignment to aList[i] replaces without shifting.
    • Data abstraction: one name for a collection, hiding details. It manages complexity.
  9. 3.10 List traversal and linear search · 9 min

    Visiting every element

    • Traversal: visit elements one by one. Complete or partial.
    • FOR EACH gives values; an index loop gives positions.
    • Max/min: start with the first element. Sum: start at 0. Average: sum ÷ LENGTH.
  10. 3.11 Binary search · 8 min

    Halve it, halve it again

    • Binary search: check the middle of sorted data, eliminate half, repeat.
    • The data must be sorted. Linear search works on anything.
    • Worst case: about log₂ n checks. Doubling n adds one check.
  11. 3.12 and 3.13 Calling and developing procedures · 11 min

    Name it once, use it everywhere

    • A procedure is a named group of instructions. Parameters are its input variables; arguments are the values in a call.
    • A call jumps into the procedure and returns to the next statement. RETURN sends back a value and ends the procedure at once.
    • Procedural abstraction: use a procedure knowing what it does, not how. Modularity: split a program into subprograms.
  12. 3.14 to 3.16 Libraries, random values and simulations · 10 min

    Borrowed code, chance, and models of the world

    • A library holds reusable procedures. An API specifies how they behave; documentation explains how to use them.
    • RANDOM(a, b): a whole number from a to b, inclusive, each equally likely. That's b - a + 1 values.
    • Probability: favorable equally likely outcomes ÷ total. For two calls, count pairs.
  13. 3.17 and 3.18 Algorithmic efficiency and undecidable problems · 10 min

    Fast enough, and possible at all

    • Efficiency: resources (usually time) as a function of input size. Estimate by counting statement executions.
    • Polynomial (n, n², n³): reasonable. Exponential (2ⁿ) or factorial: unreasonable.
    • A heuristic gives a good-enough, not guaranteed optimal, answer when exact methods are impractical.
  14. Unit 3 wrap-up · 9 min

    Put it together