Unit 3 · Algorithms and Programming

Variable ● (core concept) — An abstraction inside a program that can hold a value, with associated data storage representing one value at a time. That value can itself be a list or other collection containing multiple values.

Assignment ● (core concept) — The operation that changes the value a variable holds. The variable keeps the most recently assigned value; assigning an expression stores a copy of its result, so later changes to the variable do not affect values copied from it earlier.

Data types ● (core concept) — Categories of data a programming language provides, referenced using variables. Common types include numbers, Booleans, lists, and strings; some values are better suited to one type than another.

Meaningful variable names ○ — Descriptive names for variables, which help with the readability of program code and make clear what values the variables represent.

List ● (core concept) — An ordered sequence of elements, written for example as [value1, value2, value3, ...], where value1 is the first element, value2 the second, and so on.

Element ● (core concept) — An individual value in a list, each assigned a unique index.

Index ● (core concept) — A natural number used to reference an element in a list or string. In the exam reference, list indices run from 1 through the number of elements; an index below 1 or above the list length produces an error and terminates the program.

String ● (core concept) — An ordered sequence of characters.

Data abstraction ● (core concept) — The separation between a data type's abstract properties and the concrete details of its representation. Giving a collection of data a name lets a program treat multiple related items as a single value without referencing representation details, which manages complexity and makes programs easier to develop and maintain.

Array ○ — An alternative name some programming languages use for a list.

Algorithm ● (core concept) — A finite set of instructions that accomplishes a specific task. Algorithms can be expressed as natural language, diagrams, pseudocode, or in a programming language.

Sequencing ● (core concept) — Applying each step of an algorithm in the order in which the code statements are given. Sequential statements execute in the order they appear.

Pseudocode ● (core concept) — An informal, programming-language-free notation for expressing algorithms. Every algorithm can be constructed from combinations of sequencing, selection, and iteration, so pseudocode built from those three constructs can describe any algorithm.

Expression ● (core concept) — A value, variable, operator, or procedure call that returns a value. Expressions are evaluated to produce a single value, following the order of operations defined by the programming language.

Arithmetic operators ● (core concept) — Addition, subtraction, multiplication, division, and MOD. The expression a MOD b evaluates to the remainder when a is divided by b (for example, 17 MOD 5 is 2), and MOD shares precedence with multiplication and division.

String concatenation ● (core concept) — Joining two or more strings end-to-end to make a new string.

Substring ● (core concept) — Part of an existing string.

Boolean value ● (core concept) — A value that is either true or false.

Relational operators ● (core concept) — The operators =, ≠, >, <, ≥, and ≤, used to test the relationship between two variables, expressions, or values. A comparison using a relational operator evaluates to a Boolean value.

Logical operators ● (core concept) — NOT, AND, and OR, which evaluate to a Boolean value. NOT is true when its condition is false; AND is true only when both conditions are true; OR is true when at least one condition is true.

Selection ● (core concept) — Determining which parts of an algorithm are executed based on whether a condition is true or false.

Conditional statement (if statement) ● (core concept) — A statement that affects the sequential flow of control by executing a block of statements only when a Boolean expression evaluates to true; no action is taken when it is false.

If-else statement ● (core concept) — A conditional that executes one block of statements when its Boolean expression is true and a different block when it is false.

Nested conditional ● (core concept) — A conditional statement placed inside another conditional statement.

Iteration ● (core concept) — A repeating portion of an algorithm. Iteration repeats a specified number of times or until a given condition is met.

REPEAT n TIMES ● (core concept) — A loop construct in which the block of statements is executed exactly n times.

REPEAT UNTIL(condition) ● (core concept) — A loop construct that repeats its block of statements until the Boolean condition evaluates to true. The condition is checked before the loop body, so if it is true initially the body never executes.

Infinite loop ● (core concept) — A loop whose ending condition will never evaluate to true, so it repeats forever. It is a common defect in REPEAT UNTIL loops.

Algorithm equivalence ● (core concept) — Different algorithms can be written to accomplish the same task yet yield different side effects or results. Relatedly, some conditional statements can be rewritten as equivalent Boolean expressions, and some Boolean expressions as equivalent conditionals.

Reusing existing algorithms ● (core concept) — Creating new algorithms by combining or modifying known ones, such as finding a maximum or minimum, computing a sum or average, testing divisibility, or tracing a path through a maze. Using correct existing algorithms as building blocks reduces development time, reduces testing, and simplifies identifying errors.

Side effect ● (core concept) — An observable change a procedure or algorithm causes beyond its returned result, such as displaying output or modifying a variable. Comparing algorithms requires checking both their results and their side effects.

List indexing (access) ● (core concept) — Reading an element of a list by its index. In the exam reference, the first element is at index 1 and is accessed with the notation aList[1]; a value can also be copied from aList[i] into a variable or assigned into aList[i].

