When are two algorithms said to be "similar"?

Question

I do not work in theory, but my work requires reading (and understanding) theory papers every once in a while. Once I understand a (set of) results, I discuss these results with people I work with, most of whom do not work in theory as well. During one of such discussions, the following question came up:

When does one say that two given algorithms are "similar"?

What do I mean by "similar"? Let us say that two algorithms are said to be similar if you can make either of the following claims in a paper without confusing/annoying any reviewer (better definitions welcomed):

Claim 1. "Algorithm $A$, which is similar to algorithm $B$, also solves problem $X$"

Claim 2. "Our algorithm is similar to Algorithm $C$"

Let me make it slightly more specific. Suppose we are working with graph algorithms. First some necessary conditions for the two algorithms to be similar:

1. They must be solving the same problem.
2. They must have the same high level intuitive idea.

For instance, talking about graph traversal, breadth-first and depth-first traversal satisfy the above two conditions; for shortest-path computations, breadth-first and Dijkstra's algorithm satisfy the above two conditions (on unweighted graphs, of course); etc.

Are these also sufficient conditions? More specifically, suppose two algorithms satisfy the necessary conditions to be similar. Would you indeed call them similar, if

1. they have different asymptotic performance?
2. for a special class of graphs, one algorithm requires $\Omega(n)$ time while the other requires $O(n^{1/3})$ time?
3. they have different terminating conditions? (recall, they are solving the same problem)
4. the pre-processing step is different in the two algorithms?
5. the memory complexity is different in the two algorithms?

Edit: The question is clearly very context dependent and is subjective. I was hoping that the above five conditions, however, will allow getting some suggestions. I am happy to further modify the question and give more details, if needed to get an answer. Thanks!

Answer 1

It is a tough problem to give even a coherent definition of "Algorithm A is similar to Algorithm B". For one, I don't think that "they must be solving the same problem" is a necessary condition. Often when one says in a paper that "the algorithm $A$ of Theorem $2$ is similar to the algorithm $B$ in Theorem $1$", the algorithm $A$ is actually solving a different problem than that of $B$, but has some minor modifications to handle the new problem.

Even trying to determine what it means for two algorithms to be the same is an interesting and difficult problem. See the paper "When are two algorithms the same?" http://research.microsoft.com/~gurevich/Opera/192.pdf

Answer 2

More often than not, it means "I don't want to write out Algorithm B in detail, because all the interesting details are nearly identical to those in Algorithm A, and I don't want to go over the 10-page limit, and anyway the submission deadline is in three hours."

Answer 3

If you mean "similar" in the colloquial sense, I think JeffE's answer captures what some people mean.

In a technical sense though, it depends on what you care about. If asymptotic time complexity is all you care about, the difference between recursion and iteration may not matter. If computatability is all you care about, the difference between a counter variable and a one-symbol stack do not matter.

To compare algorithms, a first step would be to make the notion of equivalence precise. Intuitively, let $A$ be the space of algorithms and $M$ be a space of mathematical objects and $\mathit{sem}: A \to M$ be a function encoding that $\mathit{sem}(P)$ is the meaning of algorithm $P$. The space $M$ could contain anything ranging from the number of variables in your algorithm, to its state-graph or it's time complexity. I don't believe there is an absolute notion of what $M$ can be. Given $M$ though, we can say two algorithms are equivalent if $\mathit{sem}(P)$ equals $\mathit{sem}(Q)$. Let me add that I think each of the five criteria you mentioned can be formalised mathematically in this manner.

If we want to talk about an algorithm being more general than another (or an algorithm refining another), I would endow $M$ with more structure. Imagine that $(M, \sqsubseteq)$ is a partially ordered set and the order $x \sqsubseteq y$ encodes that $x$ is a more defined object than $y$. For example, if $M$ contains sets of traces of an algorithm and $\sqsubseteq$ is set inclusion, $\mathit{sem}(P) \sqsubseteq \mathit{sem}(Q)$ means that every trace of $P$ is a trace of $Q$. We can interpret this as saying that $P$ is more deterministic than $Q$.

Next, we could ask if it's possible to quantify how close two algorithms are. In this case, I would imagine that $M$ has to be endowed with a metric. Then, we can measure the distance between the mathematical objects that two algorithms represent. Further possibilities are to map algorithms to measure spaces or probability spaces and compare them using other criteria.

More generally, I would ask - what do you care about (in intuitive terms), what are the mathematical objects representing these intuitive properties, how can I map from algorithms to these objects, and what is the structure of this space? I would also ask if the space of objects enjoys enough structure to admit a notion of similarity. This is the approach I would take coming from a programming language semantics perspective. I'm not sure if you find this approach appealing, given the vastly different cultures of thought in computer science.

Answer 4

Along the lines of Jeff's answer, two algorithms are similar if the author of one of them expects that the author of the other one might be reviewing her paper.

