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.

1,698 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4
votes
0answers
103 views

Optimal schedule for broadcasting a file in a complete graph with overheads

I am trying to solve the following problem and despite having performed quite extensive literature review, I do not seem to find any similar problem or technique that would be useful here. PROBLEM ...
4
votes
0answers
50 views

Infer probabilities, for concatenation of words

Fix an alphabet $\Sigma$, and a set of words, $W = \{w_1,\dots,w_n\} \subseteq \Sigma^*$. I have a randomized model that works like this: Alice generates a random sequence of words, using some ...
4
votes
0answers
353 views

KMP Algorithm, Pratt's Minimisation/optimization of Knuth's original DFA based algorithm

The Original Knuth's Algorithm is based on DFA and it depends on the alphabet size. And Then, Pratt optimised it to be independent of Alphabet Size. But, All the ...
4
votes
0answers
189 views

Voronoi Diagrams with L∞ Metric

I've recently become interested in randomly generating Voronoi diagrams to create "territory" maps (similar to this) for a project I've been working on. Traditional Voronoi diagrams using an ...
4
votes
0answers
570 views

2D version of LeetCode house robber problem

The house robber problem of leetcode can be described as followed : A robber enters a colony of houses numbered from 1 to n. Every house has a number printed on the top of it. That number is the ...
4
votes
0answers
28 views

Enumerating Polygonal Subdivisons

Let $P$ be a given polygon in $\mathbb{R}^{2}$ such that all the vertices lie on integral points $\mathbb{Z}^{2}$. An integral polygonal sub-divison of $P$ is a subdivison of $P$ into integral sub-...
4
votes
0answers
246 views

Algorithm to find piecewise circular curve around object made of non-overlapping circles

Introduction I have an object which consist of loosely packed, non-overlapping circles, of radius r. Part of such an object is seen below, the object consist of the bold blue circles, and it ...
4
votes
0answers
146 views

Computing parity of a permutation in a streaming-fashion way

I'm looking for a one-pass algorithm which computes parity of a permutation. I assume that an input permutation is given by stream $\pi[1], \pi[2], \cdots, \pi[n]$. The output should be the parity of ...
4
votes
0answers
97 views

Concurrent Programming Bar Problem

I have been posed a question by my lecturer and I'm trying to figure the right way to go about it. They want me to ensure mutual exclusion for n processes. The code provided is as follows: ...
4
votes
0answers
3k views

Fastest algorithm for shortest path with atmost k edges on a DAG with non-negative edge weights?

(Please note, this is not a duplicate to Shortest path with exactly $k$ edges OR Shortest path with a fixed number of edges. What I want is a better algorithm) The problem under consideration is to ...
4
votes
0answers
122 views

variant of the stable roommates problem

The Stable Roommates Problem matches 2n participants into n sets of roommates based off of each participant's list of preferences. I was wondering if there was a variant of this problem where the ...
4
votes
0answers
207 views

Updating the Cheriton-Tarjan MST algorithm to use binomial heaps?

The Cheriton-Tarjan MST algorithm finds MSTs in time O(m log log n) in arbitrary graphs by using a cleverly-modified version of a leftist heap data structure to store edges. It was developed in 1976. ...
4
votes
0answers
142 views

How does Earley parsing using an automaton work?

As described in this paper, you can use an pre-computed automaton to speed up an Earley parse. I'm not interested in the rigorous proof of this, but just how the basic algorithm works so that I can ...
4
votes
0answers
437 views

Variation of interval scheduling algorithm with several job categories, only one from each can be used

I have a problem similar to the interval scheduling algorithm. The differences are: The jobs have the same length. There are several categories of jobs and only one job from each category can be ...
4
votes
0answers
356 views

Stereo images rectification and disparity: which algorithms?

I'm trying to figure out what are currently the two most efficent algorithms that permit, starting from a Left/Right pair of stereo images created using a traditional camera (so affected by some ...
4
votes
0answers
647 views

What is the complexity of Hoffman and Pavley's Nth best path algorithm?

I am currently working on a project where I'm using an implementation of Hoffman and Pavley's "Method for the Solution of the Nth Best Path Problem" to find n-th best path through a directed graph. ...
4
votes
0answers
229 views

Reduction from knapsack problem to Integer relation that equals one

