Solving in a set order

An algorithm is "a set order for solving a problem." Walk the steps and an answer comes out; if the order is wrong, the result is wrong. With the same order, anyone gets the same answer. So write a computer an order, and it always does the same thing.

A big problem won't be solved in one bite. So you break it into small problems of the same shape, set what order to solve them in, and combine the piece answers back together. Handling a big problem this way, by breaking, ordering, and combining, is exactly where computational thinking starts. However hard a problem looks, break it small and it fits in your hand.

Sorting is putting jumbled things into order in a line. Repeat comparing neighbors and sending the bigger one back, and the line falls into order step by step. One settles into place each round, so however jumbled, the line ends up in order. Tidy it up and finding gets easier too.

Sorting by comparing neighbors one by one blows up in comparisons and gets slow as the line grows. The smarter path is to split the line in half, sort each part, then merge the two sorted halves like a zipper. Halving all the way leaves only singles, and a single is already sorted. Merging is fast since you only compare the two fronts. Because you halve, the layers grow slowly, and each layer costs about the line's length, so the whole thing finishes far faster than one by one. This split-and-merge idea is the secret of fast sorting.

Searching is picking out what you want. One by one is slow, but in order you cut in half each time and find it much faster. Cutting in half works only when sorted. So sorting and searching are partners. Line it up once and it stays fast for good.

Speed is measured not in seconds but by the shape of its growth. You look at how much the work grows as the input boxes n get bigger. log n barely grows, n grows with the boxes, n squared explodes. And however messy the formula, you keep just the one term that grows the most. 3n squared + 5n + 9 is simply n squared. This way of seeing only the biggest term is big O. That is why, with big data, cutting in half beats one by one beyond compare.

An algorithm does not only spend time; it spends room (memory) too. Space complexity measures how the extra room an algorithm uses beyond the answer grows with the input size. The very same big-O lens we used for time, we now place over space instead. If the extra room is always one slot, that is O(1); if it grows with the input, that is O(n). And time and space are often traded for each other. Build a table up front and spend more room, and it gets faster; solve it in place and save room, and it gets slower. So when choosing a good algorithm, we look not only at speed but at the cost of room as well.

You conquer a big problem by splitting it in half, solving each, and merging back. The key is that the two pieces don't overlap. Work done on one side never has to be redone on the other. When a piece gets small enough that you can't split it further, you solve it right away, then merge the solved pieces upward into the whole answer. Binary search and merge sort both follow this frame. The pieces not overlapping is what gives this approach its power.

Recursion is solving a problem by calling itself again with a smaller input. In lesson 8 you conquered a big problem by splitting it in half. That splitting is exactly calling itself again. So divide-and-conquer and recursion are one and the same. What it truly needs is a floor to stop. Without a floor, it descends forever. The calls stack up one by one, and once they hit the floor, they unwind back up, combining into one answer. Calling itself, a floor to stop, stacking then unwinding. These three are recursion.

Recursion often re-solves the same small problem over and over. Just look at the Fibonacci tree, fib(2) pops up all over. Write a solved answer on a note and reuse it, and you never solve the same thing twice. That is memoization. Filling a table upward from the smallest values at the bottom is the same idea in reverse. Then what was exponentially slow becomes linear, way faster. Divide and conquer had non-overlapping pieces so there was nothing to write down, but when they overlap, the one move of writing it down changes everything.

A greedy algorithm picks "the best-looking thing right now" at every step. Since it chooses one step at a time without looking at the whole, it's fast and simple. For some problems it's genuinely right, like handing back change biggest-coin-first, or grabbing meetings that end earliest. But when the coin set is odd or the path is tangled, the best in front of you isn't the best overall and becomes a trap. So greedy is fast and often right, but not always right.

Some solutions roll dice and pick what to do at random. In quicksort, always using the last value as the reference gets slow on bad inputs, but choosing the reference at random dodges that trap and is faster on average. You can also scatter points inside a square and look at the fraction landing in a circle to estimate an area. The more you throw, the sharper the estimate. A random solution can't promise the same answer every time, but in return it's fast and simple. You give up a little certainty and gain speed.

A graph is "a picture drawn with dots (things) and lines (relationships)." A dot can be anything, a line is a relationship between two of them. Subways, friend networks, the web are all graphs. A tree is the special case among them with no loop (cycle). So a tree is one kind of graph too. See the world as dots and lines, and what looked tangled comes into view at a glance.

There are two gaits for starting at one dot and touring the whole graph. Breadth-first spreads layer by layer like a ripple, nearest first. Depth-first follows one path to the end, and backtracks when stuck. Both reach every dot without missing one, just in a different order. And when the lines have no distance difference, the order breadth-first touches them is the shortest distance.

When edges have different distances, the route with fewer turns isn't the fastest. So just counting by nearness won't do. From the start, you lock in distances one point at a time, nearest first, and push the boundary of the locked region outward one point at a time. Each moment you pick the nearest point not yet locked, the best in front of you. Once the boundary spreads everywhere, you know the fastest distance to every point.

For some problems, even a small bump in input makes the cases to check explode, so no fast way to solve them is known yet. Think of a salesman finding the shortest route that visits every city once. Yet for many of these, finding the answer is hard but checking someone's answer is easy. So if checking is fast, is solving fast too? That question is called P versus NP, and nobody knows the answer yet. It is a big open mystery.

Even for a hard problem where the perfect answer can't be found fast, a "good enough" one is often quick to find. Some methods go one step further and even guarantee the answer is "within a few percent of the best." It's a trade: give up a little accuracy, gain time. Spend more time and it gets more accurate, less time and less accurate. Where to stop is ours to choose. This is how the whole area closes. We can't solve every problem perfectly, but with fast methods, smart strategies, and knowing the limits, a wise trade puts a usable answer in your hands even in front of a hard problem.