Stack Exchange Network

Stack Exchange network consists of 175 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.

2
votes
1answer
14 views

Merging rectangles into rectilinear polygon

Having a set of adjacent rectangles, what would be the algorithm that gets the rectilinear polygon wrapping around them?
1
vote
1answer
52 views

Given an array of size n, create a sub array with given conditions using dynamic programming

We are given an array of integers of size n, which is not necessarily sorted, and we want to create a sub array. We are allowed to do one of 3 tasks below in each level: 1. skip the number in original ...
1
vote
1answer
19 views

Algorithm for commonalities across related objects

I am making early forays into the application of algorithms to best solve a problem and I am finding it difficult to choose the best application. The problem is give the data below (two columns) ...
1
vote
1answer
10 views

How do i find the feature tracks for triangulation?

I have multiple cameras that records the 2D pixel coordinates of the features each camera sees. After some searching, I came across this paper with a method to calculate the 3D coordinates of the ...
0
votes
2answers
109 views

Algorithm for scheduling unit time tasks with arrival times and deadlines

Suppose we have $n$ tasks to order over $n$ days. Each tasks takes 1 day to be completed. Each task has a start date when the task becomes available and a deadline when the task must be delivered. ...
0
votes
2answers
16 views

Assume we have an algorithm HC for HAMILTONIAN CIRCUIT. How is it possible to convert the HC algorithm to an algorithm HP for HAMILTONIAN PATH?

My understanding is that I have to use the algorithm for Hamiltonian Circuit to help solve the Hamiltonian Path problem. My understanding is that we have to perform a reduction from Hamiltonian Path-...
16
votes
2answers
926 views

Algorithm to test whether a language is context-free

Is there an algorithm/systematic procedure to test whether a language is context-free? In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n a^n : n \in \...
2
votes
2answers
24 views

Least common multiple of a list of numbers

I'm trying to learn computer science by doing some challenges. One is the following. 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. ...
0
votes
1answer
17 views

Question is about a paper “A Block-sorting Lossless Data Compression Algorithm” by M. Burrows and D.J. Wheeler

In the paper A Block-sorting Lossless Data Compression Algorithm by M. Burrows and D.J. Wheeler Link. On page number 5. please describe this line If the original string $S$ is of the form $Z^p$ for ...
1
vote
0answers
86 views

Will this algorithm always solve a constrained sudoku puzzle in quadratic time?

Constrained Puzzle Generation: Let us say a sudoku puzzle is generated with the following procedure: Gather a sequence input of 9 unique numbers in the range $[1 .. 9]$. Call it $S$. Map $S$ to a $3 ...
0
votes
0answers
16 views

Question on preventing k from reducing too quickly during KMV intersection

This question considers KMV, an algorithm that is able to estimate the cardinality (unique item) from a stream of data. The way it does it is to first map the stream of data to a space that almost ...
0
votes
1answer
28 views

algorithm for correctly rounded floating point radix conversion

Is there any generic algorithm which implements a floating point radix conversion? Lets say we have a $p$-digit FP number $A = \sum_{i=0}^{p-1} A_i \beta^{e-i}$ in radix $\beta$ and with $0 \leq ...
1
vote
1answer
43 views

Finding constrained random time intervals with a constrain also on their sum

I'm searching to devise an algorithm that finds a set of n time intervals with a random duration between min and max. On top of that, the total duration is also given (tot). For example: n = 15 ...
0
votes
0answers
23 views

ILP representation of the number of maximal 1 sequences in a row

I am currently using an ILP to model events which occur on some input sequence from $1...n$. These events modify the input sequence in order to obtain a desired sequence. Each event can happen on some ...
0
votes
2answers
361 views

What if Indexes in Hoare's Quick Sort Algorithm Both Land on Values Less than Pivot?

If I were to sort the list of numbers 1,7,5,7,1 using Hoare's algorithm as described at the very beginning of wikipedia item on Hoare partition scheme with 5 being the pivot, and the indexes start at ...
3
votes
1answer
36 views

Finding the shortest path for synchronized pawns in a maze

I have been trying to wrap my head around this problem, and I just can't get it. We have an $a \times b$ matrix where every cell corresponds to either an empty space, denoted with a dot, or a wall, ...
0
votes
1answer
84 views

Confused about constructing the “failure table” in Knuth-Morris-Pratt algorithm

