This week we learned two new algorithm design techniques: dynamic programming and greedy algorithms. Dynamic programming is a way to avoid solving the same subproblems repeatedly by saving their answers for later use, and the greedy technique solves optimization problems by making the locally optimal choice at each step without ever going back.
Dynamic programming
Dynamic programming is useful when a recursive solution keeps solving the same smaller problems over and over. Instead of recomputing them, you solve each subproblem once, store the answer in a table, and build up to the final answer from the smallest cases.
Fibonacci numbers are the classic example, where computing one value recursively ends up recomputing the earlier values many times.
The coin-row problem is another example. You have a row of coins and want to collect the most money, but you can’t take two coins that are next to each other. At each coin you have two choices: take it and give up its neighbor, or skip it. Instead of trying every combination, you walk down the row once, and keep track of the best total you can get.
The coin-collecting problem is the same idea on a grid, where a robot can only move right or down and wants to pick up as many coins as possible. The best total at any square is the better of the totals from the square above and the square to the left, plus any coin on that square.
Warshall’s and Floyd’s algorithms
Warshall’s algorithm answers the question “can I get from here to there?” for every pair of vertices in a directed graph. The book mentions spreadsheets as an example: when you change one cell, the software needs to know every other cell that depends on it, even indirectly. The algorithm starts by only allowing direct edges, then lets paths pass through the first vertex, then the first two, and so on. Each round, a new path opens up whenever you can get to the new vertex and then from it to somewhere else.
Floyd’s algorithm uses the same structure to find the shortest distance between every pair of vertices. Each round it asks whether going through the new vertex is a shortcut compared to the best route found so far.
The two algorithms are basically the same idea applied to different questions, and they both use dynamic programming. Instead of breaking the graph into smaller pieces, they solve a simpler version of the same problem first, with fewer vertices allowed as stops along the way. Each round builds on the answers saved from the round before, so no path ever has to be worked out from scratch.
The greedy technique
A greedy algorithm builds a solution one step at a time, always making the choice that looks best right now, and never going back to change it. Making change is an everyday example: to give someone 48 cents, you hand over a quarter, then dimes, then pennies. The greedy approach doesn’t always provide the optimal solution, however. If you only had quarters, dimes, and pennies and wanted to make 30 cents with the fewest coins, the greedy approach would give a quarter and five pennies, but three dimes would be optimal. Greedy algorithms are easy to come up with, but it’s hard to prove that they actually give the best answer.
Prim’s algorithm is one where the greedy approach does work. It finds a minimum spanning tree, the cheapest set of edges that connects every vertex in a weighted graph, like the cheapest way to wire a set of buildings into one network. You start at any vertex and keep adding the cheapest edge that reaches a vertex you haven’t connected yet until everything is connected. Surprisingly, this always gives the cheapest possible tree.