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.
11,347
questions
0
votes
0
answers
13
views
Edge connectivity using flow network
Find an algorithm for edge connectivity in undirected graph using flow networks. Try to use $O(m)$ edges.
So basically the flow network should be used as a "helper function" and the graph ...
- 31
1
vote
1
answer
47
views
Worst Case Scenario Quick Sort
I'm aware that the worst case scenario recurrence relation corresponding equation is:
$$
T(n) = T(n-1) + T(0) + \Theta(n)
$$
However, I really don't get how the last term $ \Theta(n)$ was determined.
...
- 11
0
votes
1
answer
30
views
3 Processor Scheduling
A set of n independent tasks, each having integer execution times,
are to be executed using three identical processors. A task can be
executed in any of the three processors. Develop a sequential
...
- 1
0
votes
1
answer
52
views
Optimizing Delivery Routes in a Graph-Based Network to Minimize Maximum Delivery Time
In a graph with N nodes, where each node represents a house and is labeled from 0 to N-1, an ...
- 135
2
votes
1
answer
93
views
Optimal torch placement in voxel games
Problem definition
The world consists of an infinite three-dimensional cartesian grid, i.e. every position is in $P = \mathbb{Z}^3$.
Neighbours of a position $p \in P$ are defined by $N(p) = \{p + e_1,...
- 63
1
vote
1
answer
48
views
Expected maximum matching size in a random bipartite graphs
What is the expected maximum matching size of a bipartite graph $(A\cup B, V)$ where $\lvert A\rvert = n$ and $\lvert B\rvert = n$ and the probability of a edge existing between $A$ and $B$ is a fixed ...
- 25
0
votes
1
answer
35
views
Find a substring length $k$ with maximum occurrences
Given a string length $S$, find a substring length $k$ that has the most occurrences in the given string.
We want $O(S)$ time complexity in an average case.
I think the solution lies in sophisticated ...
- 31
0
votes
0
answers
70
views
Is the following a correct proof for the interval covering problem?
I have written the following greedy stays ahead proof for the problem of covering an interval with subintervals. Is it correct? I think it is, but this is my first time proving a greedy algorithm.
...
- 1
-1
votes
1
answer
65
views
The three elevator problem
There are three elevators in a building that has twelve floors. Find an algorithm that needs to find the best possible way for the elevators to stop at any particular floor considering the traffic ...
0
votes
0
answers
24
views
Optimizing an Algorithm for Timestamp-Aware Partitioning of Data
My Problem
I'm currently dealing with an algorithmic problem that involves two input lists:
A list of natural numbers $[A_1, A_2, \dots, A_n]$ with $A_1, \dots, A_n \in \mathbb{N}$.
A list of triples ...
0
votes
1
answer
27
views
How does a regular expression match `.+x`?
A quick test shows what I'm describing:
> const text = 'foobarhelloworld'
> const pattern = /.+or/
> text.match(pattern) //=> 'foobarhellowor'
What is ...
- 2,163
1
vote
1
answer
58
views
Complexity of non-commutative range multiplication operation
Let $G$ be a non-commutative group, such as $\operatorname{GL}_k(\mathbb F_p)$. Given a list $\vec{a}=(a_1, \cdots, a_n) \in G^n$, we use $(p, q, x)$ to denote the operation that maps $\vec{a}$ to $(...
- 13
1
vote
0
answers
45
views
How to evaluate the complexity of a code
Here is my code for computing the product of sequences of matrices
...
- 111
1
vote
1
answer
84
views
Algorithm for optimal item selections
I'm trying to find an algorithm for this problem:
I'm going to the shop and need to buy X grams of an ingredient.
The shop does not necessarily have an "X grams of ingredient" product.
But ...
- 111
0
votes
0
answers
32
views
Lookup Using Path Matrix in Floyd Warshall Algorithm
How is the path matrix created by the Floyd Warshall algorithm used for path lookup?
The 2 images show the graph (b) and the path matrix (c). Both are taken from the book: Foundations of Algorithms by ...
0
votes
0
answers
93
views
Finding all stable matchings in stable marriage problem
I need to find an algorithm for a modified version of the stable marriage problem. In particular, I need to find all possible stable matchings and not only one (unlike what the Gale-Shapley algorithm ...
- 1
0
votes
0
answers
13
views
Finding all stable matchings in stable marriage problem [duplicate]
I need to find an algorithm for a modified version of the stable marriage problem. In particular, I need to find all possible stable matchings and not only one (unlike what the Gale-Shapley algorithm ...
- 1
0
votes
0
answers
38
views
fast estimation of the amount of unique combinations
Let's say I have a set of two columns - Name, Surname. I have a list of possible values for
Name -> Jacob, John
Surname -> Mayerson, Kindle.
I want to generate a set of unique combinations for ...
- 125
1
vote
1
answer
90
views
Is there an efficient algorithm for this ecommerce optimization problem?
Consider the problem of minimizing the checkout price of a shopping basket in the presence of some discount rules:
There are $n \gt 0$ distinct products in our shopping basket. Each product is ...
- 15
0
votes
1
answer
36
views
Round-robin tournament scheduling, with teams that may share their home field
I need to implement an algorithm to create schedules for round-robin tournaments (where each team faces each other team exactly once), but with the constraint that up to 2 teams – that may play in ...
0
votes
1
answer
104
views
Finding the error probability of a Monte Carlo algorithm
Let's say I have a Monte Carlo algorithm $A$ that gives the correct answer with a probability $p$ > $1/2$. I don't have any information on if it's decisional or not.
I understand that I can make ...
0
votes
2
answers
76
views
Calculating cells encompassing points in a grid
I have a sequence of points over time, and a grid of X by Y cells to which I need to calculate the cells in which the points fall, as depicted in the diagram below
Another point now arrives (as ...
- 101
0
votes
1
answer
33
views
Struggling with Recurrence Relation using Telescoping Approach
I have the following recurrence relation that I am trying to solve using the telescoping approach:
$T(n) =
\begin{cases}
T(\frac{n}{4})+ n^2 & \text{for } n \geq 4
\\
1 & \text{otherwise}
\...
1
vote
1
answer
14
views
How to avoid global delaunay check in conforming triangulation?
I implemented a conforming (i.e. it creates Steiner points using Ruppert's algorithm) delaunay triangulator, which is working, but there is one step I am doing that I straight up don't understand and ...
- 331
1
vote
0
answers
26
views
How to actually implement ruppert's algorithm?
I have been scouting the internet for resource son how to properly implement Ruppert's algorithm and what I ahve found is always lacking in details. The best resources I have so far are these 2:
...
- 331
0
votes
1
answer
34
views
Should I concatenate three lists together or use two separate while loops in Python? Which option offers a better runtime complexity?
In the context of adding sparse polynomials, you have two alternative approaches to combine the terms from two separate polynomials. One option is to use the line of code ...
0
votes
0
answers
18
views
Minimal pairwise comparisons to combine multiple binary trees that are only relatively sorted?
I'm intending on writing a program to let my friends make pairwise comparisons of computer generated images, ranking them. I'm mostly doing this for fun and to do some learning and I picked computer ...
- 410
3
votes
0
answers
28
views
Why is there no self-stabilizing determinsitic algorithm for vertex coloring in general graphs?
This question considers the design of a deterministic self-stabilizing algorithm for vertex coloring in uniform anonymous networks. Uniform anonymous networks do not have distinguished nodes and all ...
- 171
0
votes
0
answers
28
views
State of the art in register allocation for straight-line programs
TL;DR: I'm looking for the fastest known algorithm to perform optimal register allocation (optimal in the sense of minimizing the number of spills and reloads) for straight-line programs.
Context
I am ...
- 161
0
votes
0
answers
28
views
Finding the minimum window where each input array has at least one active element [duplicate]
Given an $m\times n$ matrix $M_{ij}$ where $M_{ij}\in\{0,1\}$, find the minimal range $[a,b]$ for $1 \leq a \leq b \leq m$ such that each column has at least one value set to $1$ within that window, i....
- 1
0
votes
1
answer
44
views
Finding the Point with Maximum Distance from the Boundary of a Closed Polygon in 2D Euclidean Space
Given a closed polygon defined in the 2D Euclidean plane. My objective is to determine the point within this polygon that is furthest away from its boundary. In other words, I want to find the point ...
- 103
0
votes
0
answers
27
views
What is the minimum length word accepted by the product of these simple loop automata?
Let $A_{n} = (aa|aaa|aaaa|\dots |a^{n-2})(a^{n})^* $ where $n \geq 4$ is some natural,and $A_2 = (a^2)^*, A_3 = (a^3)^*$. Clearly every transition is thus labeled by an $a$. From now on let $A_n$ ...
- 495
2
votes
1
answer
61
views
Longest Fibonacci word
We define Fibonacci words as: $F_0 = a, F_1 = b, F_{n+2} = F_n F_{n+1}$, $a, b$ can be any symbols.
How can we find the longest Fibonacci sub-word in a given string in linear time?
This question is ...
- 31
0
votes
0
answers
29
views
Proof of The Optimality Of Greedy Algorithm for The Interval Scheduling Problem
I have this proof for the optimality of the greedy algorithm for the interval scheduling problem in my algorithms class, but I'm struggling to understand it fully, especially starting from the second ...
0
votes
0
answers
26
views
Enumerate all n-tuples in parallel
Let $T = \{0, 1\} ^ {n}$, i.e. set of all $n$-bit binary strings ($n$-tuples). Let $f : T \to T$ be a function, that maps one string to another. $f$ is bijective, but $f^{-1}$ is hard to compute.
It ...
- 101
0
votes
0
answers
27
views
Is there a fully dynamic algorithm to find a minimum arborescence (like Chu–Liu/Edmonds' algorithm)?
Given a weighted directed graph with nonnegative edge weights and a vertex $r$ designated as root, at each step I will do one of the following:
Add a new edge to the graph.
Remove an edge from the ...
- 101
0
votes
0
answers
26
views
A* (A-star) search algorithm including closest distance from a node to an obstacle in heuristic and step cost
I want to include the distance of a node to the closest obstacle in the cost function, so that the path length is not only minimal, but also not near obstacles.
We know that:
Dijkstra's algorithm uses ...
- 1
1
vote
1
answer
41
views
Efficient intersection of multiple paths in a tree
Consider a graph tree $T$, where we are given $k > 1$ unique pairs of nodes $\{u_1,v_1\}\dots \{u_k,v_k\}$. Let $P_{i}$ denote the unique path on $T$ between $u_i$ and $v_i$. Then, my problem is ...
- 13
1
vote
1
answer
136
views
Sorting O(log n) elements in O(n) time
I am presented with the following problem: In an array of $n$ sorted numbers and $f(n)$ unsorted numbers where $f(n)=O(\log n)$, find an algorithm to sort the entire array in $O(n)$ time.
What I am ...
- 11
1
vote
0
answers
23
views
Upper bound via standard manipulation in proof of semi-private learning
I have been reading a paper on private learning [1].
In the proof of lemma 3.3. they claim that
$$
2\left(\frac{2e n_\text{pub}}{d}\right)^{2d}e^{-\alpha n_\text{pub}/4}
$$
is upper bounded by $\beta$ ...
0
votes
0
answers
26
views
Optimal algorithm to select unique values from a daily-growing list
Suppose I have a list of numbers, say $L$, that grows every day when a new batch of numbers get added to it every night. Right now, say the list is of size $M$, with the daily batch size is of the ...
- 101
1
vote
1
answer
54
views
Chordal graphs - what are the use cases?
I'm taking a course in graph algorithms. I've just implemented recognition of chordal graphs for an assignment.
I'm wondering: what are the use cases for chordal graphs?
In other words, what are the ...
- 13
0
votes
0
answers
27
views
Number of clauses in SAT problems
I was going through the proof that DNF-SAT can be solved in polynomial time. The strategy was to go through all clauses, find a clause that doesn't contain both x and x' for any variable x and then ...
- 1
0
votes
0
answers
12
views
Mixfix-parser: finding associated tokens on a list
I've been trying to design an in-program programming language. Like any programming language, the input source code must go through various stages:
Divide the source code into tokens. (Tokenizer)
...
2
votes
1
answer
51
views
Randomizing pairing in "gift swawp"
The problem
I'm arranging a "gift swap" for Christmas with N people involved (N > 2).
I want to create an algorithm that generate the pairing gifter->giftee so that:
everyone receives ...
- 123
0
votes
1
answer
31
views
time complexity of loops
what is the time complexity of:
for (i = 1; i <= n; i = 2*i)
for (j = 0; j < i; j++)
sum++;
?
I thought it is O(nlogn) since the otter loop ...
1
vote
1
answer
113
views
Finding the Largest Partition of Non-Connected Nodes in a Graph in polynomial time
I have a graph, and I want to determine the largest possible set (or partition) of nodes such that no two nodes within this set have an edge between them. I am looking for an efficient algorithm to ...
- 83
1
vote
0
answers
92
views
complexity of graph matching with order constraint
Given a graph with $n$ vertices and $m$ edges, $m \le {n \choose 2}$, we index the vertices from 1 to $n$, and denote every edge by $(l,r)$ where $1\le l < r \le n$.
Find the maximum $k$ such that ...
- 11
0
votes
1
answer
41
views
how do universal turing machines actually work
a TM has states and a tape, and a set of symbols that can get put on the tape. when it 'reads' a symbol on the tape, it's current 'state' tells it what to do next; write a new symbol, where to move ...
1
vote
0
answers
28
views
Grouping transactions having pre-determined sums?
I have a transaction grouping problem that I'm having trouble to devise the algorithm to solve it. Not even ChatGPT (version 3.5) can solve this correctly.
Suppose I have five transactions:
...
- 111