I'm trying to learn how the "failure table" is constructed in the Knuth-Morris-Pratt algorithm since it seemed nontrivial to me that you could do it in $O(k)$ time (where $k$ is the length of the ...
4
votes
1answer
219 views

An algorithm for a minimization problem, How to minimize the wasted length of combination of multiple items with different length and number

Suppose there is an unlimited number of pipes, each has length $x$ meters. There is a list of requirements of pipes with shorter length than $x$. The number of these items are also given. For example ...
6
votes
2answers
197 views

Find if a sequence of node is a result of a binary tree preorder traversal

Assume we have a sequence of 0's and 1's: $n_0, n_1, ..., n_N$, in which 0 stands for a leaf node, and 1 stands for an uncertain node (it may or may not be a leaf node). How to check if this sequence ...
1
vote
1answer
75 views

How do you solve this [1,5,9,4] pair numbers problem?

So given an array of [1,5,9,4], find all pairs of numbers that can sum/subtract/divide/multiply to another number in the array(that number is not part of the pair), and return the total count of pairs ...
1
vote
1answer
38 views

Given Directed Graph G(V,E) with red/black vertices, v is good if there's a path from v to a black vertex

Given Directed Graph G(V,E) with red/black vertices, v is "good" if there's a path from v to a black vertex. in linear time. Question: Find all the good vertices in the graph I've come up with an ...
1
vote
1answer
20 views

Complexity of set partition generation while equivalence relation is given

Given a binary equivalence relation, R on a set A, Let P be the resulting partition. I want to generate the partition means each subset in the partition. What would be the fastest algorithm for this ...
3
votes
1answer
114 views

Use dynamic programming toe

Let's say we have two arrays m and n containing the characters from the set a, b, c , d, e. ...
0
votes
1answer
40 views

How to understand a equation related to speaker recognition?

This question refers to the following paper: Support Vector Machines for Speaker and Language Recognition, W. M. Campbell, J. P. Campbell, D. A. Reynolds, E. Singer, P. A. Torres-Carrasquillo, ...
4
votes
1answer
56 views

Indexing Edge Permutations for the Rubik's Cube

I'm working on a Rubik's Cube solver that implements Korf's algorithm, as published in his 1997 paper, Finding Optimal Solutions to Rubik's Cube Using Pattern Databases. His method involves creating ...
4
votes
2answers
72 views

Find maximal subgraph containing only nodes of degree 2 and 3

I'm trying to implement a (Unweighted) Feedback Vertex Set approximation algorithm from the following paper: FVS-Approximation-Paper. One of the steps of the algorithm (described on page 4) is to ...
0
votes
0answers
37 views

Find a minimum weight matching of a specific size

Given a positive-weighted complete graph $G=(V,E)$ and an even integer $k$, I want to find a minimum weight matching of size exactly $k$, i.e., I want to choose $k/2$ vertex disjoint edges such that ...
1
vote
1answer
287 views

Finding all paths from s to t in linear time

I was looking at the following algorithm which prints all the paths from node s to node t and I have some questions I don't ...
1
vote
0answers
21 views

vertex cover of bipartite graph

A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. A minimum vertex cover is a vertex cover with minimal cardinality. ...
0
votes
1answer
53 views

Modify max value multiple times of a list

I have two lists say $A$ and $B$, each consisting of n positive integers. I make a list $C$ such that each element of $C$ i.e., $C_i=A_iB_i$ for each element $A_i \in A$ and $B_i \in B$. Now I have ...
2
votes
1answer
352 views

Distance vector in a weighted graph

I got a weighted, connected and directed graph $G$. There is a vector called the distance vector $Dv \in \mathbb{N}^n$ in which $Dv_i$ is the shortest distance from $1$ to $i$. All edge weights are ...
4
votes
0answers
36 views

How to generate a random reducible flow graph?

Is there any known algorithm to generate a random reducible flow graph (single root, single sink) with a given maximum cardinality $N$? Ideally, the distribution should be uniform over the set of ...
-1
votes
0answers
17 views

What is the source to understand Feedback edge arc set? [on hold]

What is the source to understand Feedback edge arc set? I tried wikipedia and research papers any easy tutorial?
1
vote
0answers
97 views
+200

Morphing Hypercubes, Token Sliding and Odd Permutations

