Exam practice

• i.Time O(n): one look at each; memory O(1): one variable for the smallest so far.
• ii.Time O(n²) and memory O(n²): there are n(n − 1) ÷ 2 pairs, and every one is stored.
• iii.Time O(n log n); memory O(n): merging needs a new list as long as the items being merged (plus O(log n) waiting calls on the stack).
• iv.Time O(n): each look-up and add to a set is O(1) on average; memory O(n): the set can hold up to n numbers. It trades memory for time: comparing every pair would need only O(1) memory but O(n²) time.

• i.Twice the classes: 2³ = 8 times the work, 8 × 4 = 32 seconds.
• ii.Ten times the classes: 10³ = 1,000 times the work, 4,000 seconds, about 67 minutes.
• iii.A hundred times the classes: 100³ = a million times the work, 4 million seconds, about 46 days. No: it is fine for one school, but a district needs a better algorithm (or the job split into schools).

The states are the floors it is at. Pressing the button of the floor it is already at changes nothing.

States Ground (start), First, Second. Every button takes the lift to its floor:

The diagram has three circles, an arrow from each to each other labeled with the button of the floor it points to, and a loop on each labeled with its own button. For 2, 2, G, 1: Ground → Second (goes up two floors), Second → Second (already there, stays), Second → Ground, Ground → First. (A real lift also has states for doors open and closed and for moving, and remembers several requests; this machine is the simplest version.)

States: Locked, no wrong tries; Locked, 1 wrong; Locked, 2 wrong; Waiting 30 s; Unlocked. Inputs: right PIN, wrong PIN, 30 seconds pass, press the lock button. A right PIN from any of the first three goes to Unlocked; a wrong PIN moves 0 → 1 → 2 wrong → Waiting; in Waiting, PINs are ignored until “30 seconds pass” returns it to Locked, no wrong tries; the lock button in Unlocked goes back to Locked, no wrong tries.
Two states can’t do it because the phone must remember how many wrong tries in a row there have been, and an FSM can remember only through its state: so each count needs a state of its own. (Checking which PIN was typed is a separate part, done by comparing it with the stored one.)

States: S (start), N (read 9), M (read 98 or 97), E (accepting, a double circle). Arrows: S → N on 9; N → M on 8 and on 7; M → E on any digit. No other arrows: any other character means reject, and E has no arrows out, so a fourth character rejects.
Accepts: 980, 975. Rejects: 99 (no arrow for the second 9 from N) and 9811 (too long: no arrow out of E).

A machine with, say, 10 states can only be in one of 10 situations. Give it the texts with 1, 2, 3, … 11 opening brackets: two of these eleven texts, say with a and b brackets (a < b), must leave it in the same state. From then on it behaves the same for both. Now add a closing brackets to each. The first text balances and must be accepted; the second has b − a brackets still open and must be rejected. The machine does the same with both, so it is wrong about one of them. The same argument works whatever the number of states, so no FSM, and no regular expression, can do it. It needs memory that grows with the depth, such as a stack.

<plate>  ::= <zone> " " <small> " " <class> " " <big><zone>   ::= Ba | Ga | Ko | Lu<class>  ::= Cha | Pa | Kha<small>  ::= <digit> | <digit> <digit><big>    ::= <digit> | <digit> <digit> | <digit> <digit> <digit> | <digit> <digit> <digit> <digit><digit>  ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

(" " stands for one space, a terminal.) Ba 12 Pa 345: Ba is a zone, 12 is two digits (a small), Pa is a class, 345 is three digits (a big): it fits. Ga 2 Cha 12345: the last number has five digits, but <big> allows at most four, so it doesn’t fit. (The old plates’ zones and classes are a short list here; a real checker would list them all. And this grammar uses no rule inside itself, so a regular expression could do the same job.)

RPN: 5 3 + 2 × 4 2 ÷ −. With a stack: 5, 3 → + gives 8; 2 → × gives 16; 4, 2 → ÷ gives 2; − pops 2 and 16 and gives 16 − 2 = 14. Check: (5 + 3) × 2 − 4 ÷ 2 = 16 − 2 = 14.

A tape of squares, endless in both directions, each blank or holding one symbol; a head over one square, which reads it, writes on it and moves one square left or right; a fixed list of states, one the start and some halting; and rules: in this state, reading this symbol, write this symbol, move, and go to this state.
The rules (state, read, write, move, next): swap a b R swap; swap b a R swap; swap _ _ S done. It starts in swap on the first letter and stops in done.

Freezing in an endless loop means not halting, so the program claims to solve the halting problem, which Turing proved undecidable. Given any such checker, one can write a program that asks the checker about itself and does the opposite of what it predicts (loops if told it stops, stops if told it loops), so the checker is wrong about that program; no checker can be right about every app.
An honest version could promise to find many endless loops, to say “this can’t loop” for apps it can prove safe, and to answer “can’t tell” for the rest; or to stop and report an app that runs too long, with a time limit.

P is the set of yes-or-no problems that can be solved in polynomial time (work growing like n, n², n³…); NP is the set whose yes-answers can be checked in polynomial time. The question is whether they are the same: can every answer that is quick to check also be found quickly?
The trek: “is there a round trip through the 20 villages under 90 km?” If someone hands you a route, you can check it with 20 additions and a check that each village appears once: quick, so the problem is in NP. But no method is known that always finds such a route quickly; trying every route takes 19! ÷ 2 tries. The trek’s question is NP-complete, so a fast method for it would give one for every problem in NP, and P would equal NP.
For a phone wallet: the cryptography that protects payments (such as RSA) relies on problems that are quick to check but, as far as anyone knows, slow to solve, such as finding the two prime factors of a huge number. If P = NP with a practical method, those problems would become fast to solve and that protection would fail. (If P ≠ NP, that alone wouldn’t prove factoring hard, but it is what most experts expect.)