But joking aside, in the theory community, I would say that what problem algorithm A is solving is rather tangental to whether it is "similar" to algorithm B, which might be solving a completely different problem. A is similar to B if it "works" because of the same main theoretical idea. For example, is the main idea in both algorithms that you can project the data into a much lower dimensional space, preserve norms with the Johnson-Lindenstrauss lemma, and then do a brute-force search? Then your algorithm is similar to other algorithms that do this, no matter what problem you are solving. There are some small number of heavy-duty algorithmic techniques that can be used to solve a wide variety of problems, and I would think that these techniques form the centroids of many sets of "similar" algorithms.

Answer 5

Very interesting question, and very nice paper Ryan!

I do definitely agree with the idea that making an assessment on the overall similarity between algorithms is mainly a subjective value judgement. While from a technical point of view there are a number of features that are closely observed to decide upon the similarity of algorithms, in the end, it is also a matter of personal taste. I will try to provide a description of the importance of both sides of the same coin while referring to the particular points of your question:

From a technical point of view:

1. Ryan already pointed out that both algorithms must solve the same problem. One could go even further and generalize this notion by saying that it is usually enough to prove that there is a polynomial transformation of the same instance that is understoodable by algorithm A so that algorithm B can handle it. However, this would be actually very weak. I do prefer to think of the similarity in a stronger sense.
2. However, I would never expect for two equivalent algorithms to have the same intuitive idea ---though, again, this is a definition which ain't easy to capture. More than that, it is often the case that algorithms that are deemed to be similar do not follow the main rationale. Consider for example some sorting algorithms which however, originated in different ways following different ideas. As an extreme example consider genetic algorithms which are usually considered by the mathematical community just as stochastic processes (and therefore they are equivalent in their view) which are then modeled and analyzed in quite a different way.
3. Moreover, I would even generalize this notion to say that other technicalities such as the termination condition or the pre-processing stage do not matter often. But this is not always the case. See for example Dijkstra's Algorithm versus Uniform Cost Search or a Case Against Dijkstra's Algorithm. Both algorithms are so close that most people do not tell the difference, yet the differences (being technical) were very important for the author of that paper. Much the same happens with the pre-processing step. In case you are familiar with the $N$-puzzle, then observe that an A$^*$-like search algorithm using the Manhattan distance or $(N^2-1)$ additive pattern databases would actually expand the same number of nodes in exactly the same order, and that makes both algorithms (and their heuristics) to be strictly equivalent in a very strong sense, whereas the first approach has no pre-processing and the second one has a significant overhead before starting to solve a particular instance. However, as soon as your Pattern Databases consider more simulatenous interactions there is a huge gap in performance between them, so that they are definitely different ideas/algorithms.
4. As a matter of fact, I think that most people would judge algorithms for their purpose and performance. Therefore, asymptotic performance is a good metric to reason about the similarity between programs. However, bear in mind that this performance is not necessarily the typical case so that if two algorithms have the same asymptotic performance but behave differently in practice, then you would probably conclude that they are different. The strong evidence in this regard would be that both algorithms have the same performance both on time and memory (and this, as Suresh said, makes DFS and BFS to look different). In case this assertion does not sound convincing to you, please refer to the excellent (and very recommended book): Programming the Universe by Seth Lloyd. In page 189 he refers to a list with more than 30 measures of complexity that can be used to regard algorithms as being different.

So what makes algorithms to be similar/different? In my view (and this is purely speculative), the main difference is about what they suggest to you. Many, many (many!) algorithms differ just in a few technicalities when serving to the same purpose so that the typical case is different for different ranges of the input. However, the greatest of all differences is (to my eye) what they suggest to you. Algorithms have different capabilities and therefore their own strengths and weaknesses. If two algorithms look like being the same but might be extended in different ways to cope with different cases then I would conclude that they are different. Often, however, two algorithms do look much the same so that you would regard them to be the same ... until someone arrives making a key distinction and suddenly, they are completely different!

Sorry, my response was in the end so long ...

Cheers,

Answer 6

Any mention of similarity without defining a similarity metric is not well-defined. There are many ways in which two algorithms can be similar:

Quicksort and Mergesort solve very similar problems, but they use different algorithms to do so. They have similar algorithmic complexity (although their worst-case performance and memory usage can vary). Quicksort and Mergesort are both similar to Bubblesort,however Bubblesort has very different performance metrics. If you ignore complexity statistics Quicksort, Mergesort and Bubblesort are all in the same equivalence class. However, if you care at all about algorithmic complexity, then Quicksort and Mergesort are much more similar to each other than either is to Bubblesort.

Smith-Waterman dynamic programming and HMM-sequence comparison attempt to solve the problem of aligning two sequences. However, they take different inputs. Smith-Waterman takes two sequences as input, and HMM-sequence comparisons take a HMM and a sequence as input. Both output sequence alignments. In terms of motivating ideas, both of these are similar to Levenshtein's edit distance, but only at a very high level.

Here are some criteria by which two algorithms might be called similar:

1. Input/output types
2. Algorithmic/Memory Complexity
3. Assumptions about types of inputs (eg only positive numbers or floating point stability)
4. Nested relationships (eg some algorithms are special cases of others)

The critical decision about the meaning of similarity remains. Sometimes you care about the complexity of an algorithm, sometimes you don't. As the definition of similarity depends on the context of the discussion, the term "similar algorithm" isn't well-defined.