Questions tagged [ds.algorithms]

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

1,594 questions
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, ...
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.
3k views

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 ...
689 views

Following the discussion on lower bounds for 3SAT , 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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
2k views

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 ...
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 ...
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 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 ...
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 ...
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 ...
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.
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: ...
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 ...
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 ...