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
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 ...
popcorn's user avatar
  • 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. ...
RodrigoAlb's user avatar
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 ...
Sachin's user avatar
  • 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 ...
maplemaple's user avatar
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,...
user13062187's user avatar
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 ...
Anonymous's user avatar
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 ...
popcorn's user avatar
  • 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. ...
windoid's user avatar
-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 ...
chris pine's user avatar
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 ...
mathbreaker's user avatar
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 ...
Lance's user avatar
  • 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 $(...
user779130's user avatar
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 ...
Tung Nguyen's user avatar
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 ...
Julien's user avatar
  • 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 ...
Labeeb Basil's user avatar
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 ...
void's user avatar
  • 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 ...
void's user avatar
  • 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 ...
lapots's user avatar
  • 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 ...
Jo Ma's user avatar
  • 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 ...
Matteo Battaglio's user avatar
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 ...
diegodr02's user avatar
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 ...
OrdinaryOrange's user avatar
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} \...
Nancy Drake's user avatar
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 ...
Makogan's user avatar
  • 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: ...
Makogan's user avatar
  • 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 ...
alefvanoon's user avatar
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 ...
AncientSwordRage's user avatar
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 ...
NoName123's user avatar
  • 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 ...
swineone's user avatar
  • 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....
fekr's user avatar
  • 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 ...
Meni's user avatar
  • 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$ ...
Daniel Donnelly's user avatar
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 ...
popcorn's user avatar
  • 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 ...
Mohamed Hendy's user avatar
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 ...
Georgy Firsov's user avatar
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 ...
Cem's user avatar
  • 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 ...
Math98's user avatar
  • 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 ...
rolfvdhulst's user avatar
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 ...
Derek Kwon's user avatar
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$ ...
TheCollegeStudent's user avatar
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 ...
dezdichado's user avatar
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 ...
zaabson's user avatar
  • 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 ...
Aditya's user avatar
  • 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) ...
Microfractal's user avatar
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 ...
il_mix's user avatar
  • 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 ...
user163594's user avatar
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 ...
LargeHorse's user avatar
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 ...
quTANum's user avatar
  • 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 ...
gangsterio's user avatar
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: ...
adib's user avatar
  • 111