INSERT, APPEND, REMOVE, LENGTH ● (core concept) — Basic list procedures: INSERT(aList, i, value) shifts elements at indices i and above to the right and places value at index i; APPEND(aList, value) adds value to the end; REMOVE(aList, i) deletes the item at index i and shifts later elements left; LENGTH(aList) returns the number of elements.

List traversal ● (core concept) — Visiting the elements of a list using iteration. A complete traversal accesses every element; a partial traversal accesses only a portion of the elements.

FOR EACH loop ● (core concept) — A loop that assigns each element of a list, in order from first to last, to a variable and executes a block of statements once for each assignment.

Linear (sequential) search ● (core concept) — A search that checks each element of a list in order until the desired value is found or all elements have been checked.

Binary search ● (core concept) — A search algorithm that starts at the middle of a sorted data set and eliminates half of the data, repeating until the desired value is found or all elements have been eliminated. Data must be in sorted order for binary search to work.

Binary search efficiency ● (core concept) — Binary search is often more efficient than sequential (linear) search on sorted data, because each iteration discards half of the remaining elements instead of checking them one by one.

Procedure ● (core concept) — A named group of programming instructions that may have parameters and return values. Procedures are called by different names, such as method or function, depending on the programming language.

Parameter vs. argument ● (core concept) — Parameters are the input variables of a procedure; arguments are the specific values assigned to those parameters when the procedure is called.

Procedure call ● (core concept) — Invoking a procedure by name with arguments. The call interrupts sequential execution: the program runs the procedure's statements first, then returns control to the statement immediately after the call once the last statement or a RETURN has executed.

Return value ● (core concept) — A value a procedure sends back to its caller. RETURN(expression) returns control to the point where the procedure was called and provides the value of the expression; it can appear anywhere in the procedure and returns immediately.

DISPLAY ○ — An exam-reference procedure, DISPLAY(expression), that displays the value of an expression followed by a space.

INPUT ○ — An exam-reference procedure, INPUT(), that accepts a value from the user and returns that input value.

Procedural abstraction ● (core concept) — A common abstraction that gives a process a name so a procedure can be used by knowing what it does rather than how it does it. It lets a large problem be solved through smaller subproblems, extracts shared features to avoid duplicating code, enables reuse across many input values via parameters, improves readability, and allows a procedure's internals to change as long as its behavior is preserved.

Modularity ● (core concept) — The subdivision of a computer program into separate subprograms, each handling a smaller, more manageable piece of the overall problem.

Software library ● (core concept) — A collection of procedures that may be reused when creating new programs. Existing code segments can come from internal or external sources, and using libraries simplifies the task of creating complex programs.

API (application programming interface) ● (core concept) — A specification describing how the procedures in a library behave and how they can be called. API documentation is necessary to understand the behaviors a library provides and how to use them.

Random number generation ● (core concept) — RANDOM(a, b) generates and returns a random integer from a to b inclusive, with each result equally likely. Because random values vary, each execution of a program using them may produce a different result.

Simulation ● (core concept) — An abstraction of a complex object or phenomenon built for a specific purpose, using varying sets of values to reflect the changing state of the phenomenon. Simulations are most useful when real-world experiments are impractical, and they help formulate and refine hypotheses about what is being modeled.

Simulation bias ● (core concept) — Skew in a simulation derived from the choices of which real-world elements were included or excluded when the abstraction was built.

Problem vs. problem instance ● (core concept) — A problem is a general description of a task that can (or cannot) be solved algorithmically, such as sorting. An instance of a problem includes specific input, such as sorting the list (2, 3, 1, 7).

Decision problem ● (core concept) — A problem with a yes-or-no answer, such as whether there is a path from A to B.

Optimization problem ● (core concept) — A problem whose goal is to find the best solution among many, such as the shortest path from A to B.

Efficiency ● (core concept) — An estimation of the amount of computational resources an algorithm uses, typically expressed as a function of the size of the input. Efficiency is determined through formal or mathematical reasoning, but it can be informally measured by counting how many times a statement or group of statements executes; different correct algorithms for the same problem can have different efficiencies.

Reasonable vs. unreasonable time ● (core concept) — Algorithms with polynomial efficiency or slower (constant, linear, square, cube, and similar) run in a reasonable amount of time. Algorithms with exponential or factorial efficiencies run in an unreasonable amount of time, and some problems have no efficient algorithm at all.

Heuristic ● (core concept) — An approach to a problem that produces a solution not guaranteed to be optimal, used when methods guaranteed to find an optimal solution are impractical. Heuristics are sought for problems that cannot be solved in a reasonable amount of time.

Decidable problem ● (core concept) — A decision problem for which an algorithm can be written to produce a correct output for all inputs, such as determining whether a number is even.

Undecidable problem ● (core concept) — A problem for which no algorithm can be constructed that always provides a correct yes-or-no answer. Such a problem may still have individual instances with algorithmic solutions, but no algorithm solves every instance.