# 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,247 questions
Filter by
Sorted by
Tagged with
31 views

### Specialized SAT solver (?)

(Context) Given two byte arrays of length 16, say $L$ and $H$, one can define a mapping $M$ from the set of all bytes to itself in the following way. If $0 \le b \lt 256$ is a byte, let $\text{lo}(b)$ ...
14 views

### Algorithm to balance candies among students

Let's say N students S1, S2, ... SN with their respective candies count c1, c2,... cN The ask is to distribute the candies (...
1 vote
109 views

### Question about step in proof that predecessor subgraph forms a breadth-first tree

Given the following theorem and definitions from Introduction to Algorithms 3rd edition by CLRS: Theorem 22.5: (Correctness of breadth-first search) Let $G = (V, E)$ be a directed or undirected graph, ...
29 views

### Finding min s-t cut of network with flow on the nodes

Given a network with flow on the nodes. How can we find min s-t cut in a network with flow on the nodes? We know how to find min s-t cut whenever there’s a network with flow on the edges (Ford ...
56 views

### Using recursion to find rotation matrices of higher dimensions

I am looking to find a way to calculate a rotation matrix of $m$ x $m$ dimensions.I was thinking since it is almost impossible to find analytically , maybe we can use recursion to solve much simpler ...
20 views

### Max flow with a minimal in-degree objective on certain nodes (for edges with non-zero flow)

The following a small-scale example meant to illustrate the general problem Suppose we have $n = 60$ marbles that we want to distribute into 3 bowls, $B = \{bowl_1, bowl_2, bowl_3\}$ The marbles can ...
1 vote
39 views

### Properties of $\mathrm{Shade}$ algorithm

I am working on the following problem which is taken from the book Algorithms by Ojo: A relaxation of the Max-TSP problem is the Shade problem. Let us call a shade of a graph as a set of disjoint ...
1 vote
30 views

### Finding growth rate of T(n) of a code segment

I am presented with the following code segment and asked to find the growth rate, which can be done by finding the number of times the variable sum is incremented: ...
12 views

### Can Gomory-Hu tree algorithm be applied to graphs with more than one connected component?

If I have an undirected graph with more than one connected component, can I apply the Gomory-Hu algorithm directly on the entire graph or do I have to apply it separately to each component?
14 views

### Current best output-sensitive algorithm for computing all maximal cliques of a graph

I am looking for a reference on the most optimal output-sensitive algorithm currently available for listing all maximal cliques in a graph. I know the Bron-Kerbosch algorithm is highly utilized, but ...
1 vote
116 views

### Understanding the Recursive Algorithm for Integer Division

In my reference, Page 26, Algorithms by Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani, a division algorithm is give as, \begin{align} &\text{function divide}(x, y)\\\\ &\...
1 vote
44 views

### Diffucuty in understanding code after a recursive call

This is an example algorithm of a recursive insertion sort I'm trying to understand. I've have tried understanding this with the help of print statements (which I've commented). ...
1 vote
23 views

### Comparing a greedy and a brute force algorithm for NMS

Hello I am trying to implement Non Max suppression algorithm for removing overlapping bounding boxes. I have a list of bounding detected by an object detector in the format B(x,y,w,h,s) x,y are ...
27 views

### Is binary tree balanced if and only if the morris traversal of the tree produces ordered list?

I'm trying to check if the binary tree is binary search tree. My idea is to use Morris traversal. Intuitively a binary tree is balanced iff Morris traversal produces a sorted threaded linked list. The ...
55 views

### Efficient algorithm for finding a point P with the highest winding number

Given an ordered list of two-dimensional points $P$ that represent the vertices of an $N$-sided (very) self-intersecting polygon, find a point $p_{best}$ with the highest winding number of all points ...
30 views

55 views

### Does the base component affect Logarithmic and Exponential Runtimes in Time Complexity (Big-Oh) of an algorithm?

Let us look at the following 2 cases: We say a binary search implementation in a sorted array of size n has a time complexity ...
21 views

### Sign confusion in a BFS lemma

I have a confusion related the Lemma 22.1 in Cormen Leiserson Rivest Stein's Introduction to Algorithm book, Here it is written that delta(s,v) <= delta(s,u) +1 ,where s,u,v are the vertices of a ...
14 views

### Periodicity of substitution system

I’m interested in substitution systems: maps which use a set of rules to transform elements of a sequence into a new sequence. For simplicity we will consider here only binary 1-D arrays. Unlike the ...
1 vote