Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
2answers
164 views

Which of the following statements are true for the given special cases of the Traveling Salesman Problem?

I'm taking the Algorithms: Design and Analysis II class, one of the questions asks: Which of the following statements is true? Consider a TSP instance in which every edge cost is either 1 ...
0
votes
0answers
33 views

Can the Chinese Postman Problem be solved with the Traveling Salesman Problem?

Multiple people suggest that the Chinese Postman Problem (also referred to as the Route Inspection Problem) of a graph G can be solved by applying the Traveling Salesman Problem to its line graph L(G)....
1
vote
0answers
39 views

Tennis Tournament Divide and Conquer for arbitrary number of players

I'm struggling with a divide and conquer algorithm for the Tennis Tournament (or Round Robin tournament). I can successfully build a timetable if $N$ (number of players) is $2^k=N$, but Brassard-...
0
votes
1answer
16 views

Algorithm for Items Best Fit/Arangement in a Box

I was looking for an algorithm that will give the best fit arrangement of package items in a box. For example given a large box and various items with multiple shapes(can be rectangle, square and so ...
0
votes
0answers
34 views

Binary tree for 2 elements

I want to understand Binary Search for 2 element list made of 1,2. I draw a tree as below. Is it correct? If I want to search for an element 2, it will make 2 comparisons. If I want to search for an ...
1
vote
2answers
30 views
4
votes
0answers
48 views

In the FLP Impossibility paper, why did the authors claim that e is applicable to every E in proof of lemma 3?

The paper is available here: https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf The 1st paragraph of lemma 3's proof says In other words,if event e is applicable to config C,and E is any ...
2
votes
1answer
77 views

Can I compute closest split pair of points where distance is strictly less than delta

I've been studying the closest pair algorithm lately and I found this to be an extremely good and intuitive resource: http://serverbob.3x.ro/IA/DDU0221.html. It is also explained in section 33.4, "...
1
vote
1answer
49 views

find all paths from source to destinations and then calculate the path with minimum cost

I am trying to solve one problem. Please refer complete problem statement before proceeding. You are given a road network, with N cities and M bi-directional roads. Each road has some positive ...
1
vote
1answer
32 views

Delete a node with 2 children in a binary search tree

Recently in class we learned how to delete a node from a binary search tree. Since in a binary search tree, each node can have at most 2 nodes, there are 3 cases of deletion. Case 1: The node is a ...
0
votes
0answers
6 views

What analysis / algorithm helps stabilizing the fit of correlated parameters (but not colinear)?

I have many curves that I want to fit using a convolution of some functions. These functions include Weibull distributions with 2 parameters lambda and ...
6
votes
5answers
866 views

Looking for an algorithm to identify contiguous repeated series of lines in a long string

I would like an algorithm that can identify repeated parts of big stack traces like this: ...
1
vote
1answer
39 views

Can You List the Names of Some Algorithms For Determining the Intersection of Two Context Free Grammars?

Suppose we have two sets of strings XS and YS such that set XS is described by grammar GX and YS is described by grammar GY. We want an algorithm which accepts GX and Gy as inputs. The algorithm will ...
7
votes
1answer
57 views

Why do mainstream speech models no longer require a personalized training step?

Back in the Windows XP era, when setting up Windows OS-built-in speech/dictation, I had to speak out a bunch of programmed-in text samples to the speech-to-text engine to personalize my voice profile. ...
2
votes
1answer
26 views

Sublinear Homomorphism Property Testing Counter Example

This is a homework question, so I'm not looking for answers, just general guidance. I'm looking at a Sublinear Algorithms survey where (Group) Homomorphism property testing is discussed. The case of ...
2
votes
1answer
34 views

Can the Dijkstra algorithm work with a negative arc?

When there is no negative circle in the graph? And can Dijkstra not work even if there is a negative arc that does not create a negative cycle?
2
votes
4answers
94 views

A greedy algorithm for the bottle filling problem

(There’s no need to write the algorithm, I just need help with the greedy choice). Problem: you are given bottles numbered 1 to n. Each bottle i has a capacity of Ci and currently contains Li. We ...
2
votes
1answer
62 views

How do I count the exact number of executed commands for a MIPS program?

I want to know what the best way is to count the number of executed commands for a given MIPS program. Let's say we're given a simple for loop that counts from $0$ to $100$. For this I would write the ...
0
votes
1answer
61 views

Is there a useful algorithm with a decreasing asymptotic time?

Algorithmic complexity is usually increasing and almost always strictly increasing based on input size. This is logical since algorithms take time to execute steps, and for almost all problems, the ...
2
votes
1answer
27 views

Is there an algorithm to achieve optimal compression in a “streamed” manner, assuming equal probability of each possibility?

(Sorry for the question title; edits are welcome.) Let's say that you have a set of data made of repeating units, consisting of a value with $2$ possibilities, a value with $3$ possibilities, $5$ ...
3
votes
0answers
178 views

How to select a loop nesting trees for irreducible loops?

I am trying to understand the process of analyzing a control flow graph and building a tree of loops, both reducible (single entrypoint) and irreducible (multiple entrypoint), using the algorithm ...
0
votes
1answer
30 views

Generation of all combinations of a set in max-differing/random order

I'm looking for an algorithm that generates all k-combinations of a set, such that each successive combination generated differs as much as possible (or in practice, a lot) from all previous ...
1
vote
1answer
35 views

Why in Flow network ,there is no reversed edges?

I have read that Flow network is a directed graph , with no self loops and there is no reverse edges and non negative capacity. However in Residual network ,we allow the reverse edges so we can cancel(...
1
vote
0answers
65 views

Decomposition of a bipartite graph into complete bipartite graphs by adding the smallest number of edges

A bipartite graph $G$ and an integer $K$ is given. I want to decompose $G$ into $K$ complete bipartite graphs by adding the smallest number of edges. Below is an example of decomposition when $K=2$. ...
1
vote
1answer
29 views

What's the usage of $S$ in Dijkstra shortest path algorithm in the book Introduction to Algorithms?

I don't understand how the $S$ is needed in dijkstra shortest path algorithm. For each node $v$ in $G.V$, the $v.\pi = previous\_node$ is used to denote it previous node in the shortest path to the ...
1
vote
1answer
17 views

Will MST find the shortest path for each pair $(r,v)$?

Will local best choice will lead to global best choice? In other words, I'm thinking about whether it's possible that the MST has to put its branch location in the middle of two far nodes ...
0
votes
0answers
16 views

Is there a specific search paradigm for finding pairs in a set?

I'm dealing with a very common problem in computer programming that involves, for example 4 people to be divided into 2 pairs. Mathematically, this is just a permutations problem, and the number of ...
1
vote
0answers
11 views

Disk Scheduling for a Fragmented Hard-Drive

Recently In class I have been learning about simple disk scheduling algorithms such as FCFS, STTF, LOOK, LOOK-SCAN etc. From my understanding these algorithms schedule I/O requests depending on which ...
2
votes
2answers
57 views

Technique for converting recursive algorithm to DP

I'm new to Dynamic Programming and before this, I used to solve most of the problems using recursion(if needed). But, I'm unable to convert my recursive code to <...
2
votes
4answers
68 views

Prooving by Pigeonhole principle

I've been given a question to solve: ...
1
vote
1answer
25 views

Can 2-philosophers problem be analogous to dining philosophers problem?

Two philosophers A and B, two forks numbered "1", "2"; A needs both "1" and "2" for eating, so does B. Is this theoretical a dining philosopher problem? I'm questioning about the forks philosopher A ...
1
vote
0answers
21 views

Algorithm to split a grid into different shapes of similar area

I was wondering if any of you know of any algorithm which allows me to split a grid into smaller shapes of a similar area. I have a grid and a few points, these points determine the center of the ...
1
vote
1answer
37 views

Real RAM computational mode

Given a real value $M>0$, I want to compute the greatest value of $\epsilon$ strictly smaller than $M$. Given the assumption that the computational model is Real-RAM, how to find a real number ...
3
votes
2answers
70 views

Is it possible to solve this problem in less than n^2 time without using additional space?

Here's the problem: Given an array array containing integers, maximize array[i] + array [j] + |i - j| where i and j both range ...
0
votes
0answers
10 views

Lower envelope surface for 3d surfaces

Are there any fast algorithms for computing the lower envelope surface for a parametric family of surfaces $f_{a,b}(x,y) = \frac{a-x}{b-y} + c$, where (a,b,c) are parameters.
0
votes
0answers
9 views

What is the algorithm behind Strava's “Fly-bys” feature?

Strava's Flyby feature enables users to see who they passed on runs and rides. From the strava website: Flyby is a Strava Labs tool that lets you playback your activity, as well as those near you, ...
1
vote
0answers
36 views

Optimizing library dimensions

Say I have a library that looks like that: ...
0
votes
0answers
26 views

Branch and bound Dual Gap

Let's suppose we want to solve the knapsack problem using the Branch and Bound algorithm. I know that the algorithm ends when the optimality gap is = 0. However i have not understood how the dual ...
0
votes
1answer
30 views

Batch sizing for convolution neural networks — powers of 2 or powers of primes?

The conventional wisdom for convolution neural networks (CNNs) is to make the batch size a power of 2 because of hardware utilization/optimizations done in the convolution layers. A similar logic ...
2
votes
1answer
38 views

Find four sets where each element from those four appears in at least two of those four sets

I have a list of sorted arrays ("sets") of integers $A_1..A_n$ where each element is unique w.r.t. the other elements in the same array: $A_i = \{x_{i,1}..x_{i,c_i}\}$ $x_{i,p} < x_{i,p+1}$ $A_i$ ...
0
votes
2answers
40 views

Algorithm to explore every node in a graph

I need an algorithm to explore every node in a graph (starting at any given node). Each node can have multiple parent nodes and multiple child nodes. The following algorithm (in psuedocode) appears ...
0
votes
1answer
26 views

Divide and Conquer Algorithm to calculate $a^n$

I am attempting to create an algorithm which given the value of $a \in \mathbb{R}$ and $b \in \mathbb{N}$, calculate $a^n$. So for example, using the Java language pattern, the algorithm will be ...
1
vote
0answers
46 views

An algorithm for getting the position index

Consider these two equation. $$ m_1+m_2+m_3+m_4 = M_m\\ |m_1|+|m_2|+|m_3|+|m_4| = N_m $$ where $\{m_i,M_m,N_m\}\in \mathbb{Z}$. Given the value of $(N_m,M_m)$ we can find the different solutions ...
0
votes
1answer
31 views

How this proof of fractional knapsack works?

I don't understand a step in my book proving the fractional knapsack problem: Let value of items $v_1\ge v_2\ge \dots\ge v_n$, and assume $X=\langle x_1, \dots,x_n\rangle$ are the solution by ...
2
votes
1answer
30 views

How to find how many times an object's path crosses another?

I have several hundred objects that will move in a fixed area throughout the day. Frequently the objects will cross over another object's path, either at the same time (eg. a collision) or within a ...
0
votes
1answer
26 views

Point rank in 2D plane time complexity?

I'm reading about the algorithm of finding the ranks of all points in a 2D plane, I don't understand the time complexity formula for it. It has four steps: Compute the median of x-coordinates of all ...
0
votes
2answers
52 views

How do you detect if an algorithm is running at O(nlogn)?

Given only input and output(e.g. runtime), how do you know if an algorithm is running at O(nlogn) time complexity? For example, how does LeetCode detect my code is running at O(nlogn)? https://...
0
votes
1answer
53 views

Replace 1's with -1's and vice versa in a matix

Assume that we have an anti-symmetric matrix that consists of 1's and -1's and 0's. All the elements of the main diagonal are 0 and each row and each column has exactly one 1, and one -1. Design an ...
2
votes
1answer
39 views

Algorithm to find sets of vertices connected to at most one incoming and one outgoing vertex outside the set

I have a directed graph with vertices $V$, and I need to find a strict subset $U$ of its vertices such that: $U$ contains at least two vertices, and $U \neq V$ There is at most one vertex in $V \...
0
votes
1answer
30 views

Algorithm to generate repetitive sequence of fixed length

I am trying to create an algorithm to generate test cases. Each test case is an array of $n$ natural integers which are randomly generated using a pseudo-random function. The bound for $n$ is $0 < ...