# Questions tagged [ds.algorithms]

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

1,608 questions
Filter by
Sorted by
Tagged with
231 views

### Evaluation of an arithmetic formula where the time depends on the length of the arguments of gates

Let $(X,+,\cdot)$ be a commutative ring. Let $|\cdot|\colon X\to \mathbb{N}$ be a function that satisfies $|x+y|\leq |x|+|y|$ and $|xy|\leq |x|+|y|$. We call the function length, and length is always ...
89 views

### Find shortest prefix to generate original string by overlapping

Given a string $S$, I want to find the prefix string $P$ of shortest length, such that the original string $S$ can be generated by concatenating copies of $P$ (where overlapping is allowed). For ...
131 views

### How to write algorithms?

Reading research articles in theoretical computer science, I noticed that people often describe their algorithms in an enumerative way (i.e., they enumerate the steps of their algorithm and use "go to"...
102 views

### Minimization version of matrix p-norms?

I considered a minimization version of matrix p-norms, defined for a matrix $A$ by $$f_p(A)= \min_{x\neq 0} \frac{||Ax||_p}{||x||_p}.$$ Notice that $f_p(A) = 0$ if and only if $A$'s columns are ...
64 views

### What is the maximal load of a “latency-bounded” Cuckoo Hash?

Cuckoo Hashing is a method for storing key-value stores (or just a set of keys) with a constant worst-case lookup time. They use two hash functions $h_1,h_2:\mathbb K\to [n]$, where $\mathbb K$ is ...
2k views

### Algorithm whose running time depends on P vs. NP

Is there a known, explicit example of an algorithm with the property such that if $P\neq NP$ then this algorithm doesn't run in polynomial time and if $P=NP$ then it does run in polynomial time?
261 views

### Algorithm for identifying unprovable statements

I understand that this may depend on the specific set of axioms, but is there a general way (algorithm) for automatically detecting unprovable statements within a set of axioms? For example: If there ...
383 views

### Non-Orthogonal Vectors Problem

Consider the following problems: Orthogonal Vectors Problem Input: A set $S$ of $n$ Boolean vectors each of length $d$. Question: Do there exist distinct vectors $v_1$ and $v_2 \in S$ ...
85 views

### On the goal of learned clause database reduction in CDCL SAT solvers

Modern SAT solvers frequently reduce the size of their learned clause database in order to keep its size as manageable as possible. This has as effect not to slow down the speed of unit propagations. ...
109 views

### Lower bound for enumerating k closest pair of points

Consider 1 dimensional points $x_1, \dots x_n, x_i \in \mathbb{R}$ where the distance between any two points is defined as $d(x_i, x_j) = \vert x_i - x_j \vert$. The goal is to enumerate all $n^2$ ...
320 views

### Sorting with an average of $\mathrm{lg}(n!)+o(n)$ comparisons

Is there a comparison-based sorting algorithm that uses an average of $\mathrm{lg}(n!)+o(n)$ comparisons? Existence of a worst-case $\mathrm{lg}(n!)+o(n)$ comparison algorithm is an open problem, but ...
51 views

### Lower bound for reversing a list using queues

How do you prove (or disprove) that a list of length $n$ cannot be reversed in time $o(n \log n)$ using $O(1)$ queues? Each queue is FIFO. Time refers to the number of operations on the queues. ...
128 views

### Finding $n$ many different primes efficiently

I want to find $n$ many different primes on RAM. I can find $O(\frac{n}{\log n})$ many primes in the interval $1$ to $n$ in $O(n)$ running time. A brute force way is to find $O(\frac{n}{\log n})$ many ...
1k views

### Deciding whether an interval contains a prime number

What is the complexity of deciding whether an interval of the natural numbers contains a prime? A variant of the Sieve of Eratosthenes gives an $\tilde O(L)$ algorithm, where $L$ is the length of the ...
223 views

### Impagliazzo lemma, unclear detail in its proof

In Arora-Barak's book on page 378 in the proof of Impagliazzo's Hard Core lemma why did they choose the number 50 in this line: Set $t = \frac{50n}{\epsilon^2}$ ? How this choice then yields the size ...