How to design an algorithm

If you missed my previous article, I’m going to spend a series of articles providing notes as I audit Steven Skiena’s CSE 373 Analysis of Algorithms class.

In the first lecture, Skiena mentions you should take a data structures course and a linear algebra course before studying this material.

For professional (read: practical) purposes, we’re obviously not starting from scratch, but peaking at the syllabus I do believe we can incorporate data structures by implementing them in JavaScript (this is, after all, a front-end blog) along the way.

And as much as foundational linear algebra will help, there simply won’t be anything in a technical interview that would warrant deep study anyway, so we can safely skip this prerequisite.

What is an algorithm?

An algorithm is an instruction set. Kind of like a recipe for a food dish. And just like that recipe for cauliflower rice you found on some random blog, you can translate that recipe into any language you want.

Algorithms are the same way: they are language-agnostic and can be expressed in a human-readable form or machine-readable. The simpler the idea, the easier it’s going to be to express in English. The more complex or nuanced the algorithm is, the more likely you’ll want to lean on a machine language like Python or JavaScript.

For practical purposes, think of the high-level overview of your algorithm as something you’ll explain to an interviewer in English before you dive into the code, but understand that in order to prove your chops as a programmer the code will have to be the primary source for explaining and validating the algorithms you design.

The two defining characteristics of an algorithm that separate an algorithm from other instructions are:

1. It’s correct. Has anyone ever received credit for implementing an algorithm in a tech interview that didn’t produce the correct result every single time?
2. It’s efficient. We’d like our algorithms to run sometime before we get old.

Now, technically, programs don’t have to run correctly to be acceptable. Programs that run instructions that are mostly correct are known as heuristics. These will become important when studying approximation algorithms later, but for now, assume that correctness is a requirement.

How do you prove an algorithm is correct?

Proofs were not my strong suit in high school or college. For some reason, it never really clicked for me because the steps in a proof never seemed to line up with the logic my brain used to jump from one step to the next.

Luckily, the easiest way to prove correctness is to prove something isn’t correct.

Wait, what? How does proving the opposite help us here?

Well, when we’re trying to figure out a correct and efficient algorithm to solve a problem, we can narrow the scope of possible choices by eliminating the ones that are demonstratively incorrect. Proving by counterexample can be far easier than other methods.

As a trivial example, suppose we have a total T = 6 we want to strive for by adding up numbers in a valid set like S = [1,2,3]. It might seem like a very simple algorithm that will solve this problem is to pick numbers from left to right until we reach the total T. Even if you add in a big number at the beginning like S = [5,1,2,3] this works since we can just scrap the last two numbers.

What’s a counterexample that wouldn’t work?

How about S = [5,2,4].

First, we pick 5, which is less than 6. There are no other numbers in our set that could add up to equal 6 after already picking 5, but there is a valid configuration that would still satisfy T (2 and 4). That’s proof by counterexample that our algorithm was not correct. It’s also a pretty simple counterexample. Counter-examples can be useful in the real-world to quickly help you assess if the path you’re going down is a good one or not.

If you can come up with a relatively simple counterexample (simple meaning it should only require a handful of variables or items) you know that your algorithm is dead on arrival and you’ll need to try something else. If you can’t, you’re probably on the right track, but that doesn’t mean your algorithm is definitively correct.

What techniques are used to prove correctness?

One way to prove correctness is induction. Proof by induction indicates that if we can solve for a base case and the general case for n+1, we know we’ve provided a correct answer for all possible inputs.

There are two important connections to make here about induction which are useful in a professional setting:

1. Proof by induction is a mathematical form of recursion. Recursion is a fundamental concept in programming which allows a function to call itself. It allows us to split up large problems into smaller ones.

The classic example here is the Fibonacci sequence (a sequence of integers where the current number is the sum of the previous two numbers). To calculate Fibonacci for a value n in the sequence, you could count up all of the previous numbers manually for each input of n, but that would not only be slow and laborious, it would also be difficult to express as a program.

Another way would be to count a few base cases (n = 0 and n = 1) to get the counting started, and then continuously call a Fibonacci function with the summed values from the previous step. Recursion is what allows us to accomplish this in code. It is the programming strategy for tackling induction, which is the mathematical strategy for proving statements for algorithms which operate on our sets of data.

1. Proof by induction is useful for summation. If you’re adding up a lot of inputs together, and you need to prove it will work for all cases, even ones larger than the set you have defined, it can be proven with induction.

But are you ever going to need to formally prove something at work or in an interview? Absolutely not. But you will need to test your code, and tests are a form of proof.

So while a formal mathematical proof of induction is likely way more rigorous than you will ever need to showcase in a professional setting, it does set the tone that you can’t simply write code and have people assume what you wrote is correct. It needs to be tested somehow, so if you have the mindset that your algorithm needs to be proven correct in some form, you’re on the right track to writing quality code.

And how do you prove something is efficient?

If we’ll primarily be using code to express our algorithms, and tests to prove their correctness, Big O notation will be used to prove our algorithms are efficient.

We’ll cover Big O in a later post in this series, but the important thing to remember now is that in general, you’re going to want to strive for things that take a reasonable amount of time on large data.

