Questions tagged [algorithms]
An algorithm is a sequence of well-defined steps that defines an abstract solution to a problem. Use this tag when your issue is related to design and analysis of algorithms.
10,997
questions
0
votes
0
answers
29
views
Creating a PRNG to replicate the LIbrary of Babel
I had asked a question here about this before but it had a lot of vagueness to it, so I'll rephrase the entire thing.
I'm trying to create a PRNG that would replicate Borge's Library of Babel, i.e. ...
1
vote
1
answer
51
views
How to schedule ELO-based, fair games with n players and dynamic teams?
The setting is the following: There are n players that want to compete in a specific game over the course of an event. A game is played between 2 teams of 2 players each (so a 2v2). Each player as a ...
- 13
0
votes
1
answer
41
views
Minimum number of skips needed for shortest path
In a directed, weighted graph with non-negative weights we are asked to find a path from a starting node s to node t that weights $\leq W$. In our given graph there is no such path but we have the ...
- 37
0
votes
0
answers
23
views
PRNG with output of constant length
forgive me if my question is vaguely phrased.
I’m fishing around for a PRNG algorithm which generates numbers of a constant length, regardless of the seed.
I tried experimenting with a LCG but ...
2
votes
1
answer
94
views
Dynamic programming: optimal order to answer questions to score the maximum expected marks
You have $n$ questions in an exam. Question $i$ is answered correctly with probability $p_i > 0$. If question $i$ is answered correctly, you get $R_i$ marks. You can choose to answer
the questions ...
- 23
0
votes
0
answers
29
views
Given $a_1,\dots,a_n$ and $b_1,\dots,b_n$, find all $(a_i, b_j)$ on some condition
It is given $a_1,\dots,a_n$ and $b_1,\dots,b_m$. Let $S_i$ ($1\leq i\leq n$) be the set of indices of $b$ so that it could be paired by $a_i$ (For example, if $S_3 = \{1, 3, 5\}$, then $(a_3,b_1),(a_3,...
- 1
14
votes
2
answers
3k
views
Ackermann Function without Recursion or Stack
I have been studying the necessity of a WHILE loop when defining the Ackermann Function.
I am looking to write a program to compute the Ackermann function in a high level language such as Python or ...
- 143
0
votes
0
answers
31
views
How to determine the width and depth of a count-min sketch, depending of the unique elements inside
Follow up this question:
What is the correct way to determine the width and depth of a count-min sketch?
Let suppose, correct way is following:
...
- 101
2
votes
0
answers
17
views
Finding Large Subset of Variables Approximately Equal, Low-Cost with Neural Network
I was reading David J.C. MacKay's Information Theory, Inference and Learning Algorithms(pdf available in the link), and in section 16.4 of Chapter 16: Message Passing, he writes about how only ...
- 21
0
votes
0
answers
11
views
Generating a network with a certain value of correlation between node attributes
I have a graph $\mathcal{G}$, and a probability distribution, $f_X(x)$, (let's say $x\in[-1,1]$). I want to assign a random variable $x$ to each node of the graph.
So far so easy.
But I want the ...
2
votes
0
answers
42
views
Designing Shortest Route
Suppose we have a metric space $(X,d)$ and we call $r$ to be a root vertex and then there are $n$ clients(i.e. $n$ vertices/nodes) who need packages delivered to them from $r$. The $i$th client ...
- 43
0
votes
0
answers
25
views
How to solve recurrences of this type?
$T(n) = 2 T(\lceil \frac{2n}{3} \rceil) + T(\lceil \frac{n}{3} \rceil) + O(n log n)$
From the 3-ary recurrence tree, one can say that $T(n) \geq cnlog^{2}n$ for some constant c, using the shortest ...
- 1
0
votes
0
answers
17
views
Performing fuzzy search queries on a large database of strings
I have a large database of strings (~10 million)
I need to perform fuzzy search queries which would find the best match inside that database.
The best match meaning the one that has the highest 'score'...
- 113
1
vote
1
answer
34
views
How do we approach this variant of Gaussian Elimination problem
Consider a set of $N$ vectors (each of Length $L$) with positive integer as elements. Given a target vector $T$ of length $L$.
Objective: Using the given set of vectors (by addition or subtraction) ...
- 715
1
vote
1
answer
32
views
Approximate euclidean graph from distance matrix?
In a personal project of mine, I have been faced with the following problem. I have an $n \times n$ matrix $T$ where an entry $t_{ij} \geq 0$ denotes an arbitrary metric between two points $i$ and $j$ ...
- 11
0
votes
2
answers
53
views
Comparison between big-Ω and ω notations
Example of function f(x) such that it is true that f(x) = Ω(g(x)) but that it is not true that f(x) = ω(g(x))
- 111
2
votes
1
answer
58
views
Turning an undirected graph into a directed graph such that in-degree of all nodes is at most 1 or show it is not possible
I was thinking what if you just started with the node with lowest non-zero degree $u$ (only count undirected edges) and picked random edge that is connected to that and direct that inwards. EX: ...
- 21
0
votes
0
answers
15
views
Can a PTAS be called one if it is parameterized by one of the problem inputs (in addition to ε)?
I.e. is it right to say "a PTAS parameterized by sth"?
Is it unusual, and is it correct?
- 1
1
vote
0
answers
12
views
Algorithm to schedule sports league with multiple sports
I haven't seen anything online that covers this specific case:
I run a camp which has about 8 teams of kids, and every day there are 2 sports activities. Teams play each other in different sports ...
- 111
0
votes
1
answer
29
views
Partitioning a set based on a non-equivalence relation
I have a set of $n$ elements, and a binary relation between these elements. However, this is not guaranteed to be an equivalence relation. (Specifically, the elements are line segments in a plane, and ...
- 7,008
2
votes
0
answers
20
views
Algorithm for finding an embedding of a cover diagram
I am making some notes on order theory for my own self study (and certainly anyone else that wants to read them).
I'm impressed with what mermaid can do out of the ...
- 125
0
votes
1
answer
43
views
Algorithm to determine the regularity of a language
According to the answer provided by Janoma, there are several methods to determine the regularity of a language.
Theorem
Let L ⊆ Σ∗. The following conditions are equivalent:
L is generated by a ...
0
votes
1
answer
28
views
Which algorithm solves the single-pair shortest path in a weighted directed cyclic graph?
I need to find the shortest path between two nodes in a directed, positively weighted graph that migt contain cycles. All weights are either zero or one. If it was not weighted, I'd use breadth-first ...
- 3
0
votes
2
answers
63
views
Can a DFA have multiple of the same state?
I need to create a DFA for a sequential order of states e.g.
A -> B -> C -> B -> A
and so on, where 'A' is the start and finish state,
1 is a transition to the next state and 0 just loops ...
1
vote
1
answer
77
views
Given a binary matrix, find the number of sub-matrices with all ones
Given a matrix A, let Aij denote the element of the i'th row and j'th column.
$$ A_{i,j}\in \{0, 1\}$$
Find the number of sub-matrices with all ones.
1 <= #rows, #columns <= 150
P.S. This ...
- 139
1
vote
0
answers
24
views
How to handle coplanarity in convex hull?
I implemented the $O(n^2)$ convex hull algorithm. That is:
Find a triangle known to be in the hull (by finding the lowest point, a point connected to it in the 2D convex hull, and the point that ...
- 143
1
vote
1
answer
26
views
number of substrings in same position with same contents
L1 and L2 are two lists which only consist of X's and Y'...
- 13
0
votes
1
answer
34
views
Calculate all distances in an undirected and unweighted graph
Which algorithm do I use and how much does it cost if I have to:
Calculate all distances in an undirected and unweighted graph from two sources to all nodes.
I think the most appropriate algorithm is ...
- 111
0
votes
0
answers
21
views
Understanding how to assign complexity to functions
I'm having trouble understanding how to assign complexity to functions. As an example, let's take the following pseudo code of the COUNTING-SORT algorithm, taken from the book "Introduction to ...
- 111
0
votes
1
answer
32
views
Algorithm to find minimum amount of swaps to convert array A into array B with repeated elements
I'm trying to create an algorithm that finds the minimum number of swaps to convert array A into array B. In this case the arrays can only contain the numbers 0, 1 or 2.
So for example: given ...
- 15
1
vote
2
answers
82
views
Algorithm for finding a path in a directed graph that visits each node in a given subset
I was wondering about a solution for the following problem:
Given a directed graph $G=(V,E)$ and a subset of vertices $U \subseteq V$ suggest an algorithm that finds if there is a directed path that ...
- 129
1
vote
1
answer
40
views
Minimize bottleneck in flow network
Let $G=(V,E)$ be a flow network with two vertices $s,t$ also each edge has its capacity equal to $\infty$. Our goal is to transfer a flow of size $C$ from $s$ to $t$ so that minimize an edge that has ...
- 1,556
1
vote
1
answer
40
views
What's the most scalable solver of this problem?
Consider the following optimisation problem that its size is parameterised by $n$ (width) and $m$ (depth):
Find $w_1, w_2, \ldots, w_n$ that minmises:
$$
\min \Big[w_1x_1^0 + w_2x_2^0 + \ldots + ...
- 115
1
vote
1
answer
38
views
Scheduling jobs with two people where part (a) of each job must be finished before part (b)
There are n jobs each consisting of two parts: a and b.
There are two people:
person ...
- 23
0
votes
1
answer
22
views
Querying a binary search tree, find maximum
I'm studying algorithms on the very famous book "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein.
and I'm looking at the algorithms for finding the maximum and minimum ...
- 111
0
votes
1
answer
52
views
Summation over shortest path lengths
Suppose directed graph $G=(V,E)$, let $\delta(u,v)$ as the shortest path between any pair $u,v\in V$. Also there is no negative cycle in $G$. Can we conclude that
$$\sum_{u\in V}\sum_{v\in V}\delta(u,...
- 1,556
0
votes
0
answers
51
views
Longest Increasing Subsequence in linear time?
What is the optimal time complexity for an algorithm that solves the Longest Increasing Subsequence problem?
I am aware of the O(n log n) algorithm mentioned in textbooks (and on the Wikipedia article)...
- 101
0
votes
1
answer
15
views
If a graph is not 3-COLORable, then there are at most 2 Independant Sets in G?
Assuming $G=(V,E)$ is a 3-colorable graph, then there are 3 disjoint independent subsets of $V$: $S_1,S_2,S_3$ such that $S_1 \cup S_2 \cup S_3=V$, by taking each $S_i$ to include the vertices of ...
- 37
1
vote
2
answers
63
views
How do I find the most even combination for two arrays
I have two arrays that both contain n elements (positive,non zero, not negative)
{x1....xn}
{y1....yn}
I want to pair them up optimally, one from each array, so that the pairs come out as even as ...
- 11
0
votes
1
answer
36
views
Design an algorithm with linear complexity
Let A[1 : n] be a vector of n integers such that all elements except O(n^2/3) elements are between 1 and 10n. Design an algorithm with linear complexity that sorts A.
Beyond the algorithm, what I can'...
- 111
0
votes
1
answer
43
views
Telling unique values in a short array
I have thousands of short arrays (length less than 9) holding integers. These numbers can be identical with high probability (in many arrays there are two triples of equal numbers). I need to remove ...
- 7,718
0
votes
0
answers
25
views
Are there efficient ways to check if large numbers are prime [duplicate]
I was recently playing around in Python, and I wrote a program to check if a given number is prime. It works by checking to see if its divisible by each number other than 1 leading up to itself. It ...
0
votes
1
answer
36
views
Compute the maximum length of an increasing digital subsequence given an array of digits
Consider the following exercise from chapter Dynamic Programming in the book Algorithms by Jeff Erickson.
Let $D[1 .. n]$ be an array of digits, each an integer between $0$ and $9$. A digital ...
- 1,556
0
votes
1
answer
28
views
A Problem with Solving a Recurrence relation
I Hope someone Can help me with that:
what is the runtime complexity of the algorithm (base 2)
Thanks a Lot!
- 1
1
vote
1
answer
40
views
Solution for the path-finding problem which visits multiple sequences of nodes
Summary
Recently I have had a path-finding puzzle that has some complex constraints (currently, I don't have any solution for this one)
A 2D matrix represented the graph. The length of a path is the ...
- 11
0
votes
0
answers
57
views
Proving correctness of a particular algorithm
Suppose there is an array $A[1..n]$.$A$ contains a permutation of $\{1,2,3,\dots,n\}$.
We run the following algorithm $m$ times to sort $A$:
for each odd index of $A$ from left to right ,respectively,...
- 1,556
-1
votes
2
answers
96
views
Local minimum in array, find $O(\log n)$ algorithm
Main Problem
Given an array $A[1...n]$ ($n \geq 3$) of distinct integers with at least a local minimum, output a local minimum.
A local minimum is an integer $1 < i < n$ such that $A[i-1] > A[...
- 1
1
vote
1
answer
62
views
pairing numbers and intervals
subject: pairing numbers and intervals
Let NUMBERS be a list of n integer numbers. The numbers are listed in no specific order. ...
0
votes
0
answers
9
views
fault-tolerant K-median problem on an undirected graph
We know that the K-median problem is proved to be NP-Hard. In fault-tolerant K-median problem on an undirected graph $G=(V, E)$:
We are given a set of facilities $F\subseteq V$ and a set of demands (...
- 1
-1
votes
1
answer
24
views
Solving a Recurrence relation formula with squared
I Hope someone Can help me with that: enter image description here
I will be asked to answer what is the runtime complexity of the algorithm. I tried to set m=2^ and still failed Thanks
- 1