The big ideas of computer science

A switch is either off or on, so the simplest thing an electronic circuit can store is a single bit: 0 or 1. String eight bits together and you have a byte, with 2 × 2 × … × 2 = 256 possible patterns. Every file on your computer is a long sequence of bytes.

The bits themselves carry no meaning. The pattern 01000001 is the number 65, the letter "A" in the ASCII text code, or a dark grey pixel, depending on which program reads it. The same goes for negative numbers. Most computers use two's complement, in which 11111111 means −1, so the same byte can be 255 or −1.

In 1936 Alan Turing described an imaginary machine with a long tape of symbols, a head that reads and writes one cell at a time, and a small table of rules: "in state A, reading 0, write 1, move right, switch to state B." He showed that one such machine, the universal machine, can read the rule table of any other machine from its tape and imitate it. That's the idea behind the stored-program computer, in which programs are just more data.

Turing also proved a limit. Suppose some program H could look at any program and its input and say whether it eventually halts. Build a program D that asks H about itself and does the opposite: if H says "D halts", D loops forever, and otherwise it halts. Whatever H answers about D is wrong, so H can't exist.

In 1948 Claude Shannon defined the information in a message as how surprising it is. A symbol that occurs with probability p carries log₂(1/p) bits. Averaged over the symbols, this gives the entropy, the minimum number of bits per symbol any lossless code needs on average.

Text stored as ASCII uses 8 bits for every character, but "e" is far more common than "z." Huffman coding gives common symbols short codes and rare ones long codes, and gets within one bit per symbol of the entropy. Real compressors such as ZIP's DEFLATE also replace repeated phrases with short back-references, which is why text and code shrink so well.

To find a name in an unsorted list, you may have to check every entry: for n entries that's up to n steps. If the list is sorted, open it in the middle. If the name comes earlier, throw away the second half, and repeat. Each step halves what's left, so it takes at most about log₂ n steps. This is binary search.

Computer scientists describe growth with big-O notation. Linear search is O(n), binary search is O(log n), and comparing every pair of items is O(n²). Constant factors (a faster chip, a cleverer loop) change the time by a fixed ratio. A better growth rate changes it by a ratio that keeps widening as the input grows.

Insertion sort is how most people sort a hand of cards: take each new item and slide it left past everything bigger. It's simple, but on a shuffled list each item slides past about half of the ones before it, so it makes about n²/4 comparisons.

Merge sort splits the list in half, sorts each half the same way, then merges the two sorted halves by repeatedly taking the smaller front item. Merging is quick, and there are only log₂ n levels of halving, so the total is about n log₂ n comparisons. For a million items, that's 20 million instead of 250 billion.

A graph is a set of nodes and the edges between them. Many problems become graph problems: what's the fastest route home, how does a packet cross the internet, how many handshakes separate you from a stranger.

Breadth-first search explores outward from the start in rings: first everything one step away, then two steps, and so on. The first time it reaches the goal, it has found a shortest path. Dijkstra's algorithm does the same when edges have different lengths. A* adds an estimate of the remaining distance, such as the straight-line distance, so it explores towards the goal first. As long as the estimate never overstates the real distance, A* still finds a shortest path.

A salesperson must visit n cities and return home by the shortest route. With 10 cities there are 181,440 distinct round trips. With 25 there are about 3 × 10²³, and at a billion trips per second checking them all would take about ten million years. Given a route and a target length, though, you can check it in moments.

P is the class of problems that can be solved in time growing like a polynomial in the input size. NP is the class where a proposed solution can be checked in polynomial time. The travelling salesman problem, scheduling, Sudoku on large boards and thousands of others are NP-complete: a fast algorithm for any one of them would give fast algorithms for all of NP. Nobody has found one, and nobody has proved one can't exist.

Reading from a processor's first-level cache takes about a nanosecond. Main memory takes about 100 nanoseconds, a solid-state drive tens of thousands, and a network round trip across a continent tens of millions. Each level is bigger, cheaper and slower than the one above.

A cache keeps copies of recently used data in the faster level. It works because of locality: programs tend to reuse data they used recently and data stored nearby. When the cache is full, a common rule is to evict the least recently used (LRU) item. Web browsers, content delivery networks and databases all rely on caches.

Requests to a web server, jobs at a printer and cars at a toll booth arrive at random. Even if the server can handle the average load, arrivals bunch up, and a queue forms. The fraction of time the server is busy is its utilization.

For random arrivals and random service times, the average time a request spends in the system is the service time divided by (1 − utilization). At 50% utilization that's 2× the service time, at 90% it's 10×, and at 99% it's 100×. This is why well-run systems keep spare capacity, and why a small traffic increase can make a busy site suddenly unusable.

Every channel corrupts some bits: radio static, scratches on a disc, cosmic rays hitting memory. The crudest fix is to send every bit three times and take a majority vote. That fixes any single error in each group, but it triples the length of the message.

Richard Hamming found something better. His (7,4) code adds three parity bits to every four data bits, each checking a different overlapping subset. If one bit flips, the pattern of failed checks spells out its position in binary, so the receiver can flip it back. That corrects any single error with 75% overhead instead of 200%. Modern codes, used in phones, Wi-Fi, QR codes and spacecraft, get close to the theoretical limit Shannon proved in 1948.

For most of history, two people who wanted to communicate secretly first had to meet and agree on a key. Public-key cryptography removes that step. You publish a public key anyone can use to encrypt a message to you, and keep a private key that alone can decrypt it.

In RSA, the public key includes a number n = p × q, the product of two large secret primes. Multiplying them is easy. Recovering them from n is, as far as anyone knows, infeasible when each has hundreds of digits. Encryption raises the message to a power and keeps the remainder after dividing by n. Decryption needs a different power that can only be computed from p and q.

Nobody can write down rules for recognizing a cat in a photo, but it's easy to collect photos labelled "cat" and "not cat." Machine learning builds a program from such examples. The simplest method is nearest neighbours: to label a new point, find the k closest training examples and take a vote.

With k = 1 the method memorizes the training data perfectly, including its mistakes and noise. It scores 100% on the examples it has seen but worse on new ones. This is overfitting. Larger k averages over more neighbours and gives smoother boundaries, but too large and it misses real detail. Every learning method, up to today's neural networks, has to balance fitting the data against generalizing beyond it, and is judged on held-out test data.