Questions tagged [ds.algorithms]
Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.
1,886 questions
5
votes
0
answers
218
views
Hidden constant in complexity of the AKS primality test
In the AKS paper, the authors based on the Lemma
There exist constants $c > 0$ and $n_0$ such that, for all $x\ge n_0$: $$\bigl|\{q \mid \text{$q$ is prime, $q\le x$ and $P(q − 1) > q^{2/3}$}\}\...
- 151
2
votes
0
answers
64
views
Cache-Oblivious large integer multiplication
Given two $n$-bit integers $a$ and $b$ how many memory transfers are needed to compute $ab$?
Since $ab$ can be computed in $O(n \log n)$ time, this is an upper bound on the number of memory transfers. ...
- 161
4
votes
1
answer
244
views
Matrix classes that admit quadratic time squaring
Matrix squaring for general matrices is as hard as matrix multiplication because of the $2n\times2n$ matrix $\begin{pmatrix}0&A\\B&0\end{pmatrix}$ (as said by Ryan Williams here). So the ...
- 51
2
votes
1
answer
192
views
Allocating values in Boolean expression
Let there be a set of slots $a_1, a_2, ..., a_m$, a set of items $b_1, b_2, ..., b_n$, and a function $f$ such that $f(a_i, b_j)$ returns whether item $b_j$ fits into slot $a_i$. Additionally, let ...
- 123
1
vote
1
answer
125
views
Problem on a Directed Graph subcase of load time scheduling
I have the following graph optimization problem. In a directed graph G, each node $v$
is assigned a number $n(v)$ which is initially 0. At any time, I can make a move to assign the number $ max \{ n(...
- 358
2
votes
1
answer
211
views
Integer multiplication with limited space
When multiplying two $n$-bit integers, it seems like we have to compute and store intermediate results. For example, in the schoolbook algorithm, we typically have to compute and sum $O(n^2)$ partial ...
- 1,074
2
votes
0
answers
62
views
Bounds for Offline Dominance Counting in the Semigroup Model
I am looking for state-of-the-art results on the runtime bounds of offline dominance counting, specifically in the semigroup model.
The problem, for a semigroup $(G, \oplus)$ and points $P$, e.g., in $...
4
votes
0
answers
163
views
Trying to find source for there is no PTAS for binary SCS
I'm trying to find a proof that there is no PTAS for binary Shortest common supersequence.
I know there is a paper here P. Bonizzoni, M. Duella and G. Mauri. Approximation complexity of longest common ...
- 358
8
votes
0
answers
220
views
Is there a theory of approximate dynamic programming?
By which I mean for problems which can be solved perfectly by dynamic programming but instead of computing all necessary subproblems you only compute a subset and each entry of the DP table that you ...
- 358
0
votes
1
answer
163
views
Truncated arithmetic with promise
Problem: Top two bits of arithmetic expression $ab+cd$ with promise
Input: Four $n$-bit integers $a, b, c, d$
Promise: $ab+cd<2^{2n}$ or $ab+cd \geq 2^{2n} + 2^{2n-1}$
Output: Whether $ab+cd<2^{...
- 1,074
1
vote
1
answer
113
views
A theoretical model for a non-standard data type with real-world applications
I'm exploring a theoretical model for a data type that doesn't fit into conventional computer science paradigms. I'm not a computer scientist, so I'm looking for guidance on whether such a data type ...
- 11
0
votes
0
answers
59
views
What data structure minimizes the amount of combine operation in point updates and range queries (and having the smallest leading constant)?
Suppose you have an array $a$ of $n$ elements in a set $X$, and an associative binary operation $\circ \ \colon X \times X \rightarrow X$, that can be evaluated in constant time, but is costly (e.g. $...
- 1
4
votes
1
answer
300
views
Fast integer multiplication
By "fast" here I mean time $O(n)$ for two $n$-bit integers.
What classes of integers admit fast multiplication?
For example, powers of 2 admit fast multiplication, since for these integers ...
- 1,074
5
votes
1
answer
257
views
Binary search with uneven comparison cost?
I have a problem where I need to perform binary search (search a sorted list), but verifying that an index is larger than my target has a much greater runtime cost than verifying that it is lower.
Is ...
- 151
0
votes
1
answer
403
views
I have written a preprint about a novel algorithm to find MST, I think it can be a replacement for Kruskal's algorithm; Can any anyone review it?
I am a recent CS Grad, and I wrote a preprint about a algorithm for MST, with time complexity O(E+VlogV) and Ω(E) in the worst and base cases, respectively; given sorted edges. I feel like it is a ...