My question is related to the Integer Relation Detection Problem which can be formulated as: $\qquad a_1x_1 + a_2x_2 + \cdots + a_nx_n = 0$ Where $\forall i. a_i\in\mathbb{Z} \land a_i<c \land x\...
4
votes
0answers
2k views

Show that the Minimum spanning tree Reduce Algorithm runs in O(E) on sparse graphs

This is a problem from CLRS 23-2 that I'm trying to solve. The problem assumes that given graph G is very sparse connected. It wants to improve further over Prim's algorithm $O(E + V \lg V)$. The idea ...
4
votes
1answer
102 views

Merge sort in place

I don't quite understand why in-place sort merge sort isn't preferred over not-in place? Is it because theoretically in place merge sort is better because of its memory complexity tradeoff, but in ...
4
votes
1answer
93 views

How to cluster similar objects into fixed size groups?

I have $n$ people each of which can meet on certain days of the week. I want to group them into $\frac{n}{k}$ groups of size $k$ such that all people in a group can meet on a day. eg - Suppose there ...
4
votes
2answers
964 views

How to Match Socks

When I do my laundry I tend to make a pile of unmatched socks, putting new socks on the top of the pile and matching off pairs if two of the same sock are near the top of the stack. Since eventually ...
4
votes
1answer
3k views

When to use DFS and when use BFS?

Preparing for an interview. I see two cases where each one is specially suited BFS: When you need to find shortest path between vertices (if one exists). DFS: If you need to find cycles in a ...
4
votes
1answer
5k views

Merge two sorted arrays without using additional memory

We have two sorted arrays of integers. Without using additional memory we need to merge these two arrays such that the smallest numbers are in the 1st array and the remaining numbers are in the ...
3
votes
1answer
81 views
+50

Why does Min-Max algorithm delays a good move indefinitely?

Consider a simple chess example: Q is white Queen. K, R is black King and black Rook respectively. A B 1 . Q 2 . . 3 K . 4 . . 5 . . 6 R . 7 . . 8 . R 1,2......
3
votes
0answers
23 views

Gin heuristic algorithm design

