Questions tagged [ds.algorithms]

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

6
votes
3answers
305 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, ...
0
votes
3answers
287 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.
55
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 ...
13
votes
1answer
689 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 ...
10
votes
2answers
331 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. ...
16
votes
2answers
919 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 ...
22
votes
9answers
950 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
3answers
851 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 ...
8
votes
6answers
610 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 ...
36
votes
9answers
10k 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, ...
33
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 ...
8
votes
0answers
393 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 ...
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 \...
2
votes
3answers
924 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 ...
3
votes
2answers
320 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 ...
2
votes
1answer
337 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 ...
11
votes
4answers
456 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)$ ...
6
votes
4answers
744 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
110
votes
17answers
7k 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 ...
12
votes
3answers
417 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 ...
28
votes
3answers
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 ...
23
votes
3answers
1k 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 ...
23
votes
6answers
2k 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. ...
7
votes
4answers
2k 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 ...
3
votes
4answers
2k 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 ...
13
votes
12answers
5k 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?
22
votes
6answers
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 ...
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 ...
34
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 ...
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 ...
16
votes
2answers
341 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 ...
10
votes
2answers
226 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 ...
24
votes
2answers
525 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 ...
8
votes
5answers
548 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 ...
355
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 ...
13
votes
1answer
305 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 ...
-1
votes
2answers
562 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 ...
116
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 ...
8
votes
1answer
388 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.
15
votes
1answer
782 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: ...
15
votes
6answers
3k 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 ...
10
votes
1answer
290 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
1answer
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, ...
13
votes
2answers
830 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 ...