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
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
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

CountDistinct on a range

I have a dataset with and ID and a date looking like: ...
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,...

1
2 3 4 5
โ€ฆ
196