Questions tagged [ds.algorithms]
Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.
2
votes
0answers
55 views
What is the competitive ratio of a $d$-way associative LRU cache?
In a caching problem, items arrive online, and the algorithm needs to decide which elements to keep in the cache. If the current item is not cached, we pay a penalty of $1$.
It is well known that for ...
0
votes
0answers
55 views
Coordinate descent in integer programing: when does it work?
Denote $N_i=\{0,1,\dots,\bar{n}_i\}$ and define $N=N_1\times \dots \times N_I$. I want to minimize a function $f:N\rightarrow \mathbb{R}$. It is very easy to minimize $f$ coordinate by coordinate so ...
-3
votes
0answers
50 views
Optimal algorithm to compare lines of different files without repetition [closed]
I have 1600 ASCII files with 1000 lines in each file. Each line has only one entry and is a floating point number e.g. 1.67923.
Let's denote the line1 of file1 with ...
0
votes
1answer
93 views
Permuting the columns of a 0/1-matrix to avoid short segments
Consider an $n \times n$ table with $n$ stars such that each row contains at most $\log n$ stars. The stars break each row into segments (continuous parts of a row without stars). Let's call a segment ...
5
votes
0answers
99 views
Evaluating addition chains
I hope this is a suitable place to ask this question.
An addition chain of size $n$ is a sequence $x_1, \dots, x_n$, where $x_1$ is fixed to 1 and $x_i = x_j + x_k$ for some $j,k < i$. I am ...
1
vote
0answers
30 views
PTAS for projective clustering : survey
$(k,j)$-projective clustering is the natural generalisation for k-clustering, in which one needs to find $k$ $j$-flats in $\mathbb{R}^d$ that minimizes the cost function as defined below:
Given a $j$-...
-4
votes
2answers
77 views
Is it possible to have a sorting algorithm that computes faster than QuickSort? [closed]
Given an unsorted array, QuickSort has to touch each source element it is trying to sort multiple times before it declares an array as sorted.
(notice how many times the 2 is touched [circled in red ...
5
votes
1answer
64 views
Pop desired elements on stacks of bounded capacity
Consider there are $k$ stacks containing a total of $n$ elements. Each element is either red or blue. We have complete knowledge of each element's location and color.
Only push and pop are allowed on ...
-1
votes
1answer
56 views
Formally prove that the loops of this sorting algorithm will terminate [closed]
Given is the sorting algorithm Bubblesort
...
5
votes
1answer
188 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 ...
2
votes
1answer
69 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 ...
1
vote
0answers
112 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"...
2
votes
1answer
96 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 ...
1
vote
0answers
20 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 ...
16
votes
1answer
1k 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?
6
votes
2answers
249 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 ...
8
votes
2answers
252 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$ ...
2
votes
0answers
79 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.
...
5
votes
0answers
105 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$ ...
10
votes
1answer
296 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 ...
3
votes
0answers
43 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.
...
8
votes
0answers
124 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 ...
14
votes
1answer
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 ...
1
vote
0answers
215 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 ...
5
votes
1answer
129 views
What does “hold uniformly” mean in the context of asymptotic analysis?
What does "hold uniformly" mean in the statement of Theorem 1.7 in
A Faster Subquadratic Algorithm for Finding Outlier Correlations? Here's the theorem text ("hold uniformly" is in the last line):
4
votes
1answer
137 views
Fast algorithm to find a maximum connected subgraph of k vertices
Given an undirected graph $G = (V, E)$ and a function $f: 2^V \to \mathbb{R}^+,$ where $2^V$ is the set of all subsets of $V$. Find a connected subgraph $T = (V_T, E_T)$ of k vertices such that $f(V_T)...
1
vote
0answers
55 views
Minimization of the maximal adjacent integer sums on a circle
Arrange $\{1,2,\cdots,n\}$ on a circle. What are the arrangements that minimize the maximal sum of all adjacent $k$ integers? For specific and low $n$'s it has been pointed out in math.stackexchange....
2
votes
1answer
88 views
What is the best approximation and exact algorithm for vertex cover on cubic graphs?
"Best" = best performing in terms of run-time for exact algorithm and approximation ratio for an approximation algorithm.
6
votes
1answer
142 views
How to solve this generalization of binary search?
Let $f:\{1,\ldots,n\}$ be a monotonically non-decreasing function.
Consider, for some unknown threshold $1\le T\le n$, a threshold function
$$g(x)= \begin{cases}
0&\text{x<T}\\
1&\text{...
3
votes
1answer
47 views
Complexity of distributively verifying that the diameter is small
Consider a graph $G=(V,E)$ and an integer parameter $k$.
I'm interested in the round complexity, in the CONGEST model, of checking if the diameter of the graph is "much larger" or "much smaller" than ...
4
votes
0answers
64 views
2-hop distributed coloring in the CONGEST model
Consider a graph $G=(V,E)$ and let $d(u,v)$ denote the distance between $u$ and $v$ in $G$.
A 2-hop coloring is a mapping $c:V\to{1,\ldots, C}$ ($C$ is the number of colors) such that $d(u,v)\le 2 \...
2
votes
0answers
200 views
Career advice needed: Switching from theoretical CS to pure math
I couldn't think of a better forum to ask this question. I am a first year cs graduate student. I couldn't really pursue theoretical cs during my undergrad, but as part of our PhD qualifiers, i had to ...
2
votes
1answer
228 views
Existence of an algorithm
I need to show that there exists a polynomial time algorithm that inputs a deterministic automata $A$, and decides if $A$ accepts a word w if and only if it also accepts any word obtained by permuting ...
4
votes
0answers
59 views
Smoothed analysis to compare algorithms
Has there been any research using smoothed analysis to compare approximation algorithms that have the same approximation ratio?
Any research that compares algorithms using smoothed analysis would be ...
3
votes
1answer
46 views
Algorithm for finding smallest set and instanciation for a given constraint system
I have a system of constraints described by a set of clauses of the form
$x_1 \neq x_2 \lor \dots \lor x_{i-1} \neq x_i$, for instance:
...
21
votes
4answers
787 views
Problems that are counter-intuitively solvable in practice?
Recently, I went through the painful fun experience of informally explaining the concept of computational complexity to a young talented self-taught programmer, who never took a formal course in ...
0
votes
1answer
96 views
How can algorithms with nested combinatorial searches be quasi-linear?
I've come across algorithms similar to the one below, where a demanding step is performed, which should have at least polynomial complexity, yet the whole algorithm is deemed quasi-linear without ...
0
votes
0answers
63 views
Algorithm for solving majority of a group of k hidden elements
You may already be familiar with algorithms to compute the majority using multiple queries. The way these problems work is that you are given a bin of $n$ marbles of binary colors, whose colors you ...
4
votes
1answer
132 views
Anti bin packing
I have a (practically) unlimited amount of McDonald's coupons that I can use only if I shop for at least 1 money.
Thus I want to partition my family's meal into as many parts as possible that all ...
-1
votes
1answer
29 views
Algorithm in logarithmic time that finds a number with the help of a subarray that is not in the array
The question is as follows.
Given: A sorted array A of n integers where A[n − 1] − A[0] ≥ n.
Asked: Give an algorithm and the invariant of the algorithm that finds a number between A[0] and A[n - 1] ...
9
votes
4answers
230 views
W[1]-hard problems with FPT time approximation algorithms
I'm looking for problems that are hard to solve in FPT time but has an approximation algorithm. That is, problems that are:
R1. W[1]-hard.
R2. Admit a (preferably constant) approximation algorithm ...
5
votes
1answer
151 views
“Smallest” path that visits a given set of vertices
I use smallest rather than shortest to distinguish between the shortest path problem. The problem is as follows:
Given a directed graph $G=(V,E)$, two vertices $s$ and $t$, and a set of $p$ ...
1
vote
1answer
86 views
What is the best and easy (regarding implementation) way of computing three edge independent trees in a 3-connected graph?
I am searching for an implementation of an algorithm that constructs three edge independent spanning trees from a 3-edge connected graph. Any response will be appreciated. Thanks in Advance.
3
votes
1answer
121 views
On complexity of linear programming with quadratic equality/inequality constraints?
Feasibility test in Linear programming is in $P$ and in convex quadratic programming is in $P$. What is the maximum $k$ such that $n$-variable $m=poly(n)$ linear constraint feasibility test with $k$ ...
3
votes
0answers
126 views
Fast way of getting a matrix of sums
We are given an array of variables $A$, along with a matrix $M$. The elements of the matrix $M$ are composed of sums of the variables in $A$. We are allowed to pre-process $A$ in order to find a ...
8
votes
2answers
366 views
Counterexample to max-flow algorithms with irrational weights?
It is known that Ford-Fulkerson or Edmonds-Karp with the fat pipe heuristic (two algorithms for max-flow) need not halt if some of the weights are irrational. In fact, they can even converge on the ...
0
votes
0answers
49 views
Metric 1-Center in l-infinity norm (when dimension is part of the input)
Consider the following problem,
Input: A number $d>0$, $X \subseteq \mathbb{R}^d$.
Output: A center $c\in \mathbb{R}^d$ s.t $\max_{x \in X} \lVert x - c\rVert_p $ is minimized.
This is the 1-...
1
vote
1answer
54 views
Does the following 2-rounds distributed algorithm approximates a maximal matching well?
Let $G$ be an undirected graph.
I'm looking for a two-rounds distributed algorithm that matches as many vertex pairs as possible.
Consider the following protocol for vertex $v$.
Use a fair coin to ...
1
vote
0answers
113 views
How to represent boolean tree + algorithm as a mathematical formula
In programming say you have a boolean tree like this:
...
11
votes
1answer
1k views
Examples of algorithms and proofs that seem correct, but aren't
In my intro to programming course, we're learning about the Initialization-Maintenance-Termination method of proving an algorithm does what we expect it to. But we've only had to prove that an ...
