# Questions tagged [ds.algorithms]

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

1,603 questions
Filter by
Sorted by
Tagged with
1answer
284 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 ...
1answer
248 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 ...
1answer
245 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. ...
1answer
332 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$ ...
1answer
280 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 ...
1answer
249 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....
1answer
280 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 ...
2answers
763 views

0answers
231 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 ...
1answer
83 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 ...
1answer
165 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 ...
2answers
380 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. ...
1answer
94 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 ...
1answer
246 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 ...
1answer
298 views

2answers
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 ...
0answers
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....
1answer
169 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 , ...
4answers
243 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$, ...
1answer
213 views

1answer
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 ...
2answers
524 views

1answer
215 views

3answers
1k views

### How to design concurrent data structures?

I previously asked this question on Programmers.SE, without success. I'm looking for written learning resources on how to design concurrent data structures. I'm more interested in the design process (...