Questions tagged [ds.algorithms]
Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.
1,795
questions
-2
votes
2
answers
712
views
At last P != NP or not [duplicate]
Possible Duplicate:
Is the recent proof that P != NP correct?
some weeks ago I heard a news that some one proof that P != NP (link1 - link2) andsome days later I heard that he was wrong (I can't ...
- 105
6
votes
3
answers
316
views
Linear Time Maximum Clearance Computation on a Grid Graph?
I have a uniform NxN grid with a non-empty subset of vertices marked as obstacles. My goal is to compute, for each non-obstacle vertex, the "maximum clearance" from the obstacle set. In other words, ...
- 151
0
votes
3
answers
323
views
Image processing algorithms [closed]
Is there any place, where description of formalized image processing algorithms can be found? Like creating hdr images, bluring images, etc.
- 103
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 ...
- 31.9k
13
votes
1
answer
944
views
Space-time tradeoff lower bounds
Following the discussion on lower bounds for 3SAT [1], I'm wondering what are the main lower bound results formulated as space-time tradeoffs. I'm excluding results such as, say, Savitch's theorem; a ...
9
votes
2
answers
360
views
Quick encoding of balanced vectors
It is easy to see that for any $n$ there exists a 1-1 mapping $F$ from {0,1}$^n$ to {0,1}$^{n+O(\log n)}$ such that for any $x$ the vector $F(x)$ is "balanced", i.e., it has equal number of 1s and 0s. ...
- 971
17
votes
2
answers
1k
views
A reading list on experimental algorithmics
As in, the area of the papers in the ACM Journal on Experimental Algorithmic JEA.
Which were the foundational works? What are the main results? How are they characterized? Any interesting connections ...
23
votes
9
answers
1k
views
Reductions from the book.
This is along the lines of "Algorithms from the Book". Although reductions are algorithms as well, I thought it doubtful that one would think of a reduction in response to the question about ...
1
vote
3
answers
919
views
Complexity of a variant of the Mandelbrot set decision problem?
Mandelbrot set is defined using the complex equation $P_c (z)=z^2 +c$ where $c$ is a complex number
Let Set $M=${$(c,k,m) |$ the sequence $P_c (0),P_c (P_c (0)), P_c (P_c (P_c (0)))...$ is unbounded ...
- 20.8k
8
votes
6
answers
729
views
Have any generalizations of maximum weight matching been studied?
For example, one way to view maximum weight matching is that each vertex $v$ gets a utility $f_v= w(e_v)$ that equals the weight of the edge it's matched on, and zero otherwise.
accordingly, a ...
40
votes
10
answers
13k
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
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
8
votes
0
answers
423
views
Type inference with subtype constraints and polymorphism using Trifonov and Smith's constraint maps
Trifonov and Smith's Subtyping Constrained Types (1996) introduces constraint maps to represent consistent closed constraint sets (such maps providing sets of lower and upper bounds to each variable ...
- 1,379
38
votes
2
answers
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 \...
- 1,870
2
votes
3
answers
1k
views
Best bounds for the longest path optimization problem in cubic Hamiltonian graph?
optimization problem
Input: cubic Hamiltonian graph
feasible solution: A simple path
measure to optimize: length of the simple path
Design a polynomial-time algorithm that outputs the longest path ...
- 20.8k
3
votes
2
answers
327
views
What is the complexity of computing a compatible 3-coloring of a complete graph?
Given a complete graph whose edges are colored by 3 colors, a compatible 3-coloring is a coloring of nodes such that no edge of the graph has the same color as its end-points.
The best algorithm I ...
- 20.8k
2
votes
1
answer
352
views
What is the most efficient algorithm to sample graphs with trivial automorphism groups ?
Let us call a graph "asymmetric" if it has no nontrivial automorphism group. http://en.wikipedia.org/wiki/Asymmetric_graph
I'm looking for an efficient way to compute a random asymmetric graph on a ...
- 20.8k
11
votes
4
answers
489
views
Dimensionality reduction with slack?
The Johnson-Lindenstrauss lemma says roughly that for any collection $S$ of $n$ points in $\mathbb{R}^d$, there exists a map $f:\mathbb{R}^d \rightarrow \mathbb{R}^k$ where $k = O(\log n/\epsilon^2)$ ...
- 9,830
7
votes
4
answers
1k
views
What are the best known upper bounds and lower bounds for computing O(log n)-Clique?
Input: a graph with n nodes,
Output: A clique of size $O(\log n)$,
Providing links to references would be great
- 20.8k
122
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 ...
12
votes
3
answers
473
views
Streaming derandomization
Stream algorithms require randomization for the most part to do anything nontrivial, and because of the small-space constraint, need PRGs that use little space. I know of two methods that have been ...
- 31.9k
28
votes
3
answers
1k
views
How to produce a random graph that does not have a Hamiltonian cycle?
Let class A denote all the graphs of size $n$ which have a Hamiltonian cycle. It is easy to produce a random graph from this class--take $n$ isolated nodes, add a random Hamiltonian cycle and then add ...
- 1,945
23
votes
3
answers
2k
views
What bounds can be put on counting reachable nodes in a dag?
Given is a dag. You want to label each node by how many nodes are reachable from it. $O(V(V+E))$ is a trivial upper bound; $\Omega(V+E)$ is a lower bound (I think). Is there a better algorithm? Is ...
- 4,786
25
votes
6
answers
3k
views
Graph families which have polynomial time algorithms for computing the chromatic number
Post updated on 31st of August: I added a summary of the current answers below the original question. Thanks for all the interesting answers! Of course, everyone can continue posting any new findings.
...
- 503
7
votes
4
answers
3k
views
What are the most effective algorithms to find random number?
I was reading the Ramsey's Theory stating "complete disorder is impossible". Is there any algorithm to generate random numbers for a long period of time without there being any relation from one set ...
- 181
4
votes
4
answers
4k
views
Why is P vs. NP so hard? [closed]
Why is $\mathsf{P}$ vs. $\mathsf{NP}$ problem considered so important?
Is $\mathsf{P}$ vs. $\mathsf{NP}$ the hardest mathematical problem?
Why is it so hard?
All I'm looking for is the hindrances ...
- 175
12
votes
12
answers
7k
views
What are some real world applications for genetic algorithms?
What are some real world problems that have been solved using a genetic algorithm? What is the problem? What is the fitness test used to solve this problem?
- 528
22
votes
6
answers
1k
views
Analogs of compressed sensing
In compressed sensing, the goal is to find linear compression schemes for huge input signals that are known to have a sparse representation, so that the input signal can be recovered efficiently from ...
- 6,960
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.4k
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,811
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 ...
16
votes
2
answers
363
views
Finding small sets of integers in which every element is a sum of two others
This is a follow-up to this question on math.stackexchange.
Let us say that a non-empty set S ⊆ ℤ is self-supporting if for every a ∈ S, there exist distinct ...
- 8,801
10
votes
2
answers
246
views
Shuffling of tokens on a graph using local swaps
Let $G= (V, E)$ be a non-regular connected graph whose degree is bounded. Suppose that each node contain a unique token.
I want to uniformly shuffle the tokens amongst the graph using only local ...
- 3,043
24
votes
2
answers
551
views
Parallel Dynamic Search
Is there a natural parallel analog to red-black trees with similar or even not-terribly-worse properties for updates while being reasonably work-efficient ?
More generally, what's the best we can do ...
- 31.9k
8
votes
5
answers
763
views
Algorithm for inverting a bijective function.
Does there exist a generalized algorithm for finding the inverse function of an arbitrary bijective function?
In order for this algorithm to be
useful, it must eventually halt once
the correct answer ...
- 207
379
votes
92
answers
113k
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 ...
13
votes
1
answer
349
views
Finding odd holes in circulant Paley graphs
The Paley graphs Pq are those whose vertex-set is given by the finite field GF(q), for prime powers q≡1 (mod 4), and where two vertices are adjacent if and only if they differ by a2 ...
- 8,801
-1
votes
2
answers
616
views
Minimum spanning tree algorithm. [closed]
Is the following a valid algorithm for finding a minimum spanning tree?
Given a weighted graph with unique weights, remove the all edges that are the highest cost edge in any cycle of the original ...
- 151
128
votes
11
answers
11k
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 ...
- 22.9k
8
votes
1
answer
457
views
Best resources for string searching or pattern matching exercises
I would like to be somewhat good at string searching and pattern matching, could you point me to some good online resources? Exercise problems would be great. Thanks.
17
votes
1
answer
1k
views
Online transitive closure better than O(N^2) per edge addition
I'm looking for an online algorithm to maintain the transitive closure of a directed acyclic graph with a time complexity less than O(N^2) per edge addition. My current algorithm is like this:
...
- 696
16
votes
6
answers
4k
views
Complexity of the Fisher-Yates Shuffle Algorithm
This question is in regard to the Fisher-Yates algorithm for returning a random shuffle of a given array. The Wikipedia page says that its complexity is O(n), but I think that it is O(n log n).
In ...
- 623
10
votes
1
answer
320
views
Generalizing the FFT
Can the divide and conquer nature of the FFT be generalized to other transforms (z Transform, chirp, etc) automatically?
Is there an algorithm that takes in a description of transform (I don't know ...
8
votes
1
answer
1k
views
What are some effective heuristics to find the number of Hamiltonian paths in a rectangular grid?
A particular programming problem I came across recently reduces to finding hamiltonian paths in a rectangular grid that would look something like,
...
- 191
13
votes
2
answers
1k
views
What is a good special-case sorting algorithm?
I have a dataset which is a number of objects arranged in a 2-D grid. I know I have a strict ordering, increasing as you go left-to-right within each row, and increasing as top-to-bottom within each ...
- 353