Can algorithms teach us anything about life? Is it more than just a computer science course that tells use to find n*log(n) algorithms for divide and conquer and create tables for dynamic programming? Let’s examine some popular programming techniques: divide and conquer, dynamic programming, greedy algorithms, linear programming, and streaming algorithms, NP-complete/reductions.
Divide and conquer. Divide and conquer is all about breaking into smaller subproblems that have a similar structure. Break things into smaller subproblems until they become easy to solve. There is something to be said about when you’re given a complex problem, break it into half. Solve the easier problems, then put them together.
The way Berkeley describes dynamic programming is that it is a “failed” attempt at divide and conquer, but you notice some subproblems are repeated. I think it teaches you that you shouldn’t learn things twice. Don’t relearn the lessons life teaches you, remember it the first time. Just like how you build from the bottom of the table that you store your results and build upon the past results, try not to repeat unnecessary work that you’ve already done. Keep notes on past processes. Automate things you know you will do a lot. There is no use in learning something if you’re just going to forget (well, that’s not entirely true…but you get the point). This is different from divide and conquer because divide and conquer teaches you how to break up problems, while dynamic programming teaches you to not repeat problems.
Greedy algorithms are an interesting different section. Maybe it’s better to be called greedy strategies. Greedy strategies just mean you see the data, and you make a decision, and you stick with it. You never backtrack. Once you make a decision, it’s final. In a sense, all algorithms are “greedy” as they end up choosing decisions based on the data, but greedy algorithms are really focused a lightweight simple system of choosing the next step to take. For example, Dwight’s greedy strategy for loyalty was “ Look, I’m all about loyalty. In fact, I feel like part of what I’m being paid for here is my loyalty. But if there were somewhere else that valued loyalty more highly, I’m going to wherever they value loyalty the most.” Dwight just chose the company which gives him the best offer (which is not actually true, since he stays with Dunder Mifflin forever, but it’s what he says). And the interesting thing about greedy strategies is they often don’t yield the optimal result (like divide and conquer and dynamic programming). Which makes sense, because you only have the data now. If you always change companies to whatever offers you the highest salary, you’re missing out on a lot of other factors and experiences that you would get at being at a company longer. But there are guarantees you can put on these strategies. Greedy strategies can often be lower bounded so you know that there is a worst case, and sometimes it can be proven to be optimal. And I think the most important part to remember is that greedy strategies is a strategy: it’s how to approach problems/life. There are different strategies as well, but like all strategies, it has it’s pros and cons. Pros: It’s lightweight and makes it easy to choose decisions. It simplifies your life. Cons: Sometimes, greedy is not always optimal. But it’s usually pretty good.
Linear programming. Oh, how does this apply to anything? Well, linear programming is the art of phrasing problems as maximizations with constraints that are linear. And although it seems like this is a big limitation having only linear constraints, you’d be surprised how many models it can fit. And once you can phrase it as a linear program, you just assume there’s a solver and it solves it for you. Sometimes in life, things seem very difficult. But if you can phrase and reduce the difficult problems to things that you know how to do, it becomes easy. So the challenge in life is not always doing the hard thing, but the challenge is in redefining and phrasing the problem. If you ever find something difficult, try changing your focus from solving it to defining it in terms you do know (or know something that could solve it).
I’ve already talked about streaming algorithms in my Boyer-Moore algorithm post. But let’s see it again. Sometimes you don’t need to thoroughly analyze a problem deeply to solve it. Maybe you only need one look through it to solve like streaming algorithms. Some things are simple, but complex if you look too hard.
And then we come to NP-complete problems and reductions. And the fact of the matter is, some problems in life are too hard to solve, only have unrealistic exponential runtimes, or there is a solution but no one knows if there is one. So what do you do if you encounter an impossible problem? You prove it is extremely difficult by reducing it to a known impossible problem. Which seems like a pretty valid excuse to not being able to do something. And that’s fine. Some problems are too difficult. And it’s up to you whether you want to work on these problems or something else.