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
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)$ ...
fuzzypixelz's user avatar
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 (...
Novice User's user avatar
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, ...
Hugh Mann's user avatar
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 ...
Almog David's user avatar
-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 ...
Cerise's user avatar
  • 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 ...
silass0's user avatar
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 ...
meeeeee's user avatar
  • 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: ...
user163191's user avatar
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?
Yandle's user avatar
  • 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 ...
pyridoxal_trigeminus's user avatar
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)\\\\ &\...
Sooraj S's user avatar
  • 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). ...
river_bell's user avatar
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 ...
Tanya Choudhary's user avatar
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 ...
Some Name's user avatar
  • 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 ...
Mark Miller's user avatar
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{...
EddieG's user avatar
  • 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 ...
User's user avatar
  • 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 ...
Bob Aiden Scott's user avatar
-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)= ...
NoObMaster42069's user avatar
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 ...
Hugh Mann's user avatar
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 ...
Mathematician....'s user avatar
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}...
fiktor's user avatar
  • 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 ...
Balchandar Reddy's user avatar
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 ...
jacoboneill2000's user avatar
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, ...
Balchandar Reddy's user avatar
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 ...
KSI's user avatar
  • 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 ...
whatdafq's user avatar
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 ...
Martin Inf1n1ty's user avatar
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 , ...
Cerise's user avatar
  • 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 ...
Alex D.'s user avatar
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 ...
Nikita Artemenko's user avatar
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 ...
Oneechan69's user avatar
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 ...
Jim Diroff II's user avatar
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 ...
Money Mit's user avatar
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 ...
Daniel Cherno's user avatar
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 ...
Balchandar Reddy's user avatar
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: ...
silass0's user avatar
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 ...
Will's user avatar
  • 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 ...
Matthieu Latapy's user avatar
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 ...
Max Muller's user avatar
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 ...
Muhammad Z's user avatar
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 ...
lapots's user avatar
  • 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 <...
jeffkmeng's user avatar
  • 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. ...
ashish singh's user avatar
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 ...
Makogan's user avatar
  • 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 ...
PolamreddyVivekReddy's user avatar
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 ...
Ibtida Bin Ahmed's user avatar
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 ...
lesobrod's user avatar
  • 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 ...
koch_kir's user avatar
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 ...
PolamreddyVivekReddy's user avatar

1
2 3 4 5
225