# 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
Filter by
Sorted by
Tagged with
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 ...
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)\}$$ ...
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 ...
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:...
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 ...
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$...
31 views

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}$ ...
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 ...
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 ...
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 ...
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 ...
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
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
31 views

### CountDistinct on a range

I have a dataset with and ID and a date looking like: ...