Computer science: TestAS practice testlets

An algorithm is a finite sequence of well-defined steps that solves a problem. Sorting is one of the most studied problems in computer science, because sorted data can be searched and processed much more efficiently.

Bubble sort is one of the simplest sorting algorithms. It passes through the list repeatedly, compares neighbouring elements and swaps them if they are in the wrong order. After the first pass, the largest element has "bubbled up" to the end of the list; after the second pass, the second largest is in place, and so on. The algorithm can stop early if a pass makes no swaps, since the list is then sorted. Selection sort works differently: it searches the unsorted part for the smallest element and swaps it to the front, repeating this for each position. Both algorithms need a number of comparisons that grows with the square of the list length, which makes them slow for large lists; algorithms such as merge sort and quicksort are much faster in practice.

Another classic algorithm, described by Euclid more than 2,000 years ago, finds the greatest common divisor (gcd) of two positive integers. It is based on the fact that the gcd of a and b equals the gcd of b and the remainder of a divided by b. The algorithm repeatedly replaces the pair (a, b) by (b, a mod b) until the second number is zero; the first number is then the gcd. For 48 and 18: 48 mod 18 = 12, giving (18, 12); 18 mod 12 = 6, giving (12, 6); 12 mod 6 = 0, giving (6, 0). The gcd is 6. The algorithm is very efficient, because the numbers shrink quickly.

gcd(a, b) = gcd(b, a mod b) gcd(a, 0) = a

To understand or check an algorithm, computer scientists trace it by hand on small examples, record the state after each step and test special cases, such as an empty list, a list with one element or a list that is already sorted. Proving that an algorithm is correct for all inputs requires more: an argument, often using loop invariants, that it always terminates and always produces the right result.

A student traces bubble sort on the list below, passing from left to right in each pass.

Programs make decisions with conditions that are either true or false. Such conditions are Boolean expressions, named after the mathematician George Boole, and they are built from comparisons combined with the operators AND, OR and NOT. The expression (age ≥ 18) AND (hasTicket) is true only if both parts are true; (isMember) OR (paid) is true if at least one part is true; NOT(isBlocked) is true exactly when isBlocked is false.

The behaviour of any Boolean expression can be checked with a truth table, which lists the result for every combination of inputs. With n input variables there are 2ⁿ rows. Two expressions are equivalent if their truth tables are identical. Important equivalences include De Morgan's laws: NOT(A AND B) is equivalent to (NOT A) OR (NOT B), and NOT(A OR B) is equivalent to (NOT A) AND (NOT B). They are often used to simplify conditions or to express the opposite of a condition correctly: the opposite of "the user is logged in and is an administrator" is "the user is not logged in or is not an administrator", not "the user is not logged in and not an administrator".

NOT(A AND B) ≡ (NOT A) OR (NOT B) NOT(A OR B) ≡ (NOT A) AND (NOT B) A OR (A AND B) ≡ A

Many programming languages evaluate Boolean expressions with short-circuit evaluation: in A AND B, if A is false, B is not evaluated at all, since the result must be false; in A OR B, if A is true, B is skipped. Programmers use this to avoid errors, for example writing (x ≠ 0) AND (10 / x > 2), so that the division is never carried out when x is zero.

Boolean logic is also the foundation of digital hardware: the same operators are implemented as logic gates, and every calculation in a processor is ultimately a combination of them.

A library's software decides whether a user may borrow a book. The variables are M (the user is a member), F (the user has unpaid fines), and S (the book is a special reference copy). Borrowing is allowed if the condition M AND (NOT F) AND (NOT S) is true.