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
Filter by
Sorted by
Tagged with
0 votes
0 answers

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 ...
ashim's user avatar
  • 135
0 votes
0 answers

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 ...
David Harris's user avatar
  • 3,488
0 votes
0 answers

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 ...
Michael Borgwardt's user avatar
0 votes
0 answers

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 ...
ilija's user avatar
  • 1
0 votes
0 answers

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 ...
Richard's user avatar
  • 307
0 votes
0 answers

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 ...
Legend's user avatar
  • 101
0 votes
0 answers

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, ...
anacrusis's user avatar
0 votes
1 answer

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 ...
daniel pehoushek's user avatar
-1 votes
1 answer

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 ...
user14389379's user avatar
-1 votes
1 answer

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\...
Sudipta Roy's user avatar
-1 votes
1 answer

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] ...
Jefferson Brian's user avatar
-1 votes
1 answer

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 ...
Eric Nunes's user avatar
-2 votes
1 answer

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 ...
gmr's user avatar
  • 121
-2 votes
1 answer

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 ...
wroscoe's user avatar
  • 111
-3 votes
1 answer

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 ...
claudio G's user avatar
-3 votes
1 answer

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 ...
alamar's user avatar
  • 95

6 7 8 9