Algorithm design strategies and limits
Many problems can be solved by a few general strategies. Some problems, though, have no known fast solution, and some cannot be solved by any algorithm at all.
Brute force
Brute force tries every possibility: every password, every route, every arrangement. It is simple and always finds the answer if one exists, but the number of possibilities often grows exponentially. Checking all orderings of 20 cities means about 2.4 x 10^18 routes.
Greedy algorithms
A greedy algorithm makes the best-looking local choice at each step, hoping for a good overall result. Giving change using the largest coin first is greedy and works for standard coin systems. Greedy methods are fast but do not always give the best answer: with coins of 1, 3, and 4, greedy makes 6 as 4 + 1 + 1 (three coins) instead of 3 + 3 (two).
Divide and conquer and recursion
Divide and conquer splits a problem into smaller instances of the same problem, solves them, often recursively, and combines the results, as in merge sort and binary search. A recursive solution needs a base case that stops the recursion, or it will call itself forever.
Dynamic programming
Dynamic programming solves problems by breaking them into overlapping subproblems and storing each subproblem's answer so it is computed only once. Computing Fibonacci numbers naively by recursion takes exponential time; storing earlier results makes it linear. Dynamic programming solves the coin-change problem correctly for any coin system.
Graph algorithms
Many problems are graphs: places joined by roads, people joined by friendships, pages joined by links. Breadth-first search explores outward level by level and finds shortest paths in unweighted graphs. Dijkstra's algorithm, published by Edsger Dijkstra in 1959, finds shortest paths when edges have non-negative weights, such as distances, and underlies route planning.
P, NP, and hard problems
P is the class of problems solvable in polynomial time, such as O(n^2) or O(n^3). NP is the class whose proposed solutions can be checked in polynomial time. Many important problems, such as the travelling salesperson decision problem, are NP-complete: no fast algorithm is known, and finding one for any of them would give one for all. Whether P equals NP is a famous open question, with a million-dollar Clay prize.
Undecidable problems
Some problems cannot be solved by any algorithm at all. Alan Turing proved in 1936 that the halting problem, deciding for every program and input whether the program eventually stops, is undecidable. This means no tool can perfectly detect all infinite loops, a fundamental limit on computation.
Worked example
Fibonacci with dynamic programming: F(0) = 0, F(1) = 1, and each next value is the sum of the previous two. Computing F(10) bottom-up: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. That takes 9 additions. Naive recursion recomputes the same values repeatedly, making 177 calls for F(10) and growing exponentially as n increases.
Key takeaways
Brute force tries everything and often explodes exponentially. Greedy algorithms pick the best local choice: fast, but not always optimal. Divide and conquer splits problems and needs a base case when recursive. Dynamic programming stores subproblem answers, turning exponential work into polynomial. Graph algorithms such as breadth-first search and Dijkstra's find shortest paths. P versus NP is a major open question; NP-complete problems have no known fast algorithms. The halting problem is undecidable.
Flashcard
Try every possibility
Check your understanding
With coins of 1, 3, and 4, a greedy algorithm makes 6 as 4 + 1 + 1. What does this show?