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.
9,765
questions
0
votes
0answers
5 views
How to cover a surface with a predefined set of objects
I'm making a program that's supposed to be able to find pieces of wood in a dataset to cover a surface. For now I'm focusing on parallelepipedic shapes to simplify the problem (eventually I'd like it ...
0
votes
2answers
73 views
Can't understand the $O$ notation for runtime of algorithms
In my book,the $O$-notation is given as:
$$O(g)=\{f:\mathbb N\rightarrow \mathbb R_{\geq 0}:\exists \alpha\in \mathbb R_{>0},\exists n_0 \in \mathbb N : \forall n\geq n_0 f(n)\leq \alpha g(n)\}$$
...
0
votes
1answer
16 views
Choosing which connection to travel down efficiently
Suppose i want to check if my position is enclosed in a closed loop by following the connection of waypoints that surround it:
Now if i travel from node 0 to node 1. I'm at node 1 and i need to find ...
0
votes
0answers
17 views
Is there a simple algorithm for generating unit tests given a function's code?
Given the abstract syntax tree (AST) of each line of a function's code, I am asked to generate code for that function's corresponding unit tests, similar to what Microsoft's IntelliTest tool does here:...
0
votes
0answers
16 views
Minimum unrooted binary spanning tree
Given a graph $G$ with $n$ tip vertices, $n-2$ internal vertices and a cost on each edge $C(v)$, find a minimum spanning tree subject to degree constraints:
tips have degree $1$
internal vertices ...
2
votes
2answers
2k views
Interval tree: find all intervals containing a given interval
Given an interval tree $T$ and an interval $I$, I need to find an algorithm that returns all intervals in $T$ that contain $I$. The asymptotic running time should be $O(min(n,(k + 1) log n))$ where $k$...
0
votes
1answer
31 views
Best algorithm for Decisional 4-XOR problem?
Decisional 4-XOR Problem: Assume $M>>n$ (e.g. $M=50n$ ). Let $A_1,A_2,A_3,A_4$
be sets consisting of $M$-bit elements. Each set has order exactly $2^n$. Decide whether or not there exists $a_i \...
0
votes
0answers
54 views
Solving an IMO problem Using Graph Theory
Here is a question from IMO 2021:
Let $n>100$ be an integer. Ivan writes the numbers $n,n+ 1,\dots,2n$ each on different cards. He then shuffles these $n+ 1$ cards, and divides them into two piles....
1
vote
1answer
57 views
Calculating a jackpot winner based on probabilities
Imagine a jackpot where users can bet as much as they want, and each bet increases their winning chance. Given a roll [0-100], how would you calculate the winner?
...
0
votes
1answer
23 views
Is it possible to use a quantum computer simulation to perform a cyber attack?
Is it possible to use a quantum computer and or a simulation to perform a cyber attack on classic computers? This is part of a research objective I'm trying to figure out.
1
vote
1answer
49 views
Unconstrained subset sum vs constrained subset sum?
In class, we discussed two question types: constrained subset-sum and unconstrained subset-sum. Let me define the question specifically and then I will mention what I am confused by.
Question 1: ...
0
votes
1answer
32 views
asymptotic tight bounds for quadratic functions
In Introduction to Algorithms by CLRS, it's said
For any quadratic function $f(n)=an^2+bn+c$, where $a$, $b$ and $c$ are constants and $a>0$, $f(n)=\Theta (n^2).$ Formally, to show the same thing, ...
3
votes
0answers
27 views
Reduction from Edge-Coloring and Vertex-Coloring to a new problem
I have a question from a test I did and failed, a question I failed to do.
In short:
the question is about reduction from Vertex-coloring and Edge-coloring, to a new problem they have defined.
The new ...
3
votes
2answers
5k views
Inventory planning problem solved through dynamic programming
I am working on problem (15-11) Inventory planning from Introduction to Algorithms (CLRS, 3rd Ed).
15-11: Inventory Planning, p.411
The Rinky Dink Company makes machines that resurface ice rinks. The ...
0
votes
1answer
91 views
How can I prove the correctness of this exponentiation algorithm using induction?
I have the following algorithm. How could I prove it using induction that for every $n\ge 0$, Exp(n)${}= 2 ^ n$?
...
-4
votes
0answers
17 views
Decision Making Algorithm [closed]
can someone help design a simple algorithm for a task's success, it outputs green if the failure percentage is less than 5%, orange if Its greater than 5% and less than 30 and red if its greater than ...
0
votes
1answer
957 views
Time complexity of quicksort for arrays in increasing or descreasing order
Two $n$-size arays are given: $n_1$ is in decreasing order and $n_2$ is in increasing order.
Let $c_1$ be the time complexity for $n_1$ using quicksort, and $c_2$ the time complexity for $n_2$ using ...
1
vote
1answer
18 views
In every DFS run on $G$, in every step of DFS, the $G_{\pi}$ is a forest
Studying for my finals. So I'm reading the "Introduction to Algorithms (Third Edition)" book. In the DFS section there is the following section:
Depth-first search yields valuable ...
1
vote
2answers
112 views
Need the type of time complexity and its formula
If the complexity of my problem is $O(f_n(n))$ begins at $n =4$ and increases in this sequence:
At
$n = 4$ the number of operations = $(n - 2)$,
$n = 5$ the number of operations = $((n - 2) (n-2)(n-...
3
votes
2answers
76 views
Is there a good algorithm to divide two integers without using division directly?
I am wondering whether this question is appropriate for MathOverflow, but I have asked elsewhere and gotten no satisfactory answer.
Problem. Given positive integers $a$ and $b$, obtain $\frac{a}{b}$ ...
0
votes
0answers
28 views
Reduction from IS problem to other problem [closed]
Given graph 𝐺 = (𝑉, 𝐸) it is said that it is a star if there is a vertex $𝑣_0 ∈ 𝑉$ so that all the other vertices are connected exclusively to it (and not to ...
1
vote
1answer
66 views
Algorithm to check Gibbs' Phase Rule
I am looking for an algorithm to solve the following problem. I am unsure whether to post this in computational science or here, but since this is an algorithm I thought I would try here first.
I have ...
1
vote
1answer
65 views
Generating Unique Ids for Objects
I have an Object Pool and I will be using it to create Objects. I want to generate an unique id for each object. id should be an integer starting from 0. Ids should be continuous. When an object is ...
1
vote
1answer
51 views
For any direct graph $G(V,E)$, there is always an iteration of DFS algorithm on $G$ so the result does not have any cross trees
I suspect that it is not true but I came across with the following statement:
For any direct graph $G(V,E)$, there is always an iteration of DFS algorithm on $G$ so the result does not have any cross ...
-5
votes
0answers
14 views
Find the DFS solution for the following graph if the starting point is vertex 3 and traces all vertice
Find the DFS solution for the following graph if the starting point is vertex 3 and traces all vertice
2
votes
2answers
54 views
Prove that $f(n)$ is $= \Omega(g(n))$ but not $= O(g(n))$
I am trying to prove the following statement.
if $\displaystyle \lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}= \infty$, then $f(n) = \Omega(g(n))$ but $f(n) \neq O(g(n))$
What I've done so far
Using ...
2
votes
1answer
436 views
Imperfection in randomness in VLC shuffle playlist - why?
Whenever I play a playlist of music using VLC (possibly other software too), I notice that some songs never get played while others get played repeatedly (even for a playlist of just 8 songs).
I know ...
2
votes
2answers
30 views
There exists some number $x$ so in any run of BFS from vertex $w$, so the distance from $u$ to $v$ in BFS tree is always $x$
Studying for my finals and stuck on the following question:
Prove or disprove: Given an undirected and connected graph $G=(V,E)$ and three different vertices $u,v,w\in V$ then there exists some ...
2
votes
1answer
70 views
Finding the (probable) maximum of a large set of integers *without* iterating over all of the values
As in the title, I am trying to find the largest (aka least upper bound) of a (very large) set of integers. Importantly, I do not have direct access to the full list of integers, but I do have a ...
2
votes
3answers
130 views
Finding largest elements
I was asked to find write a pseudocode of an algorithm that extracts the Log(N) largest elements in an array and return them in a sorted list, my attempt is
...
1
vote
0answers
49 views
How to design an unbounded Monte Carlo algorithm for SAT(Boolean Satisfiability Problem) problem?
I want the algorithm to be in polynomial time and the correct answer rate is 0.5 or more. (True / false judgment is polynomial time)
All the methods I think of take exponential time(2^n).
Can anyone ...
1
vote
0answers
24 views
Arranging $n$ double-sided cards to produce a given string
Suppose you're given a string $s$ that consists of lowercase alphabetic letters only. The length of the string is $n$. You are also given $n$ cards, which have lowercase alphabetic letters on the ...
6
votes
1answer
450 views
Is there an algorithm to detect race conditions in logic circuits?
I'm writing a logic gate simulator. I would like to prevent user from constructing circuits prone to race condition such as flip-flops, and instead provide them as separate building blocks. Is that ...
1
vote
1answer
133 views
Generating project network graph
I had a problem of generating project network graph (like there and there) from list of activities and their dependencies.
Informal description:
Every activity is represented as edge of directed ...
1
vote
0answers
31 views
0
votes
1answer
39 views
How to work out the odd case?
I am trying to solve this by using Substitution method. My solution must work both for even n-s and odd n-s. For evens case I have solved it. But for the odd's case I am stuck at this point. Hot to ...
1
vote
0answers
31 views
Equivalence of algorithms with less than vs equal to constrains
Problem A:
Given an algorithm $\mathcal{A}$ for $(I,k)$,$k\in \mathbb{N}$, $A$ return true $\iff$ There exist a subset $S\subseteq I$ s.t $|S| \le k$ some property hold.
Problem B:
Given an algorithm $...
5
votes
1answer
68 views
Find all $k$ such that $X_1+kY_1,\ldots,X_n+kY_n$ are all equivalent modulo $M$
Let $n, M$ be integers. Given two arrays $X$ and $Y$ of $n$ elements.
For each $i \leq n$, we define arithmetic progression $X[i] + kY[i] \pmod M$, where $0 \leq k \leq M$.
Find all $k$ such that for ...
2
votes
1answer
370 views
What is the best solving algorithm for a game with stacks?
Game Explanation: Suppose there is a game with cards that have numbers from 1 to n. Each card has a different number so there are not two cards with the same number. The deck is scrambled. We chose ...
1
vote
1answer
142 views
Finding Conflict algorithm doubt
Let $e_1,e_2,\cdots,e_n$ are some events are given by their starting time and ending time.
I have to find an event that conflict with maximum number of other events.
Conflicts means interval ...
1
vote
0answers
19 views
Algorithm to find largest intersection of sets
This is a cross-posting from here, on the mathematics Stack Exchange. I thought this might be a more appropriate venue.
The problem is this:
I have a list of sets $$S_1, S_2,... S_N$$ where each set ...
1
vote
0answers
51 views
Could someone explain the algorithm from this paper? (Thank you) [closed]
Trying to get a fair understanding of our artificial immune systems. To do this I’ve been reviewing this paper, but the algorithm and mathematics is over my head, could someone explain the below to me ...
0
votes
0answers
23 views
Efficient algorithm to solve multiplication Diophantine equation
Consider an equations of the form: (a + x) * (b + y) - c = 0
Or: (a + x) * (b + y) = c
Or: ...
2
votes
1answer
78 views
Is there an FPTAS for 3-way number partitioning?
The maximization problem of the 3-way number partitioning reads as follows:
given $n$ positive integers, partition them into 3 subsets such that the smallest sum is as large as possible. It is known ...
0
votes
1answer
21 views
Best split with conditions
Given this sort of dataset:
ID
Score1
P1
Flag
id1
0.01
0.2
False
id2
0.99
0.9
True
...
...
...
...
The limitations of each variable are:
ID: identifier if each object, unique in the table
Score1:...
2
votes
1answer
70 views
Faster algorithm for specific inversion count (part 2)
Following the issue from Faster algorithm for a specific inversion:
We have a permutation (a derangement actually) $\sigma$ of the set $\{0,1,\dots,n-1\}$ with cardinality $n$.
I want to compute ...
0
votes
1answer
22 views
Find two nodes in a BST such that the root's key is the average of their keys without extra space in $\theta(n)$ worst case time
We can do this in $\theta(n^2)$ time if we calculate the average of all couples of nodes in the tree and compare it to the root, but this is too much time.
We can do this in linear time but with extra ...
0
votes
1answer
134 views
Product Sum of Special Arrays
Can someone please explain why this is correct:
...
2
votes
1answer
49 views
Merging all adjacent and overlapping rectangles in a grid to bigger rectangles
I have a 𝑛×𝑚
rectangular grid of cells, and a set 𝑅 of rectangles within this grid. Each rectangle is a subset of the cells. (Alternatively, you can think of them as axis-aligned rectangles where ...
1
vote
0answers
29 views
Is weighted interval scheduling where the weights are the interval lengths simpler/faster
In weighted interval scheduling arbitrary weights are given to the intervals. A clean dynamic programming solution runs in $O(n \log n)$ time.
If the weights of the intervals are their integer lengths,...
