Variables and Assignments

A variable is an abstraction inside a program that holds a single value and has a name. The value can change as the program runs. An assignment evaluates the expression on the right, then stores the result in the variable on the left (written ← in AP pseudocode).

score ← 10
score ← score + 5      // evaluate 10 + 5, store 15 in score
DISPLAY(score)         // 15

• A variable holds only its most recent value; assigning a new value replaces the old one.
• Common data types: integer, real number, string, Boolean.
• Use meaningful names (totalCost not x) so code is easier to read.
• Swapping two variables needs a temporary variable: temp ← a, a ← b, b ← temp.

Data Abstraction

Data abstraction hides the details of how data is stored so programmers can work with a simpler idea. A list is the main example: it stores many values under a single name.

// Without a list: score1, score2, score3 ... (hard to scale)
scores ← [82, 91, 77, 68]     // one name, many values

• Lists manage complexity — you don't need a separate variable for every item.
• Code using a list can handle any number of items without being rewritten, so it is easier to develop and maintain.
• Naming a collection (like scores) gives it meaning, which makes the program easier to read.

Mathematical Expressions

Expressions combine values, variables, and operators. AP pseudocode uses + − * / and MOD.

• Order of operations follows normal math: parentheses, then * / MOD, then + −, left to right.
• n MOD 2 = 0 tests whether n is even.
• MOD is also useful for wrap-around, like a clock or cycling through list positions.

Strings

A string is an ordered sequence of characters (letters, digits, symbols, spaces). Strings are written in quotes.

• Length — the number of characters, including spaces.
• Concatenation — joining two strings end to end: "Sun" and "shine" become "Sunshine".
• Substring — a part of an existing string: "com" is a substring of "computer".
• String operations are available as procedures in most languages, though the exact names differ.

first ← "Ada"
last  ← "Lovelace"
full  ← first + " " + last     // "Ada Lovelace" (concatenation)

Boolean Expressions

A Boolean value is true or false. Boolean expressions use relational operators and logical operators.

Conditionals

Selection lets a program choose which statements to run based on a Boolean condition. AP pseudocode uses IF and an optional ELSE.

IF (temp > 30)
{
    DISPLAY("Hot")
}
ELSE
{
    DISPLAY("Comfortable")
}

• If the condition is true, the IF block runs; otherwise the ELSE block runs (if present).
• Without an ELSE, nothing happens when the condition is false.

Nested Conditionals

A nested conditional places one conditional inside another, allowing more than two outcomes. AP pseudocode has no "else if", so extra choices go inside ELSE.

IF (grade ≥ 90)
{
    DISPLAY("A")
}
ELSE
{
    IF (grade ≥ 80)
    {
        DISPLAY("B")
    }
    ELSE
    {
        DISPLAY("C or below")
    }
}

• The inner conditional only runs if the outer branch containing it is taken.
• Order matters: check the strictest condition first.

Iteration

Iteration repeats a block of statements. AP pseudocode has three forms:

i ← 1
sum ← 0
REPEAT UNTIL (i > 4)
{
    sum ← sum + i
    i ← i + 1
}
DISPLAY(sum)      // 10

• If the REPEAT UNTIL condition is true at the start, the loop body never runs.
• If the condition never becomes true, you get an infinite loop.

Developing Algorithms

An algorithm is a finite set of instructions that accomplishes a task. Every algorithm is built from sequencing, selection, and iteration.

• Algorithms can be described in natural language, flowcharts, or pseudocode, and then coded in any language.
• Different algorithms can solve the same problem, and they can differ in efficiency.
• New algorithms can be built by combining or modifying existing ones.

Common patterns to know: finding the maximum, summing/averaging, counting items that meet a condition, and linear search.

max ← nums[1]
FOR EACH n IN nums
{
    IF (n > max)
    {
        max ← n
    }
}
DISPLAY(max)

Lists

A list is an ordered sequence of elements. Each element has an index. In AP pseudocode, indexes start at 1.

• Traversal visits each element — with FOR EACH or a loop over indexes.
• Linear (sequential) search checks elements one by one from the start; it works on any list, sorted or not.
• Using an index outside 1 to LENGTH(list) causes an error.

Binary Search

Binary search finds a target in a sorted list by repeatedly checking the middle element and discarding the half that can't contain the target.

1. Look at the middle element.
2. If it equals the target, done.
3. If the target is smaller, keep the lower half; if larger, keep the upper half.
4. Repeat on the remaining half until found or empty.

• The list must be sorted first.
• Each step halves the search space, so it needs roughly log₂ n steps — a list of 1024 items takes about 10 steps.
• For large sorted lists it is much faster than linear search, which may check all n elements.

Calling Procedures

A procedure is a named group of programming instructions (also called a method or function). You call it to run its code.

• Parameters are the input variables in the procedure's definition; arguments are the actual values passed when calling.
• A procedure may return a value (RETURN), ending the procedure and handing a result back.
• When called, the program jumps to the procedure, runs it, then continues after the call.

PROCEDURE doubleIt(x)
{
    RETURN (x * 2)
}

result ← doubleIt(7)     // 7 is the argument → result is 14

Developing Procedures

Procedural abstraction lets you use a procedure without knowing how it works inside. It supports modularity: breaking a big program into smaller reusable parts.

• Procedures reduce repeated code — write once, call many times.
• Parameters generalize a procedure so it works with different inputs.
• Programmers can change the internal code of a procedure without changing the code that calls it, as long as it still does the same job.
• Good documentation states what a procedure does, its parameters, and what it returns.
• Procedures make programs easier to debug, test, and maintain.

PROCEDURE average(a, b, c)
{
    RETURN ((a + b + c) / 3)
}

Libraries

A library is a collection of procedures that can be used in programs. An API (application programming interface) describes how to use those procedures — their names, parameters, and what they return.

• Libraries save time because the code already exists and has been tested.
• You need to read the documentation to use a library correctly.
• Libraries and APIs let you build complex programs (graphics, maps, data analysis) quickly.
• Give credit and follow licensing when using other people's code.

Random Values

Random values make a program behave differently each time. In AP pseudocode, RANDOM(a, b) returns an integer from a to b, inclusive, with each value equally likely.

roll ← RANDOM(1, 6)       // 1, 2, 3, 4, 5 or 6
IF (RANDOM(1, 2) = 1)
{
    DISPLAY("Heads")
}
ELSE
{
    DISPLAY("Tails")
}

• Because the result is unpredictable, the same program can produce different output on different runs.
• Used in games, simulations, and testing.

Simulations

A simulation is a program model of a real-world object or event. It is an abstraction that includes some details and leaves out others.

• Used when real experiments are too dangerous, slow, expensive, or impossible (e.g. crash tests, weather, disease spread).
• Often use random values to mimic real unpredictability.
• Allow testing many scenarios by changing variables.
• Limitations: results depend on the simplifications and assumptions chosen, so a simulation may contain bias or miss real-world factors.

Algorithmic Efficiency

Efficiency describes how many steps (or how much time or memory) an algorithm needs as the input size n grows.

• A heuristic is an approach that finds a good-enough answer when finding the best one takes too long.
• A decision problem has a yes/no answer; an optimization problem asks for the best solution.
• Efficiency is often judged by counting steps, not by timing on one computer.

Undecidable Problems

Some problems cannot be solved by any algorithm for every input.

• A decidable problem has an algorithm that always gives a correct yes/no answer for every input.
• An undecidable problem has no such algorithm — no program can solve it for all possible inputs.
• Famous example: the halting problem — deciding whether any given program will eventually stop or run forever.
• An undecidable problem may still be solvable for some specific inputs.