Algorithms and Programming

A variable is a named place that holds a value, like a number, a Boolean, a string or a list. Assignment (a ← expression) works out the expression and stores the result in the variable, replacing whatever was there, so a variable always holds the last value assigned to it.

A list holds many values in order, and each value (an element) has a position number called its index; on the exam, indexes start at 1, so aList[1] is the first element. Using one list instead of many separate variables is data abstraction: you can work with the whole collection by name, which makes a program simpler to write and change.

An algorithm is a finite list of steps that does a job, and sequencing means running those steps in the order they're written. Expressions use +, -, *, / and MOD with the usual order of operations (MOD ranks with * and /). On the exam / is ordinary division, so 7 / 2 is 3.5, and a MOD b is what's left over after dividing a by b, so 20 MOD 6 is 2.

A string is text: a sequence of characters in a set order, like "hello" or "A7!". Concatenation sticks strings together into a new, longer string ("sun" and "flower" give "sunflower"), and a substring is a piece of a string, like "flow" inside "sunflower". On the exam, any string procedure you need is explained in the question.

A Boolean value can only be true or false. Relational operators (=, ≠, >, <, ≥, ≤) compare two values, and the logical operators combine conditions: NOT flips a value, a AND b is true only when both are true, and a OR b is true when at least one is true.

Selection lets an algorithm choose which steps to run based on whether a condition is true. An IF (condition) block runs only when the condition is true, and IF ... ELSE runs exactly one of its two blocks.

A nested conditional is a conditional inside another conditional, so the inner check only happens when the outer condition sends the program that way. Tracing one branch at a time, with a specific input, is how you work out which output you'll get.

Iteration repeats part of an algorithm. REPEAT n TIMES runs its block exactly n times, while REPEAT UNTIL (condition) checks the condition before each pass and stops once it's true, so the body never runs if the condition starts out true, and the loop never ends if the condition can never become true.

Different algorithms can solve the same problem, and algorithms that look different can still give the same result. You can build new algorithms from ones you already know work, like finding a maximum or minimum, adding up a sum or average, or checking whether a number divides evenly using MOD.

The exam's list procedures are INSERT, APPEND, REMOVE and LENGTH, and an index below 1 or above LENGTH(aList) stops the program with an error. Traversing a list means visiting its elements one at a time (often with FOR EACH item IN aList), and a linear search checks each element in order until it finds the value or runs out of elements.

Binary search looks for a value in a sorted list by checking the middle element and throwing away the half that can't contain it, repeating until it finds the value or nothing is left. It only works on sorted data, but on large lists it's usually far faster than a linear search.

A procedure is a chunk of code with a name. It can take inputs called parameters and can send back a value with RETURN, and you call it by name with arguments (the actual values for the parameters), like total ← addUp(3, 5). A call pauses the normal order of the program, runs the procedure's steps, and then picks up right after the call, using any value that was returned.

Writing your own procedures is procedural abstraction: you can call a procedure as long as you know what it does, even if you never look at the code inside it, and one procedure with parameters can replace many repeated chunks of code. Breaking a big problem into smaller procedures (modularity) makes a program easier to read, test, fix and reuse.

A software library is a collection of procedures someone else has already written that you can use in your own programs. Its API (application program interface) spells out what each procedure does and how to call it, and reading the documentation is how you learn to use it. Libraries make complex programs much quicker to build.

RANDOM(a, b) returns a random whole number from a to b, including both a and b, and each value is equally likely. Because each run of the program can give a different result, you reason about every possible outcome rather than a single one.

A simulation is a program that models a real-world system or event, often using random values to copy real-world variety, so you can test ideas that would be too slow, costly or dangerous to try for real. Simulations leave out details on purpose, which makes them simpler but means their choices about what to include can add bias.

Efficiency is how much time or memory an algorithm needs as its input grows. Algorithms whose number of steps grows no faster than a polynomial (like n, n² or n³) run in a reasonable amount of time, while ones that grow exponentially or faster (like 2ⁿ or n!) take an unreasonable amount of time. When finding the best answer would take too long, a heuristic finds an answer that's good enough.

A decision problem has a yes-or-no answer, and it's decidable if some algorithm gives the right answer for every possible input (like "Is this list sorted?"). An undecidable problem is one where no algorithm can always give the right answer, though some individual cases may still be solvable.