AP Computer Science Principles Unit 3 Review: Algorithms & Programming Fundamentals

A variable is an abstraction that holds one value at a time. The AP exam reference sheet uses the left-arrow operator (a <- expression) to assign a value. The value stored is always the most recent assignment. Meaningful variable names improve readability.

• Assignment operator: The left-arrow <- evaluates the expression on the right and stores a copy of the result in the variable on the left.
• Most-recent-assignment rule: If a variable is assigned multiple times, its current value is whatever was assigned last. Tracing line by line is the reliable method.
• Data types: AP CSP variables can hold numbers, Booleans (true/false), strings, or lists. The type affects what operations make sense on the value.
• Sequence of assignments: When b <- a is followed by a <- 2, b still holds the original value of a because assignment copies the value at that moment.

A list is an ordered sequence of elements, each identified by an index starting at 1 on the AP exam. Data abstraction gives a collection a single name, hiding the details of how individual elements are stored. This makes programs easier to build and maintain.

• Index: A natural number that identifies an element's position in a list. The first element is at index 1 in AP pseudocode.
• Data abstraction: Naming a collection of values so the program can refer to the group without specifying every element's storage detail.
• List as a variable: A list variable holds the entire ordered collection. Assigning one list to another copies the list at that moment.
• Managing complexity: Using a list instead of separate variables reduces code length and makes it easier to add, remove, or process related values together.

An expression evaluates to a single value. Arithmetic expressions use +, -, *, /, and MOD. MOD returns the remainder and has the same precedence as * and /. String concatenation joins two strings end-to-end. A substring is a portion of an existing string.

• MOD operator: a MOD b returns the remainder when a is divided by b. Example: 17 MOD 5 = 2. Useful for checking divisibility and cycling through values.
• Order of operations: Standard math precedence applies. MOD, *, and / are evaluated before + and -. Parentheses override default precedence.
• String concatenation: Joins two or more strings into one new string placed end-to-end. For example, 'hello' + ' world' produces 'hello world'.
• Substring: A part of an existing string extracted by specifying a start and end position.

A Boolean value is either true or false. Relational operators compare two values and produce a Boolean. Logical operators combine Boolean values. The AP reference sheet provides NOT, AND, and OR.

• Relational operators: =, not-equal, <, >, <=, >= compare two values and return true or false.
• NOT: Reverses a Boolean: NOT true = false, NOT false = true.
• AND: True only when both conditions are true; false otherwise.
• OR: True when at least one condition is true; false only when both are false.

Selection uses IF and IF/ELSE statements to execute different code blocks based on a Boolean condition. Nested conditionals place one IF inside another, allowing more specific branching. Tracing every possible path is the key exam skill.

• IF statement: Executes a block only when the condition is true; does nothing if the condition is false.
• IF/ELSE statement: Executes the first block when the condition is true and the second block when it is false. Exactly one block always runs.
• Nested conditional: A conditional statement placed inside another conditional's block. The inner condition is only evaluated if the outer condition is true.
• Tracing execution paths: To determine output, substitute specific values and follow which branches execute. Check every branch, not just the first one.

Iteration repeats a block of statements. REPEAT n TIMES runs the block exactly n times. REPEAT UNTIL(condition) runs the block until the condition becomes true, checking the condition before each iteration. If the condition is true at the start, the block never runs.

• REPEAT n TIMES: Executes the block exactly n times regardless of what happens inside the block.
• REPEAT UNTIL(condition): Checks the condition before each pass. Stops when the condition is true. If true initially, the block runs zero times.
• Infinite loop: Occurs in REPEAT UNTIL when the stopping condition can never become true. The program runs forever without terminating.
• Accumulator pattern: A variable initialized before the loop that collects a running total, count, or other value updated each iteration.

Algorithms can be created from scratch, by combining existing algorithms, or by modifying them. Two algorithms that look different can produce the same result. Some conditional statements can be rewritten as equivalent Boolean expressions and vice versa. Knowing common building-block algorithms speeds up development.

• Algorithm equivalence: Two algorithms are equivalent if they always produce the same result or side effect for every possible input.
• Building-block algorithms: Common patterns include finding a maximum or minimum, computing a sum or average, checking divisibility with MOD, and navigating a robot through a maze.
• Combining algorithms: Using a correct existing algorithm as a component of a new one reduces development time and the chance of introducing errors.
• Conditional-Boolean equivalence: An IF/ELSE that sets a variable to true or false can often be rewritten as a single Boolean expression assigned directly to that variable.

The AP reference sheet provides specific list operations. Indexing starts at 1. INSERT shifts elements right and increases length. REMOVE shifts elements left and decreases length. APPEND adds to the end. FOR EACH traversal visits every element in order.

