Questions tagged [ds.algorithms]
Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.
1,814
questions
4
votes
0
answers
91
views
$\log^\star n$ is somewhat common in runtimes. Does the superroot ever make an appearance?
Many algorithms and data structures have iterated logarithms ($\log^\star n$) in their runtimes. This function is the discrete inverse of tetration, in that
$$\log_a^\star (a \uparrow \uparrow b) = b$$...
- 2,121
10
votes
0
answers
142
views
Fine-grained complexity for game-type problems
My specific question is the following. Consider the following problem that I call Strange-TQBF:
there is a Boolean function $f(x_1, \ldots, x_n)$ and two players Alice and Bob.
They take turns ...
- 1,973
57
votes
10
answers
18k
views
Recent advances in computer science since 2010?
Since I left school (early 2010s) a couple of recently developed techniques were widely adopted by the industry. For example,
Asymmetric numeral systems for compression (e.g. Ubuntu ships with ...
- 651
1
vote
0
answers
37
views
Understanding David Pisinger's balanced algorithm for the subset-sum problem with bounded weights
I'm trying to understand David Pisinger's balanced algorithm for the subset-sum problem with bounded weights, which can be found on page 5 of his paper Linear Time Algorithms for Knapsack Problems ...
- 111
0
votes
0
answers
46
views
Deamortization of basic COLA (Cache oblivious lookahead array)
I am reading the paper titled Cache Oblivious Streaming B-trees. I am trying to understand the deamortization technique used for basic COLA.
The paper says that for every level k, for deamortization, ...
6
votes
1
answer
384
views
Given real numbers $x_1,...,x_n$ , find the maximum of $ \frac{(x_j-x_i)^2}{j-i}$
Can it be done in linear or at least subquadratic time?
- 13.6k
2
votes
0
answers
36
views
Generalization of Binary Decomposition to Polynomials?
Given an integer $x\in\mathbb{Z}$, we can write its binary decomposition (and more generally base $B$ for $B\in\mathbb{Z}$, $B>1$) as
$$x = \sum_{i=0} x_i B^i,$$
where $x_i \in \mathbb{Z}/B\mathbb{...
- 918
20
votes
10
answers
3k
views
What are examples of recent relatively simple 'toolbox algorithms'?
Taking an introduction to algorithms course, one encounters quicksort, minimal spanning tree, Dijkstra, Ford–Fulkerson algorithm etc.
There are also several relatively standard data structures, such ...
2
votes
0
answers
42
views
Effective algorithms for finite lattices of (higher-order) monotonous functions?
I am looking for references on effective algorithms on finite lattices or posets, and in particular on lattices of monotonous functions between two lattices, with higher-order structure -- monotonous ...
- 2,040
6
votes
1
answer
342
views
Condition Number dependent algorithms for matrix operations
Using the Conjugate gradient method we can solve a linear system $Ax=b$, where $A\in\mathbb R^{n\times n}$ in time $O(n^2 \sqrt{\kappa})$, where $\kappa=\frac{\sigma_\mathrm{max}(A)}{\sigma_\mathrm{...
- 958
-1
votes
1
answer
86
views
How is memory being used by an algorithm, to define its space complexity? [closed]
In computation we always talk about the time and space complexity of a given algorithm. The time complexity describes how long an algorithm takes in relation to the quantity of input it receives. ...
- 99
0
votes
0
answers
58
views
kd-tree optimality for orthogonal range search
It is known that a kd-tree can be constructed for $n$ points ($k$-dimensional) in $O(n \log n)$ time and searching of any axis-aligned hyperrectangle can be done in time $O(n^{1-1/k} + out)$ time ...
- 1,177
1
vote
0
answers
45
views
Compute Fourier coefficients from Single Fourier coefficient and initial vector?
I have some vector $\vec v\in\mathbb{Z}_q^n$, and would like to obtain $n$ vectors $\vec f_0,\dots, \vec f_{n-1}$ where $\vec f_i = (\mathcal{F}(\vec v)_i,0,\dots,0)$, i.e. each vector is a single ...
- 918
1
vote
1
answer
46
views
What is known about the complexity of Network Diversion?
In the Network Diversion problem, we are given an undirected graph $G$ on $n$ vertices, with specified nodes $s$ and $t$ and specified edge $e$, and a positive integer $k$, and are tasked with ...
- 576
5
votes
1
answer
147
views
Finding $k \times k$ rectangle in a matrix with maximum sum
Given an $n \times n$ matrix $A$ with $0-1$ entries, I want to maximize $\sum\limits_{i \in I, j \in J} a_{ij}$ subject to $|I| = |J| = k.$
I expect the problem to be NP-hard, so I want a polynomial ...
- 151
0
votes
0
answers
42
views
Speed networking algorithm
I have 40 people and 10 tables that can accommodate 4 people at a time. The task is to make sure that every person seats with every other person at the same table exactly once, that is every person ...
- 101
4
votes
1
answer
85
views
Independent set queries with preprocessing
Suppose we have a sparse undirected graph $G = (V, E)$ with $|E| = O(|V|)$, and we want to process it and then answer queries of the following type: given a set $A$, is it an independent set in the ...
- 464
1
vote
1
answer
47
views
Maximizing merges with restrictions
Note: The input to this problem has type List[List[List[Pair[int, int]]]]. Since it's tricky to visualize that, I'll use terminology from the original problem, which comes from the optimization of ...
- 13
3
votes
0
answers
82
views
Is the Moser-Tardos algorithm used in any real-world applications?
The Moser-Tardos algorithm can be used to construct algorithms for certain combinatorial problems. However, I'm curious about whether this algorithm is utilized in real-world systems (a SAT solver, ...
- 31
0
votes
0
answers
87
views
Consequences of early-exiting BFS after reaching the target node in Dinic's algorithm
In a typical exposition (or implementation), Dinic's algorithm executes a full BFS traversal of the residual graph starting from the source node in each phase. If the target node is unreachable, the ...
- 195
-3
votes
1
answer
134
views
help me understand what semiprime factorizations are worth
Based on a response I received in another post, I would like to ask this question.
Are there semiprimes that are not very interesting in terms of research and are not worth factoring?
Are only the RSA ...
0
votes
1
answer
74
views
Exchange cards with sum requirement
Given are positive integers $a_1,\dots,a_{2k},b_1,\dots,b_{2k},S$ such that $\sum_{i=1}^ka_i = \sum_{i=k+1}^{2k}a_i = S$ and $\sum_{i=1}^kb_i = \sum_{i=k+1}^{2k}b_i = S$. There are $2k$ cards, card $i$...
- 123
1
vote
0
answers
42
views
What are the fastest known parameterized algorithms for Grid Tiling?
Let $k$ and $n$ denote positive integers.
In the $k$-GridTiling problem, for every pair of indices $(i,j)\in \{1, \dots, k\}^2$ we get a subset $S_{ij}\subseteq \{1, \dots, n\}^2$ of pairs of the ...
- 576
-3
votes
2
answers
184
views
pq factorization
If I tried to factor a semiprime as the product of the two prime factors given below in the form pq on a home computer would I be successful?
p=(2^1024-1)+644 prime factor
q=(2^1028-1)+188 prime ...
0
votes
0
answers
45
views
What Data Structure storing points in space for fast lookup of stored points "near" a query point?
In NLP a common problem is that you have vector embeddings of large vocabularies, and you do manipulations on these vector embeddings to compute some result vector, and then you want to find which ...
- 101
6
votes
1
answer
573
views
Find odd-ranked numbers from a list
From a list of $n$ distinct numbers, I want to find the set consisting of all odd-ranked numbers (1st, 3rd, 5th, ...). How many comparison queries do I need?
I could sort the whole list using $O(n\log ...
- 123
3
votes
0
answers
98
views
Why do some problems seem to admit a richer family of algorithms than others?
Let's take integer multiplication and comparison sorting as examples. Despite being roughly comparable in terms of computational complexity, if we look at the set of algorithms which solve each ...
- 803
1
vote
0
answers
56
views
Why does splitting $n$ bit integers into chunks of size $\log(n)$ specifically, help in multiplying them
In integer multiplication algorithms such as the Schonhage-Strassen algorithm (and the recently described Harvey and van der Hoeven algorithm), integers of size $n$ are reduced to polynomials with ...
0
votes
0
answers
47
views
Complexity of XOR-Knapsack
Edit: Actually I should have been more careful. Maybe the optimal way to solve this is to approach it as a series of $k'-$XOR sum problems (Generalized birthday due to Wagner) for increasing $k'.$ And ...
- 2,070
2
votes
0
answers
102
views
Is there a calculus or formalism for measuring set relations between algorithm outputs?
I'm asking this question from a fairly naive position, so apologies in advance, etc.
I'm aware of the Bird-Meertens formalism for equational reasoning about algorithms but what I'm really interested ...
- 121
0
votes
1
answer
197
views
Construction of a collection of subsets of $\{1,2,\ldots,n\}$ with certain properties
Let $n$ be a large positive integer. Given a collection $\mathfrak S$ of subsets of $[n] := \{1,2,\ldots,n\}$, and a vector $z=(z_1,\ldots,z_n)\in \{\pm 1\}^n$, define
$$
f_{\mathfrak S}(z) := \sum_{\...
- 291
3
votes
2
answers
160
views
Worst-case complexity of computing a certain non-standard dot product + algorithms realizing this complexity
Let $n$ be a large positive integer. Give a nonempty collection $\mathcal S$ of subsets of $[n] := \{1,2,\ldots,n\}$, define an inner-product on $\mathbb R^n$ by
\begin{eqnarray}
\langle x,y\rangle_{\...
- 291
2
votes
0
answers
66
views
Confusion with the definition of Online Set Cover
I am confused on a technicality on how Online Set Cover is defined.
One way to define it is: We are given a collection of sets $\mathcal{S}$ upfront, and in each time-step an element arrives to be ...
- 607
1
vote
1
answer
55
views
$k-$median problem and filtering technique Lin and Vitter
I read a paper from Tardos et al. about $k-$medians in metric space problem:
Given $N$ as set of points in metric space with distance function $c_{ij}$ for each $i,j\in N$, demand $d_i$ for each point ...
- 113
0
votes
0
answers
76
views
Why does the prefix sum operation require its binary operator to be associative?
Prefix Sums and Their Applications states that
The all-prefix-sums operation takes a binary associative operator ⊕, and
an ordered set of n elements...
Why is associativity a required property of ...
0
votes
1
answer
76
views
An inequality about median of points in higher dimensions
Let $S$ be a set of points in $\mathbf{R^d}$ and let $m$ be the median of this set of points, i.e. $\sum_{x \in S} || x - y||$ is minimized when we have $y=m$. Now let $z$ be an arbitrary point in $\...
- 1
2
votes
1
answer
184
views
On parallel complexity of modular inverse
Modular inverse is not known to be in $NC$ either.
How about the cases where the modulus is just $2^n +i$ where $i\in\{-1,0,1\}$?
Are these cases in $NC$?
Are there any non-trivial classes of moduli ...
- 12.8k
0
votes
0
answers
65
views
Maintaining a $K_{3,3}$-minor-free graph
Suppose we are given that an undirected, connected graph $G$ is $K_{3,3}$-minor-free.
Let $a,b\in V(G)$ be non-adjacent vertices.
Under what conditions is the graph that results by adding the edge $(a,...
- 95
0
votes
1
answer
74
views
Spectral sparsification of graphs with negative edge weights
I am reading the following well-known paper on spectral sparsification of weighted graphs: https://arxiv.org/pdf/0808.4134.pdf. Page 2 contains most of the definitions relevant to this question.
It is ...
- 1
12
votes
1
answer
2k
views
Is the 3-coloring problem NP-hard on graphs of maximal degree 3?
Consider the 3-coloring problem: given an undirected graph $G = (V, E)$, decide if there is a 3-coloring of $G$, i.e., a function $f$ from $G$ to $\{1, 2, 3\}$ such that there is no edge $\{u, v\}$ in ...
- 8,896
1
vote
0
answers
103
views
On the borderline between natural and artificial problems
While there is no formal definition of what constitutes a natural algorithmic problem,
in most cases there is pretty good consensus whether a specific problem is natural or artificial. Natural usually ...
- 11.3k
1
vote
1
answer
68
views
Prefix free code unbalancing 0 and 1 bits
We have a long message $m$ to encode. The message is composed of a set of symbols $\{s_i\}$. Let $p_i$ denote the number of appearance of $s_i$ in $m$. We seek to find a prefix-free code for each $s_i$...
- 113
2
votes
0
answers
43
views
Algorithms for parametric matroid optimization
Let $M$ be a rank $r$ matroid with basis set $\mathcal{B}$ and an independence oracle. Given a linear function $w_e$ on each element $e$ of the matroid, we want to find the minimum weight basis for ...
- 4,367
0
votes
1
answer
228
views
Where should I start?
I am a college student majoring in Computer Science, before my college, I played OI for about 2 years. I want to learn tcs cuz I like it. Among the many tcs fields, I am most interested in algorithms. ...
- 101
0
votes
0
answers
57
views
Uniformly redistributing items across bins. What problem is this?
I'm trying to find reading material on a particular problem I'm interested in, but I don't know the terms to search.
Problem assumptions/definitions:
We have finite number of items I with weights [0, ...
- 101
2
votes
0
answers
76
views
Has there been any research on faster tensor inner products?
Matrix multiplication is a well studied problem which is recently back in the news due to deepmind.
That got me wondering has anyone looked at the more general problem of faster tensor multiplication? ...
- 369
0
votes
0
answers
39
views
Computing a feasible exchange bijection between bases of a matroid
A base-orderable matroid is a matroid in which, for any two bases $A$ and $B$, there exists a feasible exchange bijection, that is, a bijection $f: A\to B$ such that, for all $a\in A$, both $A-a+f(a)$ ...
- 2,086
5
votes
1
answer
219
views
Graph coloring with limit on number of times a color is used
Are there any results on coloring a graph using a limited number of each color. In other words, the decision problem would be: given a list of colors $C = (c_1, \dots, c_k)$ where each color $c_i$ is ...
- 53
0
votes
0
answers
80
views
Examples of Gaussian randomized algorithms
I've been thinking about algorithms of the form where a quantity $c$ can be viewed as the expectation of some estimator (random variable) $X$ and the expectation is taken over some multivariate ...
- 111
-1
votes
1
answer
51
views
Flow of value lower bounded by $X$
In a given network, is it possible to find a flow of value that is lower bounded by $X$ in near-linear time, $O((m + n) \text{poly}\log n)$? I do not want to find the exact maximum flow just whether ...
