Comprehensive Guide to Big Idea 3: Algorithms and Programming

Variable

An abstract placeholder used to store data values in programming.

Data Abstraction

Provides the lowest level of data abstraction using variable names instead of binary memory addresses.

Data Type

A specification of the type of data a variable can hold, such as integer, string or boolean.

Integer

Whole numbers, e.g., 5 or -10.

Float

Numbers that include decimals, e.g., 3.14 or 0.05.

String

An ordered sequence of characters enclosed in quotes, e.g., 'Hello World'.

Boolean

Values that can be true or false.

Assignment

The process of setting a variable's value, typically using the assignment operator.

Left-facing Arrow Notation

A notation used in AP CSP to assign values, e.g., variable ← expression.

Destructive Assignment

Assigning a new value that completely overwrites the old value.

Directional Assignment

Data moves from right to left in assignment operations.

Swap Pattern

A technique for exchanging values of two variables using a temporary variable.

List

An ordered collection of elements that allows referring to a set of data with a single variable name.

Element

An individual value within a list.

Index

The position of an element in a list, with 1-based indexing in AP CSP.

INSERT method

A list operation that adds a value at a specific index, shifting existing elements.

APPEND method

A list operation that adds a value to the end of the list.

REMOVE method

A list operation that deletes an item at a specific index.

LENGTH method

A list operation that returns the number of items in the list.

Concatenation

Joining two strings together.

Sequencing

Executing algorithms in the order given by the code statements.

Selection

Executing parts of an algorithm based on a condition being true or false.

Boolean Expression

The condition tested within an IF statement.

Relational Operators

Operators used to compare values, such as =, ≠, >, <.

Nested Conditionals

Placing one IF statement inside another for complex logic.

Iteration

A repetitive portion of an algorithm that executes multiple times.

REPEAT n TIMES

A loop that runs a block of code exactly n times.

REPEAT UNTIL (condition)

An indefinite loop that runs while the condition is false.

FOR EACH item IN list

A loop that automatically iterates over each element in a list.

Algorithm

A finite set of instructions to accomplish a specific task.

Sum/Average Algorithm

An algorithm that calculates the total or average value from a list.

Max/Min Algorithm

An algorithm that finds the maximum or minimum value within a list.

Linear Search

A method of finding a target in a list by checking each item sequentially.

Binary Search

A method of searching a sorted list by repeatedly dividing the search interval in half.

Procedural Abstraction

A method of simplifying code by using named procedures to encapsulate functionality.

Parameter

A variable defined in a procedure that accepts input values.

Argument

The actual value passed to a procedure when it is invoked.

Library

A collection of useful procedures for programming.

API (Application Programming Interface)

A specification that outlines the expected behavior of procedures in a library.

Randomness

Non-deterministic behavior often used in simulations and cryptography.

RANDOM(a, b)

A procedure that returns a random integer between a and b, inclusive.

Simulation

A program that mimics real-world events or systems.

Algorithm Efficiency

Measured by the number of steps required as a function of input size.

Reasonable Time

Polynomial time complexity, where the number of steps is a polynomial function of input size.

Unreasonable Time

Exponential or factorial time complexity, which grows impractically large for small increases in input size.

Heuristic

An approach that produces an approximate solution when exact solutions are too slow.

Decidable Problem

A problem for which an algorithm can be constructed that produces a correct yes-or-no answer for every input.

Undecidable Problem

A problem for which no algorithm can provide a correct yes-or-no answer for all possible inputs.

Common Mistake: 0-based vs. 1-based Indexing

Mistake of assuming list[1] is the second item instead of the first.

Common Mistake: Robot Orientation

Not tracking the robot's current heading, leading to erroneous movements.

Common Mistake: REPEAT UNTIL Logic

Misunderstanding the loop's condition leading to unintended behavior.

Common Mistake: Binary Search Requirements

Attempting binary search on unsorted data, leading to failure.

Common Mistake: Swapping Variables

Incorrectly swapping variable values without using a temporary variable.