Questions tagged [ds.algorithms]

Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.

Filter by
Sorted by
Tagged with
357
votes
93answers
108k views

Algorithms from the Book.

Paul Erdos talked about the "Book" where God keeps the most elegant proof of each mathematical theorem. This even inspired a book (which I believe is now in its 4th edition): Proofs from the Book. If ...
305
votes
29answers
191k views

Core algorithms deployed

To demonstrate the importance of algorithms (e.g. to students and professors who don't do theory or are even from entirely different fields) it is sometimes useful to have ready at hand a list of ...
140
votes
2answers
18k views

Super Mario Galaxy problem

Suppose Mario is walking on the surface of a planet. If he starts walking from a known location, in a fixed direction, for a predetermined distance, how quickly can we determine where he will stop? ...
117
votes
11answers
10k views

How hard is unshuffling a string?

A shuffle of two strings is formed by interspersing the characters into a new string, keeping the characters of each string in order. For example, MISSISSIPPI is a ...
112
votes
17answers
8k views

Examples of the price of abstraction?

Theoretical computer science has provided some examples of "the price of abstraction." The two most prominent are for Gaussian elimination and sorting. Namely: It is known that Gaussian elimination ...
96
votes
6answers
45k views

How do the state-of-the-art pathfinding algorithms for changing graphs (D*, D*-Lite, LPA*, etc) differ?

A lot of pathfinding algorithms have been developed in recent years which can calculate the best path in response to graph changes much faster than A* - what are they, and how do they differ? Are ...
72
votes
2answers
21k views

What is the actual time complexity of Gaussian elimination?

In an answer to an earlier question, I mentioned the common but false belief that “Gaussian” elimination runs in $O(n^3)$ time. While it is obvious that the algorithm uses $O(n^3)$ arithmetic ...
67
votes
9answers
12k views

Powerful Algorithms too complex to implement

What are some algorithms of legitimate utility that are simply too complex to implement? Let me be clear: I'm not looking for algorithms like the current asymptotic optimal matrix multiplication ...
59
votes
17answers
7k views

Polynomial-time algorithms with huge exponent/constant

Do you know sensible algorithms that run in polynomial time in (Input length + Output length), but whose asymptotic running time in the same measure has a really huge exponent/constant (at least, ...
59
votes
10answers
10k views

One Stack, Two Queues

background Several years ago, when I was an undergraduate, we were given a homework on amortized analysis. I was unable to solve one of the problems. I had asked it in comp.theory, but no ...
59
votes
4answers
3k views

Evidence that matrix multiplication can be done in quadratic time?

It is widely conjectured that $\omega$, the optimal exponent for matrix multiplication, is in fact equal to 2. My question is simple: What reasons do we have for believing that $\omega = 2$? I'm ...
56
votes
10answers
3k views

Provable statements about genetic algorithms

Genetic algorithms don't get much traction in the world of theory, but they are a reasonably well-used metaheuristic method (by metaheuristic I mean a technique that applies generically across many ...
52
votes
13answers
3k views

For which algorithms is there a large gap between the theoretical analysis and reality?

Two ways of analyzing the efficiency of an algorithm are to put an asymptotic upper bound on its runtime, and to run it and collect experimental data. I wonder if there are known cases where there ...
52
votes
7answers
3k views

For which problems in P is it easier to verify the result than to find it?

For (search versions) of NP-complete problems, verifying a solution is clearly easier than finding it, since the verification can be done in polynomial time, while finding a witness takes (probably) ...
47
votes
8answers
4k views

Are there non-constructive algorithm existence proofs?

I remember I might have encountered references to problems that have been proven to be solvable with a particular complexity, but with no known algorithm to actually reach this complexity. I struggle ...
45
votes
5answers
2k views

Positive topological ordering

Suppose I have a directed acyclic graph with real-number weights on its vertices. I want to find a topological ordering of the DAG in which, for every prefix of the topological ordering, the sum of ...
44
votes
8answers
5k views

The importance of Integrality Gap

I always had trouble in understanding the importance of the Integrality Gap (IG) and bounds on it. IG is the ratio of (the quality of) an optimal integer answer to (the quality of) an optimal real ...
44
votes
8answers
5k views

Obituaries of dead conjectures

I am looking for conjectures about algorithms and complexity that were viewed credible by many at some point in time, but later they were either disproved, or at least disbelieved, due to mounting ...
43
votes
11answers
4k views

If you could rename dynamic programming…

If you could rename dynamic programming, what would you call it?
43
votes
8answers
6k views

Best Upper Bounds on SAT

In another thread, Joe Fitzsimons asked about "the best current lower bounds on 3SAT." I'd like to go the other way: What's the best current upper bounds on 3SAT? In other words, what is the time ...
42
votes
5answers
2k views

Theoretical explanations for practical success of SAT solvers?

What theoretical explanations are there for the practical success of SAT solvers, and can someone give a "wikipedia-style" overview and explanation tying them all together? By analogy, the smoothed ...
41
votes
6answers
2k views

Which model of computation is “the best”?

In 1937 Turing described a Turing machine. Since then many models of computation have been decribed in attempt to find a model which is like a real computer but still simple enough to design and ...
40
votes
6answers
12k views

Complexity of Finding the Eigendecomposition of a Matrix

My question is simple: What is the worst-case running time of the best known algorithm for computing an eigendecomposition of an $n \times n$ matrix? Does eigendecomposition reduce to matrix ...
40
votes
3answers
2k views

Consequences of a quasi-polynomial time algorithm for the graph isomorphism problem

The Graph Isomorphism problem (GI) is arguably the best known candidate for an NP-intermediate problem. The best known algorithm is sub-exponential algorithm with run-time $2^{O(\sqrt{n \log n})}$. ...
39
votes
1answer
2k views

Sorting algorithm, such that each element is compared $O(\log n)$ times, and doesn't depend on a sorting network

Are there any known comparison sorting algorithms that do not reduce to sorting networks, such that each element is compared $O(\log n)$ times? As far as I know, the only way to sort with $O(\log n)$ ...
38
votes
2answers
5k views

Han's $O(n \log\log n)$ time, linear space, integer sorting algorithm

Is anyone familiar with Yijie Han's $O(n \log\log n)$, linear space, integer sorting algorithm? This result appears in a fairly short paper (Deterministic sorting in $O(n \log\log n)$ time and linear ...
37
votes
4answers
1k views

Examples where the uniqueness of the solution makes it easier to find

The complexity class $\mathsf{UP}$ consists of those $\mathsf{NP}$-problems that can be decided by a polynomial time nondeterministic Turing machine which has at most one accepting computational path. ...
37
votes
2answers
4k views

Sum-of-square-roots-hard problems?

The sum of square roots problem asks, given two sequences $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_n$ of positive integers, whether the sum $\sum_i \sqrt{a_i}$ less than, equal to, or greater ...
36
votes
9answers
11k views

Data for testing graph algorithms

I am looking for a source of huge data sets to test some graph algorithm implemention. Please also provide some information about the type/distribution (e.g. directed/undirected, simple/not simple, ...
36
votes
4answers
8k views

Is there a hash function for a collection (i.e., multi-set) of integers that has good theoretical guarantees?

I'm curious whether there is a way to store a hash of a multi-set of integers that has the following properties, ideally: It uses O(1) space It can be updated to reflect an insertion or deletion in O(...
35
votes
8answers
2k views

Higher-order algorithms

Most of the well-known algorithms are first-order, in the sense that their input and output are "plain" data. Some are second-order in a trivial way, for example sorting, hashtables or the map and ...
35
votes
5answers
2k views

Integer multiplication when one integer is fixed

Let $A$ be a fixed positive integer of size $n$ bits. One is allowed to pre-process this integer as appropriate. Given another positive integer $B$ of size $m$ bits, what is the complexity of ...
35
votes
3answers
3k views

Max-cut with negative weight edges

Let $G = (V, E, w)$ be a graph with weight function $w:E\rightarrow \mathbb{R}$. The max-cut problem is to find: $$\arg\max_{S \subset V} \sum_{(u,v) \in E : u \in S, v \not \in S}w(u,v)$$ If the ...
35
votes
8answers
3k views

Which definition of asymptotic growth-rate should we teach?

When we follow the standard textbooks, or tradition, most of us teach the following definition of big-Oh notation in the first few lectures of an algorithms class: $$ f = O(g) \mbox{ iff } (\exists c >...
35
votes
1answer
2k views

Multiplying n polynomials of degree 1

The problem is to compute the polynomial $(a_1 x + b_1) \times \cdots \times (a_n x + b_n)$. Assume that all coefficients fit in a machine word, i.e. can be manipulated in unit time. You can do $O(n \...
34
votes
11answers
1k views

Approximation algorithms for problems in P

One usually thinks about approximating solutions (with guarantees) to NP-hard problems. Is there any research going on in approximating problems already known to be in P? This might be a good idea for ...
34
votes
1answer
1k views

Toy Examples for Plotkin-Shmoys-Tardos and Arora-Kale solvers

I would like to understand how the Arora-Kale SDP solver approximates the Goemans-Williamson relaxation in nearly linear time, how the Plotkin-Shmoys-Tardos solver approximates fractional "packing" ...
34
votes
3answers
2k views

Given a weighted dag, is there an O(V+E) algorithm to replace each weight with the sum of its ancestor weights?

The problem, of course, is double counting. It's easy enough to do for certain classes of DAGs = a tree, or even a serial-parallel tree. The only algorithm I have found which works on general DAGs in ...
33
votes
3answers
1k views

Hardest known natural problem in P?

I wonder, what is (currently) the largest number $k$, such that a natural problem is known with the following properties: An $O(n^k)$ algorithm has been already found for the problem. For any fixed $\...
32
votes
6answers
3k views

Efficient and simple randomized algorithms where determinism is difficult

I often hear that for many problems we know very elegant randomized algorithms, but no, or only more complicated, deterministic solutions. However, I only know a few examples for this. Most ...
31
votes
5answers
12k views

Complexity of the simplex algorithm

What is the upper bound on the simplex algorithm for finding a solution to a Linear Program? How would I go about finding a proof for such a case? It seems as though the worst case is if each vertex ...
31
votes
9answers
2k views

Randomized algorithm that “looks” deterministic?

Is there an interesting example of a randomized algorithm for a search problem that always outputs the same (correct) answer, regardless of its internal randomness, but which exploits the randomness ...
31
votes
5answers
936 views

what is easy for minor-excluded graphs?

Approximating number of colorings seems to be easy on minor-excluded graphs using algorithm by Jung/Shah. What are other examples of problems that are hard on general graphs but easy on minor-excluded ...
31
votes
3answers
1k views

Consequences of existence of a strongly polynomial algorithm for linear programming?

One of the holy grails of algorithm design is finding a strongly polynomial algorithm for linear programming, i.e., an algorithm whose runtime is bounded by a polynomial in the number of variables and ...
31
votes
2answers
877 views

What classes of mathematical programs can be solved exactly or approximately, in polynomial time?

I am rather confused by the continuous optimization literature and TCS literature about which types of (continuous) mathematical programs (MPs) can be solved efficiently, and which cannot. The ...
30
votes
10answers
2k views

Great algorithms, machine learning and no linear algebra

I teach an advanced algorithms course and would like to include some topics related to machine learning which will be of interest to my students. As a result, I would like to hear people's opinions of ...
30
votes
3answers
2k views

Are any of the state of the art Maximum Flow algorithms practical?

For the maximum flow problem, there seem to be a number of very sophisticated algorithms, with at least one developed as recently as last year. Orlin's Max flows in O(mn) time or better gives an ...
29
votes
10answers
1k views

Current parallel models for computation

The 1980's gave rise to both the PRAM and the BSP models of parallel computation. It seems that both model's heyday were during the late 80s and early 90s. Are these areas still active in terms of ...
29
votes
2answers
2k views

Can you identify the sum of two permutations in polynomial time?

There were two questions asked recently on cs.se which were either related to or had a special case equivalent to the following question: Suppose you have a sequence $a_1, a_2, \ldots a_n$ of $n$ ...
29
votes
1answer
1k views

Finding a biased coin using a few coin tosses

The following problem came up during research, and it's surprisingly clean: You have a source of coins. Each coin has a bias, namely a probability that it falls on "head". For each coin ...