The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Questions tagged [ds.algorithms]

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

1,609 questions
Filter by
Sorted by
Tagged with
160 views

### Positive cut algorithm on bipartite graphs with negative weights

Let $G=(V,E,w)$ be a bipartite graph with weight function $w:E→\{-1,1\}$. Is there an efficient (polynomial) algorithm for finding some positive (not necessarily maximum) cut of $G$, if one exists? If ...
159 views

### Complexity of counting maximum number of co-linear points in Euclidean plane

The problem: given a set of points in the Euclidean plane, find the maximum number of co-linear points. I already know that the problem can be solved in quadratic time using hashing or projective ...
112 views

### Base extension in residue number systems with low space

Suppose I have a number $x$ represented in a residue number system, so $x = (x_1, \ldots, x_m)$, where $x_i \equiv x \pmod{p_i}$, and the $p_i$'s are all relatively prime (they can be distinct primes ...
330 views

### Pattern matching with don't cares: multiple patterns

Kalai's 2-page SODA paper gives a simple and efficient algorithm for pattern matching with don't cares (wildcards that match one character). In essence, it is as easy as convolution. But what happens ...
297 views

### Complexity of $k=2$ set packing

I am interested in the best currently known algorithm (in fact, any relevant reference) for the following problem: Given a family of subsets $S_1,S_2,\ldots S_N\subseteq \{1,2,\ldots N\}$, ...
83 views

### Constant time Lookup for Inversion Problem

I'm trying to figure out how to compute all the significant inversions $(i,j)$ in a list $l = [a_1, \ldots a_n]$ where an inversion $(i,j)$ is significant if $i < j$ but $a_i > 2a_j$. Now there ...
288 views

### Free books (or course materials) on undergraduate algorithms

What free books (or course materials) are there that cover undergraduate algorithms material? I added "course materials" in case there exist comprehensive sets of lecture notes/video/other that are ...
249 views

### Complexity involving connected components of 0/1 matrix

Assume a matrix has one component means we can traverse from a matrix entry $(i,j)$ which is $1$ to any other one by moving step of $(i\pm1,j),(i,j\pm1),(i\pm1,j\pm1)$ where each step you take you ...
256 views

### Find a string with minimal edit distance from a set of given strings

Input: a bunch of binary strings: x_0, x_1, ... , x_n Output: a binary string y that minimizes edit(x_0, y) + edit(x_1, y) + ... edit(x_n, y) where edit(x, y) denotes the levenshtein distance, i.e. ...
336 views

### Fast Algorithm to Check if a Set of Sets forms an Anti-chain

Given a set $S$ of sets, what is the fastest algorithm to check if elements of $S$ form an anti-chain with respect to subset ordering? That is, how can I quickly decide if there exists two sets $A$ ...
287 views

### Are there poly time algorithms to determine if a graph is almost bipartite?

Given an undirected graph G, we can say that G is almost bipartite if deleting k edges (or vertices) would make it bipartite. Are there poly time algorithms to determine if a graph is exactly or ...
257 views

### For a given binary-search tree obtain an isomorphic splay tree

I will assume that the reader is familiar with some undergraduate algorithms and data structures. To people who are not familiar with splay trees I recommend to read through this link : https://en....
283 views

### Enumerating all simply typed lambda terms of a given type

How can I enumerate all simply typed lambda terms which have a specified type? More precisely, suppose we have the simply typed lambda calculus augmented with numerals and iteration, as described in ...
808 views

241 views

### Approximating the VM packing problem

In the wikipedia article on bin-packing it is stated that A variant of bin packing that occurs in practice is when items can share space when packed into a bin. Specifically, a set of items could ...
84 views

### Density of multiples

I have an infinite collection of positive integers $n_1,n_2,n_3,\ldots$ and I would like to find the density of the numbers divisible by one or more of these.* If the density does not exist, the ...
167 views

### Is sparse embedding of a NP-complete problem in a polynomial problem NP-complete?

Consider the following problem P: Input is a finite graph G. If the number of vertices in G is 2^2^i for some integer i, then output a minimum vertex cover of G; otherwise output empty set. Can I say ...
393 views

### Confusing running time analysis for the Divide & Conquer algorithm of Hamiltonian Path problem

In the Hamiltonian Path problem we are given a graph $G=(V,E)$ and two distinct vertices $\{s,t\}$ and we ask if there is a path from $s$ to $t$ which traverses all other vertices exactly once. ...
96 views

### Proving hardness of approximation with reduction in terms of 1/$\epsilon$

I have a reduction that proves that a problem is NP-hard to approximate to a factor $1 + \epsilon$ for any $0 < \epsilon < 1$. The reduction is polynomial in $n$ (the size of the instance of the ...
258 views

### List of Pivot rules for simplex methods

Any implementation of the simplex method depends on the choice of pivot rule, which determines how the corners of the search space polyhedron are traversed. Many different have been proposed ...
299 views

276 views

### Is there research on algorithmic design patterns?

From what I've seen in the majority of algorithms publications, the focus of research is mainly towards improving the solutions to algorithmic problems in terms of efficiency or optimality in the case ...
109 views

### Algebraic dependence of roots of irreducibles over a finite field

I asked this question in Math SE too, but I have since modified it to make it more suited here. Also, in hindsight, the question itself was more algorithmic and was a better fit here. https://math....
170 views

### Efficient update of reachable set of a node in a digraph

Given a digraph $G = (V, E)$ and a set of vertices $S$, which does not change over the whole process, the goal is to compute the set of vertices, $R_{reach}$, reachable from $S$ and the set of nodes , ...
244 views

### Find the maximum subset contained by a ball of radius R

I am searching for the name of / literature to the algorithmic problem as follows: Given a metric space $(M,d)$, a finite Subset $X = \{ x_1, \dots, x_n \} \subset M$ and a fixed Radius $R > 0$, ...
216 views

203 views

### Algorithm/Complexity for the following SAT Version

Given : A 3 SAT problem. Known 1 : The SAT problem is satisfiable. Known 2 : We have a solution that satisfies the given 3 SAT. Problem Statement: Maximize the solution, i.e. find a solution such ...