Lessons Learned While Learning Algorithms

This is the first post in a series about the lessons I’ve learned while studying computer science algorithms. If programming isn’t an interest of yours, this might not be the most interesting article for you. However, I will add the caveat that it’s really just thinking about data in oblique ways, so if you like reading about how to expand your thinking, this might be your jam. Standard disclaimer, if you have any comments or corrections please DM me @Roneesh

Algorithms are everywhere!

During my time at the greatest programming community on Earth, I’ve decided to spend some time studying computer science algorithms. An algorithm is simply a way to do something in a series of defined steps. If you think about it, you know millions of algorithms already. For instance you know the Ham Sandwich Algorithm(TM) by heart .

HAM SANDWICH
Step 1 - Bread
Step 2 - Ham
Step 3 - Cheese (Optional!)
Step 4 - Bread

You also know several coffee algorithms.

STARBUCKS ALGORITHM          HOME BREW ALGORITHM
Step 1 - Starbucks Step 1 - Grind beans
Step 2 - Drink Step 2 - New filter
Step 3 - Cold water... etc

But the truth is, these are just a few possibilities. Without even realizing it you have subconsciously shut yourself off to the many millions of other algorithms that exist in order to do something. For instance, have you ever tried the Zebra Coffee Algorithm(TM)?

ZEBRA COFFEE ALGORITHM
Step 1 - Befriend zebra
Step 2 - Teach zebra to program computers
Step 3 - Have zebra make billion dollar startup
Step 4 - Have zebra buy you coffee every day forever as thanks

The efficiency of the Zebra Coffee Algorithm(TM) is… questionable. But it is, I suppose, in the realm of possibility therefore it is a potential way to solve the problem of getting you coffee.

But outside of whether the Zebra Coffee Algorithm(TM) is technically possible, there is in my opinion, a more intriguing question to ask about it: Is it intuitive?

Is it intuitive? Meaning on your own, with no help or guidance whatsoever (no StackOverflow, no blogs, no friends, etc) would you have naturally stumbled on to the Zebra Coffee Algorithm(TM) as a solution for getting a cup of coffee?

No, you would not have.

Which leads us to Lesson 1 in learning algorithms:

Lesson 1 — The CS algorithms we study are almost always unintuitive ways of solving problems.

And if they are at times unintuitive, we can from that naturally derive lesson 2 of algorithms:

Lesson 2 — Don’t feel bad if you don’t understand an algorithm, they are almost always inherently unintuitive, and thus, confusing.

But there is a bright side to this! If we take time to deeply understand unintuitive ideas, we are by default expanding our thinking, and expanding our thinking makes us smarter, so we get Corollary 1:

Corollary 1 — Learning new algorithms makes you smarter.

And since as a general rule, becoming smarter can increase your capabilities for empathy and understanding, I will be so bold as to make Completely Unsubstantiated, Perhaps Wrong, Claim 1:

Completely Unsubstantiated, Perhaps Wrong, Claim 1 — Learning new algorithms makes you a better person.

How we’ll study algorithms — a humble array

Let’s give ourselves an array of data, this array can be in any language, but for simplicity we’ll use JavaScript. We’ll call this array “arr” and it will have the numbers 1 through 8 in it, unsorted.

var arr = [2, 3, 5, 1, 4, 7, 6, 8];

This is the most common setup for studying an algorithm, we use a simple, small set of data like this 8 number array and we intend to use an algorithm to study or alter it some way. In my opinion, defining what you’ll do is where you begin with algorithms.

Figure out what your algorithm should be doing

Lesson 3— Figure out what your algorithm should be doing.

While technically the possibilities are limitless, in CS we most often are just trying to do a few things to our data via an algorithm:

  1. Sort or re-arrange the data in some way
  2. Alter the elements of the data in some way
  3. Obtain some knowledge about the data

Sorting algorithms are some of the most common algorithms you learn first, because sorted data is very useful to humans. Altering the data is also very common too, sometimes you want to do some mutation to it so it’s more useful to you.

Obtaining some knowledge about the data is much more open-ended, and thus less intuitive to do. But it is in fact the most algorithm-y thing we do with data.

To make this third one make sense, let’s introduce a common interview problem that you need to make an algorithm to solve, the home robber problem:

Source: Recurse Center

In this problem, you’re not trying to transform each element in the array, nor are you trying to sort or rearrange the data in anyway. In fact, if you did do a sort or rearranging, my first instinct is that such a thing would be worse for solving the problem. So in this case, all we want to do is study the data and see if we can answer our question about it: what is the maximum amount of money we can get given our constraints?

Explore the many versions of the problem

Lesson 4 — Explore the many versions of the problem

The reason the robber problem is tricky is because the data can be kind of quirky to deal with. A simple happy case would be like so:

var houses = [100, 0, 100]; 
// max value is 200 from first and last home

If we just saw this example, we might get tricked into thinking this a trivially simple algorithm, simply add up every other element in the array.

But we also need to handle cases like below, where our answer ends up just being a single number:

var houses = [100, 200, 99]; 
// max value is 200 from first home only

And we could get data like this next one, which probably isn’t what you’d expect:

var houses = [0, 200, 200, 0, null, undefined, 0, 5]; 
//max value is 205 from second and last home, null and undefined
//shouldn't really throw us for a loop

So when I say explore the problem, I really mean explore all the inputs you might have to solve for. And if you just solve for the simplest input, our first example of the houses variable, then you might be duped into implementing an incorrect solution.

Remember, your tools are limitless

Lesson 5 — Remember, your tools are limitless

Probably if you tackle this problem, you’ll write a function in JavaScript and my guess is you’d give yourself just two tools to solve this problem:

