As of May 31, 2023, we have updated our Code of Conduct.

# 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
Filter by
Sorted by
Tagged with
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 ...
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, ...
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.
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 ...
944 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 ...
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. ...
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 ...
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
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 ...
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 ...
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, ... 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 ...
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 ...
2k views

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