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.

Filter by
Sorted by
Tagged with
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'...
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 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 ...
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,...
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 ...
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 ...
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 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 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