A month ago, I asked the following question math.exchange (https://math.stackexchange.com/questions/3127874/morphing-hypercubes-and-odd-permutations), but for completeness, I will include the details ...
5
votes
2answers
2k views

how does the parallel radix sort work?

I'm currently learning computer science, and there is a slide of notes brief described the parallel radix sort under data parallelism. ...
1
vote
1answer
330 views

Binary heap: prove that number of nodes of height h is not bigger than $\lceil \frac{n}{2^{h+1}} \rceil$

My thoughts process: let number of elements in heap be $n$, total height of binary heap be $H$, height of node be $h$, and let number of nodes with height $h$ be $x$. Then number of nodes with height ...
0
votes
1answer
548 views

Task scheduling algorithm (minimize wait time)

Let's say that I have one task to perform $n$, $n<250000$ times and it takes $p$, $p < 700000$ time to complete it once. I have list of time constraints ${t_1, t_2, ..., t_n}$ where $t_1<=...
1
vote
1answer
35 views

Check if possible to perform n tasks, each between moment b(i) and e(i) and taking 1 time unit

I have such a task at university: we have n tasks, i-th of them can be done between moment b(i) and e(i). If we decide to perform a task in moment x, we finish performing it in moment x+1. We can ...
19
votes
1answer
764 views

Compression of domain names

I am curious as to how one might very compactly compress the domain of an arbitrary IDN hostname (as defined by RFC5890) and suspect this could become an interesting challenge. A Unicode host or ...
7
votes
5answers
35k views

Why can't DFS be used to find shortest paths in unweighted graphs?

I understand that using DFS "as is" will not find a shortest path in an unweighted graph. But why is tweaking DFS to allow it to find shortest paths in unweighted graphs such a hopeless prospect? ...
7
votes
2answers
2k views

Time Complexity analysis for Map-Reduce model

I am trying to redesign my algorithm to run on Hadoop/MapReduce paradigm. I was wondering if there is any holistic approach for measuring time complexity for algorithms on Big Data platforms. As a ...
0
votes
1answer
32 views

What are possible uses for cross, back and forward edges after the DFS visit?

The depth-first search visit of a graph produces, in some implementations, a labeling of the edges as "Cross", "Back" and "Forward". I know "B" edges can be used to detect cycles. What are other ...
1
vote
2answers
42 views

Algorithm to compact/simplify ranges?

I'm trying to create an algorithm in C# that given a list of ranges (segments) it produces a compacted list of them: Example 1 Input: [1, 3], [2, 6] Output: [1, 6] Example 2 Input: [1, 2], [2, 3] ...
3
votes
1answer
255 views

Convex Hull on a Spherical Surface

Is there any convex hull algorithm that can be extended to non-euclidean metric, such as the geodesic distance on the surface of a sphere?
0
votes
0answers
38 views

Area of Union Of Rectangles using Segment Trees

I'm trying to understand the algorithm that can be used to calculate the area of the union of a set of axis aligned rectangles. The solution that I'm following is here : http://tryalgo.org/en/...
1
vote
0answers
24 views

Is there a less than $O(n)$ algorithm for converting UTF-8 character offsets to byte offsets, in a gap buffer?

A Gap Buffer is a variation on a dynamically-sized array, but with a gap inside it. The gap makes editing operations around the gap more efficient. Deletion before the gap can be implemented by simply ...
15
votes
2answers
626 views

Compute a max-flow from a min-cut

We know that computing a maximum flow resp. a minimum cut of a network with capacities is equivalent; cf. the max-flow min-cut theorem. We have (more or less efficient) algorithms for computing ...
2
votes
0answers
86 views

Interleave two arrays such that collisions are minimised (dynamic programming) [on hold]

This is a fascinating bioinformatics dynamic programming that I am solving. I am not looking for an answer to the problem, but rather any algorithms, research papers, or other pointers that could be ...
0
votes
0answers
30 views

An interesting compression algorithm idea

I stumbled on this paper about compressing images using a kind of odd, but interesting idea. It seems pretty easy to implement and I was wondering if there is something wrong with it that I haven't ...
1
vote
0answers
62 views

Is there a way to solve coding challenges more easy? [on hold]

I'm always using debugging and writing test cases to solve coding challenges. It's been very helpful so far but now that problems became very complex, its not good enough. Is there a way to use tools ...