The 2024 Developer Survey results are live! See the results

# Questions tagged [ds.algorithms]

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

482 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
3k views

### Most efficient algorithm to search an unsorted array with a very precise data structure

(I apologize in advance if this question sounds a bit practical, but I suspect it might have an interesting theoretical aspect.) I have a (large) array of data, not completely sorted, but with which ...
• 145
29 views

### Analyze tags similar tags

I have a system for tagging articles. Each editor ads different tags to each piece of content. For example: for A: George Washington, first president for B: first president, Washington George for C: ...
• 101
71 views

### Sparse matrix front reducing

There is a symmetric sparse matrix with large front. This matrix is created from graph. Element with position $(i,j)$ is not zero if nodes $i$ and $j$ are connected. What algorithms can be used for ...
76 views

### Nonnegative Permanent and Ellipsoidal Method

Famously, Barahona gave an algorithm for Max Cut for Graphs without K5 complete as Subfactor Graph. This was based on the Ellipsoidal Method. Finding a Max Cut is the same for Bipartite Graphs as ...
• 1,578
93 views

### Questions on "Improved Sketching of Hamming Distance with Error Correcting" by Porat and Lipsky

What is the proof of lemma 4.3 in this paper? http://u.cs.biu.ac.il/~porately/papers/submission_24.pdf That is, how does it follow from 4.1 and 4.2? Also, why is the constant 8 necessary? How is it ...
• 11
208 views

### What machine learning algorithm solves this problem?

I want to solve this classification problem. Basically what I have is a sequence of feature vectors $\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_N$, and each feature vector is sequential in time. I ...
• 109
124 views

### Efficient update of the keys in associative container

I need to maintain a set $\langle(k_1, v_1), (k_2, v_2), \dots, (k_N, v_N)\rangle$ of key-value pairs subject to the following update operation. Given two keys $a < b$ and a "shift" value $C$ as ...
• 111
89 views

### Partitioning based on distribution

Having a set of numbers $S={s_i}$, I want to assign them to bins, $b_i$, such that the sum of items on bins follow a specific distribution. For two bins and uniform distribution, this problem is ...
• 199
124 views

### count number of i such that ( (a*i+b) mod p) mod k == l

How to determine the number of $i$'s as fast as possible such that $$1\le i \le L and ((ai+b)\mod p) \mod k = l$$ where $p$ is a prime number, $1\lt a, b\lt p-1$, and $l \lt k \lt L \lt p$. This ...
• 121
131 views

### Given a sequence find the shortest reg exp that generates it?

I'm looking for a way to find the smallest possible regular-expression that accepts a sequence. To make it interesting I don't want any stars(Kleene stars) and preferably no wildcards? For instance ...
170 views

### Finding a path between two given vertices that maximises the product of weights

I have a graph-problem which seems to be not very exotic but I do not know its proper name. As given in the heading I am looking for a path between two given vertices that maximises the product of ...
• 1
132 views

### Making algorithm comparison when algorithms use parameters

Say you have 3 algorithms, A B and C. You want to present a comparison of A B and C based on: Precompute overhead (say tree building etc that occurs prior to runtime) Runtime speed (say query ...
• 391
90 views

### Control optimization for a black box model

Computer science is not my major, hence my question is two folded : how is defined the problem I have (if I can name it, it will be easier for me to look for references) ? what kind algorithm would ...
• 101
346 views

### Divide-and-conquer approach for hierarchical clustering

I have a huge data set (33K), each represented as a bit-vector of 275-dimensions. Basically my data set can be represented as a $33000 \times 275$ matrix. I want to cluster these bit-vectors. I have ...
• 181
190 views

### Indexing over all possible functions in better than linear time

Given two sets X and Y, the number of functions mapping X to Y is $\vert Y\vert^{\vert X \vert}$. In particular I am interested in binary strings of relatively small length, e.g. 8. There are $2^8$ (...
• 835
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
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,538
508 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 ...
539 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 ...
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
939 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
415 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, ...
680 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 ...
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 ...
108 views

• 111
139 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 ...