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
0
votes
1
answer
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)$ ...
- 133
0
votes
0
answers
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 (...
- 101
1
vote
0
answers
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, ...
- 33
0
votes
0
answers
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 ...
-1
votes
0
answers
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 ...
- 29
0
votes
0
answers
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 ...
- 3
1
vote
0
answers
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 ...
- 11
1
vote
2
answers
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:
...
- 11
0
votes
0
answers
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?
- 101
0
votes
0
answers
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
4
answers
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)\\\\
&\...
- 139
1
vote
0
answers
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).
...
- 11
1
vote
1
answer
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 ...
0
votes
1
answer
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 ...
- 105
2
votes
1
answer
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 ...
- 131
0
votes
1
answer
30
views
Weighted interval scheduling on K-identical machines --- approximation factor
This is a follow-up for Weighted interval scheduling with m-machines ---greedy solution with approximation factor.
As suggested by @D.W., I will present the problem more comprehensively.
$\textbf{...
- 11
2
votes
1
answer
56
views
Is there any computation formalism based on general relativity?
Quantum mechanical principles have already been used to attack computer science problems in the form of quantum computing. In a similar vein, is there any usage of general relativity principles to ...
- 411
3
votes
1
answer
69
views
Division of Large Numbers with Known Factors
Consider two large numbers $a$ and $b$ of which some, not necessarily prime factors, are known. This means $a = a_1 \cdot \dots \cdot a_n$ and $b = b_1 \cdot \cdots \cdot b_m$. Required is their ...
- 151
-1
votes
0
answers
24
views
Recursion tree word done
An algorithm takes as input the length-n array A. It makes 16 recursive calls, on arrays of ½ the input size. It then combines the results in cn steps. Its corresponding recurrence equation is T(n)= ...
0
votes
0
answers
28
views
Confusion about Lemma for Breadth-first search (BFS) proof of correctness
I'm working my way through the graph section of Introduction to Algorithms by CLRS (3E,4E) and I came across the following proof:
3E: Lemma 22.2
Let $G = (V, E)$ be a directed or undirected graph, and ...
- 33
0
votes
0
answers
26
views
Calculating approximation factor of a TSP algorithm
The literature that I have reviewed shows examples of calculations of known approximation algorithms such as the Christofides' algorithm for the TSP. However, I have not been able to find information ...
1
vote
0
answers
47
views
Can FFT for prime $n$ be implemented as a product of $O(n\log(n))$ $2\times 2$ unitaries?
Consider normalized DFT (discrete Fourier transform) — a transform with input $x = (x_0,\dots,x_{n-1})$ and output $y=(y_0,\dots,y_{n-1})$ s.t.
$$y_j = \frac1{\sqrt{n}} \sum_{l=0}^{n-1} x_l \omega^{jl}...
- 111
0
votes
1
answer
23
views
Use of the degree variable in an MSOL formula
I am working on giving an MSOL formula for an NP-hard problem; this proves that the problem is linear-time solvable on bounded treewidth graphs. Given a graph $G = (V, E)$, the problem would be to ...
- 162
5
votes
5
answers
3k
views
Time Complexity of Linear Search vs Brute Force
I am currently watching the FreeCodeCamp Algorithms and Data Structures Tutorial. In the explanation for exponential time complexity, they explain that using a brute force attack on a combination lock ...
0
votes
1
answer
31
views
Subexponential reduction
I am working on exact algorithms for an NP-hard problem $P$. I was able to get a $(1.75^n$) time algorithm for split graphs. When it comes to bipartite graphs, the problem becomes hard to tackle. Now, ...
- 162
1
vote
0
answers
16
views
Why must a safe configuration be reached in `n^2 + n` rounds in Dijkstra's Self-stabilizing mutual exclusion algorithm?
In the book Self-Stabilization (Dolev, 2000) the author provides a proof (p.19) of Dijkstra's self-stabilizing mutual exclusion algorithm. An excerpt of the book showing the proof is found below.
At ...
- 11
1
vote
1
answer
28
views
Algorithm for iteratively distributing $5$ units to two variables
Please point me to the right place if this isn't the right one to ask in.
There are 2 initial integer variables (the values of the two can be changed). $a = 4$ and $b = 1$
There's a function. Each ...
- 13
0
votes
1
answer
61
views
Algorithm to generate length $n$ strings of $4$ colors such that no two subsequent colors are the same
Alice is preparing decorations to decorate the classroom for Children's Day. She is using beads in the colors red (r), green (g), blue (b), and yellow (y) to create strings of beads. During the class ...
- 133
0
votes
2
answers
38
views
Is this a zero knowledge proof algorithm (security)
Suppose we have a website and you log in the website with a username and a password.During registration your computer downloads a file containing a random 32 digit number.Now when you try to log in , ...
- 29
0
votes
0
answers
84
views
Finding the optimal trading route with output amount based on previous trades
I am trying to solve the following problem:
Suppose there are traders who can exchange one good for another. Each trader $i$ defines two functions $y = f_{i1}(x)$ and $x = f_{i2}(y)$, with which we ...
- 1
0
votes
0
answers
18
views
Why Random Access Machine could only have $N \leq 2^{W}$ memory slots? Is it general theorem of informal rule?
Here:
$W$ is "bitness" - number of bits in one machine word, that could be stored in memory slots
$N$ - number of memory slots (each has bitness equals $W$)
My solution:
If max length of ...
1
vote
1
answer
28
views
What would be an algorithm for calculating the ideal column widths of a table to show on-screen, to minimize the table's height?
I've you've ever had a table of text like in Word or Google Docs, you'd know that there are ideal widths for each table column to minimize the height of the table and fit the most text, here's an ...
- 111
1
vote
1
answer
27
views
Understanding crossover points in efficiency between insertion and merge sorts
Self-taught programmer here. I'm reading CORS, and right at the beginning, question 1.2-2, there asks a question:
For inputs of size $n$, insertion sort runs in $8n^2$ steps, which merge sort runs in ...
- 113
0
votes
1
answer
189
views
Finding a cycle of length log(n) given min degree
Let $G = (V, E)$ be an undirected graph such that every $v\in V$ has $\deg(v) \geq 3$. We must create an algorithm that outputs a cycle of length O(log(n)) if it exists. This algorithm must return in ...
1
vote
1
answer
31
views
Minimum edges removed to turn a strongly connected graph into an acyclic graph
If I start with a directed graph that is strongly connected, is there a straightforward way / algorithm to find the smallest set of edges to remove, such that the result is a directed but acyclic ...
0
votes
1
answer
26
views
lower bounds for exact algorithms
I am working on building exact algorithms for NP-hard problems. Let's consider an NP-hard problem $P$. The brute force approach runs in $2^n$ time. In order to prove that there is no $2^{o(n)}$ time ...
- 162
0
votes
1
answer
48
views
Is there an algorithm for the distrubution of ducks into ponds?
The following is small-scale example is meant to illustrate the general distribution problem
Consider 4 parks, each with exactly 1 pond. Parks are marked as vertices in the following undirected graph:
...
- 3
0
votes
1
answer
18
views
Dominating sets and treewidth
As input we are given a graph $G$ and an integer $k$ and are asked to find a dominating set of size exactly $k$ in $G$. This problem is clearly NP-hard, but does it become polynomial time solvable if ...
- 123
1
vote
3
answers
74
views
Matching the segments of a set to longer segments of another set
Consider a set $S$ of segments in the plane. Split each segment in $S$ into a few pieces, and slightly modify the extremities of each obtained segment (by adding a small random value to their ...
- 623
0
votes
0
answers
19
views
Reference and code for community discovery algorithms in multigraphs
In order to group unstructured or sem-structured texts for a timeline construction approach, I consider several types of correlations among such texts. These different correlations induce a weighted ...
- 101
0
votes
0
answers
51
views
Solving the Double-Choco Puzzle: Matching Sub-Matrices with Rotation and Mirroring
I'm working on implementing a solver for Double-Choco puzzle which published by Nikoli magazine. starting by representing the board cells as matrix containing cells with values 1 or 0, where 1 ...
- 111
0
votes
0
answers
15
views
Approach for the fake data generator that needs to maintain an order and referential integrity
I have a Python data generator capable of generating SQL-like relational data with primary and foreign key relationships, composite keys, and partial keys. Currently, I store this data in-memory using ...
- 125
1
vote
0
answers
30
views
Maximize sum of matrix after deleting K rows and K columns
You're given a m by n matrix filled with positive integers, as well as some integer k (0 <...
- 111
0
votes
0
answers
23
views
How to handle duplicates with Heap's algorithm for permutations?
I was able to use Heap's algorithm for generating permutations and I was able to solve the duplicates problem by looking at all the results and filtering out duplicates myself using a HashSet in Java.
...
- 101
0
votes
0
answers
18
views
Implementation of algorithm to enumerate all vertices of a convex polyhedron defined as linear inequalities?
I am looking for an implementation for any of the methods to enumerate all vertices of a convex polyhedron defined by $Ax \leq b$
I have found some papers that talk about the problem, for example this ...
- 291
0
votes
2
answers
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 ...
0
votes
1
answer
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 ...
0
votes
0
answers
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 ...
- 111
1
vote
0
answers
23
views
Graph partitioning in 2 clusters minimizing between cluster edges
I've been looking for an algorithm which divides an undirected graph into 2 subgraphs.
However, unlike most existing work on graph partitioning out there (like METIS), I don't intend to obtain ...
- 11
4
votes
1
answer
97
views
What else measures are used to compare algorithm efficiency apart from Time and Space complexities?
While Time Complexity is the measure of how an algorithm scales with respect to input size, Space Complexity on the other hand measures how much the memory scales as input changes.
I see ...