• aList[i]: Accesses the element at index i. The first element is aList[1].
• INSERT(aList, i, value): Places value at index i, shifting all elements at index i and beyond one position to the right. List length increases by 1.
• REMOVE(aList, i): Removes the element at index i, shifting all elements after it one position to the left. List length decreases by 1.
• FOR EACH item IN aList: Assigns item to each element in order from index 1 to the last index, executing the block once per element.
• Linear search: Checks each element one by one until the target is found or the list ends. Works on unsorted data.

Binary search finds a value in a sorted data set by checking the middle element, then eliminating the half that cannot contain the target, and repeating. It requires sorted data and is more efficient than linear search for large data sets.

• Sorted data requirement: Binary search only works correctly when the data is already sorted. Applying it to unsorted data produces unreliable results.
• Halving the search space: Each iteration eliminates half the remaining elements, so the number of steps grows much more slowly than the data set size.
• Efficiency advantage: Binary search reaches a result in far fewer steps than linear search when the data set is large and sorted.

A procedure is a named group of instructions with optional parameters and a return value. Calling a procedure passes arguments to its parameters, executes the body, and returns control to the call site. Procedural abstraction lets you use a procedure by knowing what it does, not how it works internally. Modularity breaks a program into subprograms, each solving one part of the problem.

• Parameters vs arguments: Parameters are the input variables listed in the procedure definition. Arguments are the actual values passed when the procedure is called.
• RETURN statement: Sends a value back to the call site and immediately ends the procedure. The returned value can be stored in a variable.
• Flow of control: A procedure call interrupts sequential execution, runs the procedure body, then resumes at the line immediately after the call.
• Procedural abstraction: Naming a process so callers only need to know its inputs and outputs, not its internal steps. Enables code reuse and simplifies debugging.
• Modularity: Dividing a program into separate procedures, each responsible for one subproblem, so the overall program is easier to read, test, and modify.

A software library is a collection of pre-written procedures available for use in new programs. An API specifies how those procedures behave and how to call them. Documentation is required to understand what a library provides and how to use it correctly.

• Library: A collection of procedures that can be imported and called in a program without rewriting the underlying code.
• API: A specification that defines the inputs, outputs, and behavior of each procedure in a library. It is the contract between the library and the programmer using it.
• Documentation: Written descriptions of what each library procedure does, what arguments it accepts, and what it returns. Without documentation, an API cannot be used reliably.
• Complexity reduction: Libraries allow programmers to build on existing correct code, reducing the amount of new code that must be written and tested.

RANDOM(a, b) returns a random integer from a to b, inclusive. Each integer in the range is equally likely. Because the result varies each run, programs using RANDOM can produce different outputs on different executions.

• RANDOM(a, b): Generates and returns one integer chosen uniformly at random from a through b, including both endpoints. RANDOM(1, 6) simulates a six-sided die.
• Inclusive endpoints: Both a and b are possible results. The total number of possible values is b - a + 1.
• Non-deterministic output: A program that calls RANDOM may produce a different result each time it runs, which is useful for simulations, games, and randomized algorithms.

A simulation is an abstraction of a real-world object or phenomenon built for a specific purpose. It uses changing values to model a system's behavior, allowing investigation without the cost, danger, or scale of the real event. Simulations simplify reality and can introduce bias based on what is included or excluded.

• Simulation as abstraction: A simulation removes or simplifies real-world details to focus on the aspects relevant to the question being investigated.
• Simulation bias: The choices about which real-world elements to include or exclude shape the simulation's results. Leaving out a key factor can make results misleading.
• When simulations are useful: Simulations are most valuable when real experiments are too expensive, too dangerous, too slow, too fast, or physically impossible to run.
• Random values in simulations: RANDOM is often used inside simulations to model unpredictable real-world variation, such as weather events or population behavior.

Efficiency measures how many computational resources an algorithm uses as input size grows. Algorithms that run in polynomial time (constant, linear, quadratic) are considered to run in reasonable time. Algorithms with exponential or factorial growth run in unreasonable time and become impractical for large inputs. Heuristics provide approximate solutions when exact solutions would take too long.

• Reasonable time: Polynomial efficiency or lower. The algorithm remains practical as input size increases.
• Unreasonable time: Exponential or factorial efficiency. The algorithm becomes impractical very quickly as input size grows even slightly.
• Heuristic: An approach that finds a good-enough approximate solution when finding the optimal solution would require unreasonable time.
• Decision vs optimization problem: A decision problem asks yes or no (is there a path from A to B?). An optimization problem asks for the best solution (what is the shortest path from A to B?).

A decidable problem is one for which an algorithm can always produce a correct yes or no answer for every input. An undecidable problem is one for which no such algorithm exists. Some specific instances of an undecidable problem may still be solvable, but no single algorithm handles all instances correctly.

• Decidable problem: A decision problem where an algorithm can be written that always gives the correct yes or no answer for every possible input. Example: is a number even?
• Undecidable problem: A decision problem where no algorithm can always give a correct yes or no answer for every possible input, no matter how the algorithm is designed.
• Instance-specific solvability: An undecidable problem may have some inputs for which an algorithm gives the right answer, but there is no algorithm that works correctly for all inputs.