Questions tagged [ds.algorithms]
Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.
466
questions with no upvoted or accepted answers
0
votes
0
answers
536
views
suffix tree: about Ukkonen's algorithm
I have specific question about suffix trees. I am reading the book Algorithms on strings_trees and sequence.
I cannot understand details of Ukkonen's algorithm for constructing suffix trees. Why ...
- 135
0
votes
0
answers
133
views
Approximation algorithms based on relaxing a feasible to infeasible solution?
A lot of approximation algorithms are based on relaxation. The way it usually works is this. You take the original problem and relax it some large class of efficiently solvable problem (e.g. relax an ...
- 3,488
0
votes
0
answers
500
views
How to detect dead ends on a board / in a graph?
Given a (2D) board of quadratic cells (movement allowed between 4-neighbours), many of which are blocked, and given a certain starting position, how can I efficiently detect dead ends, i.e. regions of ...
0
votes
0
answers
528
views
Predecessor matrix storing
What is the time complexity of computing betweenness centrality if we are given the shortest path predecessor matrix of a graph?
Predecessor matrix cells look like this:
If node $i$ and node $j$ are ...
- 1
0
votes
0
answers
128
views
On algorithms that minimizes maximal load of bins
There are $n$ bins and $m$ balls, $b_i$ where $0<i\le m$. Balls are with different weights $w_i$ and have dependency between them. ball $b_1$ depends on $b_2$, $b_2$ depends on $b_3$, and so on. It ...
- 307
0
votes
0
answers
920
views
Understanding the HRU Model (Protection in Operating Systems)
As of now I am feeling terrible because I have spent the past 10 hours trying to understand this paper titled "Protection in Operating Systems" by Harrison, Ruzzo and Ullman. At this point, any help ...
- 101
0
votes
0
answers
407
views
Hardness of Happynet problem
I have been recently researching Happynet in terms of approximation and I have found out that there is a little interest in this topic.
What's the reason for this?
Are there any related problems, ...
- 39
0
votes
1
answer
673
views
Is the running time of Boyer-Moore linear?
With pattern length $M$, text length $N$, and alphabet $\Sigma$,
is the asymptotic running-time of Boyer-Moore $O(N/|\Sigma|)$
(even when $M$ grows larger than $|\Sigma|$)?
Are there any sublinear ...
-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 ...
-1
votes
1
answer
108
views
Required sample size to hit certain subset of a ground set
Suppose $X$ is a set of $n$ points in $\mathbb{R}^d$ and $N_1,\cdots,N_k$ are k disjoint (unknown)subsets of $X$. There is a probability distribution $\phi$ on $X$ defined as $\phi(p) = \frac{\lvert\...
- 265
-1
votes
1
answer
36
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] ...
-1
votes
1
answer
2k
views
Time complexity analysis of random forest and k-means?
I am working with random forest for a supervised classification problem, and I am using the k-means clustering algorithm to split the data at each node, where
$n$ is the number of points,
$K$ is ...
-2
votes
1
answer
204
views
What are some natural problems that we can quickly find a solution to using massive parallelism but not a canonical solution?
For many problems, more than one output is acceptable. For instance, the problem of finding an assignment that satisfies a boolean formula. If randomness buys us something then it could be that it ...
- 121
-2
votes
1
answer
291
views
Find all items which are subsets of an item
I have a problem that I think should have been studied. I am looking for algorithms for it.
Each item is a set of key-value pairs.
Let $x$ be an item and $F$ be a set of items.
Each key and each ...
- 111
-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 ...
-3
votes
1
answer
159
views
Continous work distribution algorithm with failover
Imagine there's a system where there's N workers and M units of work, for example, N ≤ 64, M = 256.
Is there an algorithm that ...
- 95