# 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
Filter by
Sorted by
Tagged with
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$$...
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 ...
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 ...
1 vote
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 ...
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, ...
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?
36 views

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. ...
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 vote
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 ...
1 vote
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 ...
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 ...
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 ...
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 ...
1 vote
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 ...
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, ...
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 ...
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 ...
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$...
1 vote
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 ...
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 ...
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 ...
573 views

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 ... 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 ... 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 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 ... 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_{\... 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_{\... 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 ... 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 ... 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$\...
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 ...