Kevin Sun

What is "algorithms"?

December 24, 2020

I think the phrase "It's hard to explain what I do" is kind of snobby. But I get the sentiment, because many professions and fields of study are obscure and/or unknown to the general public. Or worse, the general public thinks they understand a profession or field of study, but they actually don't.

For example, mathematicians work on problems that bear little to no resemblance to the AP Calculus curriculum, which I (snobbily) imagine was the "peak" mathematics experience for most people. Thus, if someone says "I'm a mathematician," most people would not have an accurate understanding of what that entails.

And I don't blame them — if you asked me what biologists study, I'd probably try to recite some facts I learned in high school. "The mitochondria is the powerhouse of the cell."

Similarly, many people have a misconception of computer science, as well as what it means to have a PhD. William Gasarch recently summarized all three of these misconceptions:

I avoid saying I am a doctor since people will then ask me about the medical condition.

I avoid saying I am a computer scientist since people will then ask me how to help them with their Facebook privacy settings.

I avoid saying I am a mathematician since people will ask me to help their daughter with her trigonometry.

So when someone asks me what I do, I'm tempted to say, "It's hard to explain," but I don't want to sound snobby. At the same time, I don't want to say something misleading. My response (these days) is usually something along the lines of studying algorithms.

But what is algorithms? This is tough to answer because (I think) it's a polyseme: a word or phrase with different, but related meanings. Wikipedia has some great examples:

Similarly, (I think) algorithms is a polyseme — let's explore some of its meanings.

Even restricted to everyday contexts, the word "algorithm" already has multiple connotations. It could refer to a procedure that's dry and tedious, such as the addition algorithm taught in elementary schools (i.e., "right to left, carry the one," etc.). At the same time, it could refer to a complex and opaque system, such as the "YouTube algorithm."

While the addition algorithm is a short sequence of specific steps, the "YouTube algorithm" refers to a multitude of procedures, such as how the website selects videos to promote on its homepage, how it recommends videos to individual viewers to "watch next," and how it ranks the results of search queries. So already, given that algorithms can refer to two vastly different concepts, it's certainly unclear what it means to study them.

The situation is simpler if I'm talking to someone who's taken a class on algorithms (e.g., a computer science student). To them, algorithms often refers to a specific course titled something like "Design and Analysis of Algorithms" and often gets abbreviated as "algo" in conversations (e.g., "I'm taking algo next semester"). But luckily, these courses tend to capture the idea of what I do, so I can just say, "It's like the stuff in this course."

Interestingly, most courses on algorithms do not formally define the term algorithms. Instead, these formalities are usually taught in a course titled something like "Theory of Computation."

Speaking of which, what's the connection between the formal definition (something about Turing machines) and the informal definition (a sequence of steps)? Basically, for most purposes, the two definitions are essentially the same and only some computer scientists think about the details. (This connection is known as the Church-Turing thesis.)

Anyway, just as algorithms can refer to a college course, it can also refer to an area of research in computer science. This, of course, is what most people mean if they say they study/design/work on algorithms. They're referring to an academic field complete with publications, conferences, journals, presentations, and the like.

Back outside of academia, there's yet another kind of algorithms: the ones that people study for technical interviews. The technical/coding interview is a notorious part of the job-seeking process for software engineers (and similar positions). In fact, there are entire books (e.g., Cracking the Coding Interview), and websites (e.g., LeetCode) that help job applicants practice and prepare for these interviews.

Another aside: the term data structures is frequently found in the job-seeking context as well. To a job seeker, this refers to things like linked lists and binary search trees. To a college student, this refers to a second-semester course in computer science. And to a layman, I don't think it refers to anything.

Update: So anyway, what do I think of when I use the word algorithms? Well, as mentioned above, I'm basically referring to the content of a standard undergraduate course in a computer science department. In fact, I even wrote an entire mini textbook that summarizes this content. And it's free! I hope you'll find it interesting. I also wrote another post, answering the question of why I think we should learn algorithms.