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
7
votes
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 ...
2
votes
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 ...
6
votes
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. ...
5
votes
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$ ...
8
votes
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 ...
6
votes
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....
3
votes
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 ...
12
votes
2answers
763 views
Memory requirement for fast matrix multiplication
Suppose we want to multiply $n \times n$ matrices. The slow matrix multiplication algorithm runs in time $O(n^3)$ and uses $O(n^2)$ memory. The fastest matrix multiplication runs in time $n^{\omega + ...
9
votes
1answer
278 views
Evaluate boolean circuit on batch of similar inputs
Suppose I have a boolean circuit $C$ that computes some function $f:\{0,1\}^n \to \{0,1\}$. Assume the circuit is composed of AND, OR, and NOT gates with fan-in and fan-out at most 2.
Let $x \in \{0,...
3
votes
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 ...
2
votes
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 ...
5
votes
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 ...
6
votes
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. ...
-2
votes
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 ...
2
votes
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 ...
9
votes
1answer
298 views
How is the inner ring chosen in the Schönhage–Strassen algorithm?
I've been trying to implement the Schönhage–Strassen integer multiplication algorithm, but hit a stumbling block in the recursive step.
I have a value $x$ with $n$ bits and I want to compute $x^2 \...
12
votes
0answers
162 views
What is the curve of “search vs. insert”
Consider a collection of numbers (of arbitrary size), and an oracle that is able to accept two such numbers $a,b$ and answer queries of the form $a<b, a>b, a=b$ in constant time.
With this ...
5
votes
2answers
187 views
Solution/Hardness of the following (integer) budgeted problem?
I have no idea how to solve the following INTEGER problem or prove its hardness. Thanks for any help/comment/open discussion!
Assume there are $N$ startups. For each startup $i$, you can invest $x_i\...
2
votes
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 ...
5
votes
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....
0
votes
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 , ...
3
votes
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$, ...
0
votes
1answer
213 views
Paritioning a graph into clique and independent set
I am interested in the complexity of the following problems:
Input: an undirected graph $G = \langle V, E \rangle$
Query 1: is there a partition of $V$ into two a clique $C$ and an independent set $...
2
votes
1answer
328 views
Graph planarity testing via adjacency matrix
I have looked at several efficient graph planarity algorithms which
rely on computing and traversing DFS trees
(that add one vertex/edge/path at a time).
I am looking for graph planarity algorithms ...
7
votes
1answer
353 views
Complexity of “destroying” the graph's minimum spanning tree weight
Assume we have a connected input graph $G=(V,E)$ and a weight function $w:E\to\mathbb N$.
Denote by $w(G)$ the weight of a minimum spanning gree for a graph $G$. For this purpose, define $w(G')$ as $\...
5
votes
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 ...
2
votes
2answers
524 views
Subset product problem
We have $m$ list of integers $L_1,\dots,L_m$ and each list $L_i$ contains $n$ distinct integers $L_i(1),\dots,L_i(n)$.
You are given two integers $a$ and $b$ with $b<a$ and we know $n=O(2^{(\log b)...
4
votes
1answer
145 views
Maximum common subgraph of two planar graphs of bounded degree k
Given two planar graphs of bounded degree (i.e. each node has no more than D edges), I'd like to find their maximum common subgraph. I know that the more general problem applied to maximal planar ...
0
votes
0answers
68 views
Trade-off between number of spheres and wasted space in covering a 3d object by spheres
Consider the following optimization problem:
Input: a 3-dimensional "object" $O$.
Output: a covering of $O$ by a list of $k$ spheres $S_1, \ldots, S_k$ (given by their centers and radii) minimizing ...
7
votes
1answer
141 views
Label-disjoint paths in directed graphs
Checking if there are two edge-disjoint paths from $s$ to $t$
in a given undirected graph $G$ is in P via a standard solution based on maxflow.
I am interested in the complexity of the following ...
5
votes
3answers
445 views
Beating naive dynamic programming: examples similar to integer partitions?
Let $p(n)$ denote the number of partitions of $n\in\mathbb{N}$ (briefly, number of ways to split a pile of $n$ stones into $\geq1$ unordered nonempty parts). The classical dynamic programming ...
2
votes
0answers
159 views
Non-Linear Programming with \min operator in the constraint
Can the following non-linear program be solved in polynomial time? $c_{ij}$'s are constants and known. Each $c_{ij}$ is either -1 or 1.
\begin{align}
\text{maximize } &\sum_{i,j=1}^{m,n} c_{ij}...
5
votes
0answers
128 views
Vertex Disjoint Path Covers of Hypercube-Like Graphs
This is a followup question relating to an older question I posted, namely: https://cs.stackexchange.com/questions/55213/decomposing-the-n-cube-into-vertex-disjoint-paths.
Given a graph $G = (V, E)$ ...
2
votes
1answer
187 views
Is there any efficient algorithm for computing all semigroups of order n? [closed]
Is there any efficient algorithm for computing all semigroups of order n?
I found the following paper which solves a bit different problem.
Veronique Froidure and Jean-Eric Pin, "Algorithms for ...
6
votes
2answers
227 views
Parametrized complexity of the 2-Long Paths Problem
Consider the following problem:
Let $G=(V,E)$ be a graph, $s,t\in V$ vertices and $k\in\mathbb N$ an integer parameter. The 2-Long Paths Problems asks whether there exist two disjoint paths from $s$...
12
votes
3answers
719 views
Complexity of computing the parity of read-twice opposite CNF formula ($\oplus\text{Rtw-Opp-CNF}$)
In a read-twice opposite CNF formula each variable appears twice, once positive and once negative.
I'm interested in the $\oplus\text{Rtw-Opp-CNF}$ problem, which consists in computing the parity of ...
3
votes
3answers
166 views
Canonisation of boolean matrices under row and column permutations
Consider the equivalence relation $\sim$ on boolean matrices $A,B\in\{0,1\}^{m\times n}$ which is defined as follows:
$A\sim B$ :iff there are permutation matrices $P\in\{0,1\}^{n\times n}, Q\in\{0,1\...
1
vote
1answer
215 views
Packing sets to maximize overlap
For a set of sets $A$, let $\cup A := \cup_{S \in A} S$.
Consider the following problem:
Input:
a list of $m$ weights $w = (w_1, \ldots, w_m)$,
a list of $n$ distinct subsets $T = (S_1, \ldots, ...
2
votes
2answers
286 views
Finding a minimum tree which is isomorphic to a subtree of $T_1$ but not to a subtree of $T_2$
Consider the problem that receives two trees $T_1$, $T_2$, and asks to find a minimum size tree $T$ such that there exists a subtree of $T_1$ which is isomorphic to $T$, but there is no such ...
2
votes
1answer
144 views
Minimum weights needed to derandomize weight assignment by isolation lemma
Under isolation lemma if you have a graph with $2n$ vertices and $m$ edges an isolating weight assignment can be obtained by assigning edges weights randomly from $\{1,2,\dots,2m-1,2m\}$. A weight ...
6
votes
0answers
159 views
Machine learning algorithms on hypergrap models
Graphical models are a very useful tool with many applications,
whereby a joint distribution of a set of random variables is modeled
using only pairwise dependencies between the variables, and
two ...
5
votes
1answer
147 views
Does k-PATH admit a constant approximation?
In the $k$-PATH problem, we receive as input a graph $G$ and an integer $k$. The goal is to decide whether there exists a simple path of length $k$ in $G$.
A $\alpha$-approximation for $k$-PATH is an ...
10
votes
0answers
218 views
Does a polynomial-time algorithm for factoring product of two primes imply a polynomial-time algorithm for factoring in general?
Is it known if the existence of a polynomial-time algorithm for the promise problem of factoring of numbers with two prime factors implies that factoring in general has a polynomial-time algorithm?
1
vote
0answers
115 views
Computing $a^e \mod p^n$ Efficiently
It is well known that we can compute:
$$
a^e \mod m
$$
in $O(\log e \log ^2 m)$ bit operations (assuming multiplication $nm$ in $O(\log n \log m)$ time) via exponentiation by squaring. I am wondering ...
4
votes
1answer
468 views
Construction of a Global Isomorphism(permutation) for Graph Isomorphism using Local Isomorphism
Given two graphs $G, H$ (each has $n$ vertices). We, split $G$ into subgraphs $G_1, G_2... G_x$ (total $x$ vertex set). Similarly,assume $H$ has subgraphs $H_1, H_2... H_x$ (total $x$ vertex set).
...
4
votes
1answer
808 views
Maximizing a monotone supermodular function s.t. cardinality
I've tried to comb the literature and seen a lot of references to results that almost but don't quite seem to address this.
Question: Is it known to be true or is there a hardness result ...
-1
votes
2answers
3k views
Dynamic Programming vs Greedy Algorithm
In (Sniedovich 2006) "Dijkstra's algorithm revisited: the dynamic programming connexion", Sniedovich provides us another interpretation of Dijkstra's algorithm as a dynamic programming implementation. ...
6
votes
0answers
237 views
Most efficient inplace merge algorithms (stable and unstable)
I am currently researching the best algorithms available to achieve an inplace merge operation: consider two consecutive sorted arrays of size n and ...
8
votes
3answers
218 views
Showing that interval-sum queries on a binary array can not be done using linear space and constant time
You are given a $n$-sized binary array.
I want to show that no algorithm can do the following (or to be surprised and find out that such algorithms exist after all):
1) Pre-process the input array ...
8
votes
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 (...
