Questions tagged [ds.algorithms]
Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.
1,814
questions
381
votes
92
answers
114k
views
Algorithms from the Book
Paul Erdős 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 ...
328
votes
29
answers
202k
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 ...
- 7,629
145
votes
2
answers
19k
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?
...
- 23.1k
129
votes
11
answers
12k
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 ...
- 23.1k
123
votes
18
answers
9k
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 ...
106
votes
6
answers
53k
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 ...
97
votes
2
answers
40k
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 ...
- 23.1k
75
votes
9
answers
16k
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 ...
71
votes
17
answers
9k
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, ...
65
votes
10
answers
12k
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 ...
- 16.5k
62
votes
4
answers
4k
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 ...
- 803
59
votes
6
answers
3k
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 ...
- 36.9k
59
votes
10
answers
4k
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 ...
- 32k
57
votes
13
answers
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 ...
57
votes
10
answers
18k
views
Recent advances in computer science since 2010?
Since I left school (early 2010s) a couple of recently developed techniques were widely adopted by the industry. For example,
Asymmetric numeral systems for compression (e.g. Ubuntu ships with ...
- 651
55
votes
7
answers
4k
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) ...
- 11.3k
54
votes
11
answers
5k
views
If you could rename dynamic programming...
If you could rename dynamic programming, what would you call it?
51
votes
9
answers
11k
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 ...
- 16.5k
51
votes
6
answers
28k
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 ...
- 627
51
votes
8
answers
5k
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 ...
- 8,911
49
votes
8
answers
9k
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 ...
- 21.5k
46
votes
8
answers
6k
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 ...
46
votes
8
answers
21k
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 ...
- 11.9k
46
votes
5
answers
3k
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 ...
- 50.9k
43
votes
3
answers
3k
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})}$. ...
- 20.8k
41
votes
6
answers
3k
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 ...
41
votes
2
answers
6k
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 ...
- 23.1k
41
votes
4
answers
12k
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(...
- 747
40
votes
10
answers
14k
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, ...
Chris
40
votes
1
answer
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)$ ...
- 4,367
39
votes
9
answers
4k
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 ...
- 877
39
votes
2
answers
6k
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 ...
- 522
38
votes
8
answers
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 ...
- 8,911
38
votes
4
answers
2k
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. ...
- 11.3k
38
votes
2
answers
3k
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 \...
- 1,870
37
votes
5
answers
2k
views
Integer multiplication when one integer is fixed
$n$ is a parameter in the problem.
For every $n$ we pick a random integer $a_n\in\{2^{n-1},2^{n-1}+1,\dots,2^n-1\}$ where $n\in\{1,2,\dots\}$.
Problem: Given $n$ what is the complexity of ...
- 12.8k
37
votes
3
answers
5k
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 ...
- 9,850
36
votes
8
answers
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 >...
- 1,560
36
votes
1
answer
2k
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 "...
- 4,902
35
votes
11
answers
2k
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 ...
- 951
35
votes
3
answers
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 ...
- 562
34
votes
3
answers
2k
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 $\...
- 11.3k
33
votes
9
answers
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 ...
- 6,970
33
votes
5
answers
3k
views
Complexity of applying a permutation in-place
To my surprise, I was not able to find papers about this - probably searched the wrong keywords.
So, we've got an array of anything, and a function $f$ on its indices; $f$ is a permutation.
How do ...
- 8,911
32
votes
5
answers
5k
views
Counting words accepted by a regular grammar
Given a regular language (NFA, DFA, grammar, or regex), how can the number of accepting words in a given language be counted? Both "with exactly n letters" and "with at most n letters" are of ...
- 1,737
32
votes
5
answers
1k
views
"Directed" problems that are easier than their "undirected" variant.
I was presenting a lecture on pancake sorting, and mentioned that:
Sorting by reversals is NP-hard
"signed" sorting by reversals is in P.
Which got me thinking. There is a sense in which "signed" ...
- 32k
32
votes
3
answers
3k
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 ...
- 421
31
votes
5
answers
1k
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 ...
- 4,681
31
votes
3
answers
2k
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 ...
- 2,717
31
votes
2
answers
982
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 ...
- 516