/* name: solveRobberProblem
inputs: a an array of houses called housesArray
outputs: a integer of the maximum value you can get without
triggering an alarm.
function solveRobberProblem(housesArray) {
var maxValue = 0;
  /* Some operations on the housesArray where you will occasionally
increment maxValue */
  return maxValue;
}

The two tools here are the housesArray and the maxValue. You’ll probably try and get a solution that just uses these two variables. I’ve noticed this tends to be people’s natural instincts when tackling problems, to try and do it with only the given inputs and the desired outputs.

(I think at this point, it might be a good idea to spend a few minutes trying to solve this problem if you have never tackled it before.)

But remember, you have limitless tools at your disposal!

What if I told you that the answer involved using a new array called runningTotal, that kept adding values to the array, and your max value was the last value of the array. Probably, the sentence above doesn’t make much sense, partially because I’m a bad writer, but also because it’s not intuitive.

Let’s see what I’m talking about below:

var houses = [100, 0, 100];
function solveRobberProblem(housesArray) {
var maxValue,
runningTotal;
  /* to start with, make runningTotal equal to the first two houses
values*/
  runningTotal = [ housesArray[0], housesArray[1] ];
// so runningTotal = [100, 0]
  /* start at index 2 (the third house) in housesArray */
for (var i = 2; i < housesArray.length; i++) {

if (housesArray[i] + runningTotal[i-2] > housesArray[i - 1]) {
runningTotal[i] = housesArray[i] + housesArray[i -2];
} else {
runningTotal[i] = runningTotal[i - 1];
}
}
/* Get the last value of runningTotal and set that to maxValue */
maxValue = runningTotal[runningTotal.length - 1];
return maxValue;
}

so if we feed the code above our simplest example of `var housesArray = [100, 0, 100];`, we should get the code to do the following:

1. set runningTotal = [100, 0], the first two houses
2. iterate over the rest of housesArray, starting at index 2
3. For each item in housesArray, check if the value at index i, plus the runningTotal two spaces back is greater than the value of runningTotal one space back.
4. Put the larger of the two in runningTotal[i];

More verbosely we’re doing something like this:

var housesArray = [100, 0, 100]
so runningTotal = [100, 0]
and now we have to figure out what we'll do at house 3...
[100, 0, omgWhatWillThisValueBe???]
hmm ok, it could be the value of house 3 plus house 1 (since they are not next to each other, they can be added without triggering the alarm):
[100, 0, (housesArray[i] + runningTotal[i-2]] 
[100, 0, (housesArray[2] + runningTotal[0])]
[100, 0, (100 + 100)]
[100, 0, 200]
hmm, but it could also be just the value at house 2, let's see what that one is:
[100, 0, (runningTotal[i-1])]
[100, 0, (0)]
ok, 200 > 0 so it'll be our first scenario, not the second one.
Aaaand since no there's no more values in housesArray to check, so let's return the last value of housesArray, 200 as our answer.

Before we go further, let me disclaim that there is some code I omitted about a case where you have 0 or 1 houses in housesArray. I’m just leaving it out for simplicity sake.

What if our housesArray was [100, 500, 100]?

var housesArray = [100, 500, 100]
1. runningTotal = [100, 500]
then our runningTotal's third item is...
[100, 0, omgWhatWillThisValueBe???]
hmm ok, it could be...
[100, 0, (housesArray[i] + runningTotal[i-2]]
[100, 0, (housesArray[2] + runningTotal[0])]
[100, 0, (100 + 100)]
[100, 0, 200]
hmm, but it could also be...
[100, 0, (runningTotal[i-1])]
[100, 0, 500]
ok, 500 > 200 (by a lot!) so it'll be the latter and not the former.
Aaaand since no there's no more values in housesArray to check, so let's return the last value of housesArray, 500 as our answer.

It looks like this code works for most of our cases (in fact, it works for all our cases!). But using this runningTotal array was probably not your first technique to solve this, it sure as heck was not mine.

In my opinion, using this runningTotal concept is pretty lateral thinking. Once you know the technique, it makes a lot of sense, but until you realize it’s a possibility you just get stuck in a rut of trying to do this with simple integer variables and the given array.


So to close out the first article in this series, let’s recap our lessons so far:

Lesson 1 — The CS algorithms we study are almost always unintuitive ways of solving problems.*

Lesson 2 — Don’t feel bad if you don’t understand an algorithm, they are almost always inherently unintuitive, and thus, confusing.

Lesson 3 — Figure out what your algorithm should be doing.

Lesson 4 — Explore the many versions of the problem

Lesson 5 — Remember, your tools are limitless

I think combined, these lessons form a great base for approaching algorithms. What they really lay out is the mindset you should have when problem solving. They say that recognize these problems are hard, that you shouldn’t feel bad for taking time to understand them. They say that algorithms do many varied things, and since they do many varied things, there can’t be a single method for designing them. Finally, they implore you to be creative, in both thinking of what inputs you might have, and in what tools you give yourself in designing a solution.

That’s it for this first article, in later ones, I’ll demonstrate some concrete techniques that I’ve used across numerous algorithms.


*A quick note! A few people who read drafts of this said that they disagreed with lesson 1, that algorithms are inherently unintuitive. Perhaps it’s more precise to say two things: that mostly for newcomers they are unintuitive and that compared to people’s first instinct to brute force solve a problem, these more elegant answers are unintuitive. Once you’ve spent enough time with an algorithm, it will become intuitive, but it takes time. Also, as I said above, if you are coming in with no guidance at all, I do think it’s fair to say they are unintuitive.

*Thanks to Alena Kuczynski for finding and helping me correct a bug in my algorithm!


Thanks for reading! If you like what I’ve written please ❤ it and share, it means a lot to me as a writer!