For example, if something you design takes an n! factorial amount of time, anything over a measly 30 items and you’re dealing with numbers larger than the number of stars in the known universe. You probably want something that runs a bit faster than that.

The big picture on the properties of algorithms

Most CS courses (and most schools) only ever care about these two things. If your teachers and TAs can successfully run your program within a reasonable amount of time, you get an A. Real life doesn’t give you an A for these two things because you don’t work in a vacuum as you do on a problem set or exam. So what things are missing from the real world picture?

• Orthogonality: Is your code dependent on other stuff? Are you writing stateful or functional code? Since most coding whiteboard problems are isolated and self-contained, you usually can’t test for this, so make sure you present a portfolio of real-world projects and open source code to demonstrate this
• Readability: You can write the hackiest crap to get an algorithm to work, but in the real world other people can’t read or use that code, and that’s a fail. Make sure if you have time and your code is correct and efficient, to refactor to demonstrate you can write readable, reusable code that is DRY (don’t repeat yourself) and orthogonal (or at least that it can be written as part of an orthogonal system)

The first step in designing an algorithm

So now that we know what defines an algorithm and what is required to prove it’s worth using to solve our problems, the next step is to decide how we will design our algorithms. Modeling a problem means knowing the objects you’re dealing with, and there are two classes of objects we will cover:

Combinatorial objects

A combinatorial object is just a fancy way of saying “what kinds of things can I use to count with?” Since machines are just big 0 and 1 factories, combinatorial objects are the way for us to collect and organize all of the 0 and 1 math our machines are performing thousands upon millions of instructions per second. What kinds of things are we talking about?

• Permutations: reorderings of a set. Colloquial terms for this include words like arrangement, tour, ordering, and/or sequence.
• String: sequence of characters or patterns. Think of strings like permutations but with letters instead of numbers. Words like text, character, pattern, label, sentence are key insights that you’re dealing with string data.
• Subsets: portions of a set. If you see words like cluster, collection, committee, group, packaging, or selection, you’ve probably got a subset.
• Points: locations in space. Words like node, site, position, record, or location are all references to points.
• Graphs: nodes with vertices to connect them and give them direction. We mentioned this much earlier in this article. Words like network, circuit, web, and relationship all describe graphs.
• Trees: graphs that flow in one direction and don’t end up where they started (acyclic). When they’re perfectly balanced, they literally look like a Christmas tree. Words like hierarchy, dominance relationship, ancestor/descendent relationship, taxonomy are all indicators you’re dealing with trees in your problem.
• Polygon: graphs that do start and end at the same place (cyclic) which represent a shape or region in a physical space. Other words like configuration and boundary all indicate that your problem statement might be dealing with polygons.

Recursive objects

A recursive object, unlike a combinatorial object like from above, just takes the countable things and asks “what happens when you remove one of those things?”

In other words, if you remove 1 item from a set it results in a smaller set of permutations.

Same thing with a string: just delete one letter and you have a smaller string.

Subsets are inherently recursive because by removing one object, that in itself is a subset.

With a set of points, split the points down the middle with a line and now you have two smaller sets of points. (Same applies to a polygon).

Deleting one node from a graph is just a smaller graph.

Deleting one node from a tree is just a smaller tree. You get the idea…

With recursive objects, your base case is always the empty or solo set (or in the case of a polygon, a triangle).

With the above objects available at our disposal, we have all of the tools necessary to begin mapping our problem out into real objects which we can then manipulate with our algorithms.

The Daily Problem

Skiena offers a problem to think over for each following lecture. This is sort of like a quick practice problem to test if you’ve grasped the previous lecture’s core ideas. At the start of the next lecture, he goes over the problem (and solution) in detail. So for the August 30th lecture 2 days from now, he’s going to solve Problem 1-5 in The Algorithm Design Manual. Here’s what it looks like:

The knapsack problem is as follows: given a set of integers S = {s1, s2, . . . , sn}, and a target number T, find a subset of S which adds up exactly to T. For example, there exists a subset within S = {1,2,5,9,10} that adds up to T = 22 but not T = 23.

Find counterexamples to each of the following algorithms for the knapsack problem.

That is, give an S and T where the algorithm does not find a solution which leaves the knapsack completely full, even though a full-knapsack solution exists.

(a) Put the elements of S in the knapsack in left to right order if they fit, i.e. the first-fit algorithm.

(b) Put the elements of S in the knapsack from smallest to largest, i.e. the best-fit algorithm.

(c) Put the elements of S in the knapsack from largest to smallest.

My plan is to solve the problem before the lecture, throw it up in the next article in the series to start off the article, see if it lines up with the answer given in the lecture, and then compare and contrast the different approaches as well as discuss any flaws or issues that arose along the way.

See you next time!

Wow, this is probably one of the longest posts I’ve ever written. I hope this post has convinced you to finally learn data structures and algorithms once and for all. Even if you aren’t dedicated to taking the entire course, I hope this stands to be a reference guide if there are ever parts or pieces of this that you might want to reference or check when working with these things in JavaScript.