(Apologies if this or an equivalent question has been asked in the past; I didn't see anything that answered this question.) I'm designing an algorithm to compute a heuristic for a Gin game engine. (...
3
votes
0answers
85 views

Help understanding how to make a simple 3D minimum bounding sphere?

I need to develop a minimum bounding sphere. It'll only ever be in 3 dimensions, and the numbers of points are relatively small (500-5000 total). Performance is important however. I was looking for ...
3
votes
0answers
34 views

Modifying the JPEG compression to use custom block patterns

recently, while watching a video about machine learning, I had an idea about creating an image compression algorithm, that works similar to JPEG, but is based on arbitrary bitmaps as blocks. I should ...
3
votes
0answers
144 views

Algorithm for answering queries of the type “largest interval contained in the given interval”

I have been wondering over the following problem: Given a set $S$ of intervals on the number line. We can do two operations on them: Add a new interval $[l_i,r_i]$ to $S$ Given an interval $[l_j, ...
3
votes
2answers
58 views

Solving the min edge cover using the maximum matching algorithm

To solve an instance of an edge cover, we can use the maximum matching algorithm. Edge Cover: an edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least ...
3
votes
0answers
76 views

Assign weights to the edges in a DAG so that, for all S and T, all paths from S to T have equal weight

I have a DAG, and on each edge, I have a minimum and maximum weight. I would like to assign (or determine it's impossible to assign) exact weights to each edge so that Each edge's weight is between ...
3
votes
0answers
49 views

DCEL with dynamic graph

Is doubly-connected edge list a good data-structure for planar graph which vertices can be moved freely? I experienced DCEL as a very good structure when it comes to add/delete some vertex or edge. ...
3
votes
0answers
54 views

Self intersection in a simple polygon

Suppose I have a simple polygon whose vertices are $p_1,\ldots,p_n$ each $p_i \in \mathbb{R}^2$. Suppose now I pick two distincts vertices $p_i,p_j, i\neq j$ Is there some algorithm I can use to test ...
3
votes
0answers
72 views

Interesting applications of union-find

I've been trying to find interesting applications of union-find that are lesser known. Here are some popular algorithms based on union-find that I know: Kruskal's algorithm for MST Tarjan's off-line ...
3
votes
1answer
108 views

Building maze to maximize shortest path, may be given waypoints and teleports

How would you go about solving this problem? Is it something that could be expected to be computed/solved within a couple of hours of given a starting area with (32) threads on 3.0GHz Xeon cores? (...
3
votes
0answers
76 views

Adjacent Gray code

Gray code is permutation of $\{0,1,2,\dots,2^n-1\}$ such that each of consecutive number is differs only one bit in binary representation. Example for $n = 3$ $000\\ 001\\ 011\\ 010\\ 110\\ 111\\ ...
3
votes
0answers
45 views

Split a graph into 2 components with known distribution?

I'm trying to find a method to randomly split a connected planar graph $G$ into two connected components, such that the sum of the weights of vertices in each component are relatively close. (If there ...
3
votes
0answers
79 views

Polynomial time algorithms for rank 1 elliptic curves over Q

As an outsider, it sounds like a lot of progress has been made on understanding rank 1 elliptic curves. Much of the BSD conjecture is known for rank 1, and Heegner points provide a way to calculate a ...
3
votes
0answers
211 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 ...
3
votes
0answers
296 views

Algorithm for minimum number of partitions to transform list of sets into Laminar Set Family

I have a list of sets $L$. I want to partition the sets in $L$ to produce a new list $L'$ that is a Laminar Set Family Concretely: For any $L'_i, L'_j \in L'$ if $L'_i \not\subseteq L'_j$ and $L'_j ...
3
votes
0answers
84 views

Matching relative order in subsequence of fixed length

I encountered this problem from game development which I will formulate in a more formal way: Given a sequence $A = a_1, a_2, \dots, a_m$ and a permutation of $\{1, \dots, n\}$, $B = b_1, b_2, \...
3
votes
0answers
108 views

Edmond's Blossom algorithm (Maximum Matching) explanation

I asked this question on Math Stackexchange but it didn't get much attention, so I am asking it here. Edmond's Blossom algorithm (Wikipedia), or simply the blossom algorithm, is a popular graph ...
3
votes
0answers
135 views

Is the Bakery Lock fair?

Consider this implementation of the Bakery Lock: ...
3
votes
1answer
369 views

Task calendar scheduling algorithm

I want to write a scheduling algorithm for the following scenario: There is a set of tasks to complete, each one with a due date, difficulty (easy, normal, hard) and progress on the task. The idea is ...
3
votes
0answers
56 views

Optimal ordering of items with contradictory constraints

I've got a set of items that I'd like to sort into a list. The items have two independent sets of constraints that the ordering should respect: A set of hard constraints that must be satisfied, e.g.: ...
3
votes
2answers
183 views

Invariant on “Find K Closest Elements” problem

I run across this problem: Given a sorted array, two integers k and x, find the k closest ...
3
votes
0answers
72 views

Find all pairs of nodes whose deletion disconnects graph

Given undirected, connected graph, find all pairs of nodes (connected by an edge) whose deletion disconnects the graph. There can't be an edge connecting a node to itself. The problem seems similar ...
3
votes
0answers
100 views

How to find the top k pairwise product of in an array of integers?

Input: An array $a$ of integers $[a_{1}, \cdots, a_{n}]$, and a positive integer $k$. Output: The the top-k products of pairs in $a$. Example: $a = [7,6,5,4,3,2,1],k=3$ , output $(42,35,30)$, with ...
3
votes
0answers
983 views

Finding all possible paths in a directed, (possibly) cyclic graph

I need to find all possible paths in a directed graph, that may have loops. The graph has a defined start and one or multiple defined endings. Basically im trying to find all possible scenarios in a ...
3
votes
0answers
91 views

How to find a minimum spanning forest with a constrained number of nodes in each spanning tree?

Consider a weighted undirected acyclic graph consists of m source (root) vertices and n target vertices. The m-spanning tree problem of the graph is defined as that: (1) each of the m spanning trees ...
3
votes
0answers
53 views

Simon's algorithm in quantum computing

I am curios how simon's algorithm works and I have read this post Simple explanation of Simon's Problem but still is not clear for me. I have found on th internet this example https://www.cs.vu....