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,976 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
3
votes
0answers
56 views

Max nodes whose value exceeds all neighbors

A node is valid if its value is greater than all of its incident edges. Task is to maximize the number of valid nodes. Given $n$ values for nodes and $n-1$ values for edges, how do I assign these ...
3
votes
0answers
14 views

Algorithm for animating/morphing convex polygon diagrams

I am trying to find an algorithm to smoothly morph a (given) diagram made of convex polygons into another (given) diagram of the same type. The target diagram is usually generated from the source, ...
3
votes
0answers
52 views

Assignment problem with symmetric matrix

I came across a problem which I think can be reduced to the assignment problem/Hungarian algorithm. We have matrix $A$ and matrix $B$ which are both $n\times n$ symmetric matrices. We can rearrange $...
3
votes
0answers
42 views

Approximate algorithms for class P problems

As a part of my Algorithm course we studied Approximate Algorithms for NP-complete or NP-hard problems, e.g. "set cover", "vertex cover", "load balancing", etc. My professor asked us as an extra ...
3
votes
0answers
26 views

Rearrange items in order reduce fragmentation and reduce wasted space

I have a segment with some offsets at irregular intervals There are items of various length inside. Items cannot be placed randomly. Instead, their left side must match some offset. Items are free ...
3
votes
1answer
53 views

Improve algorithmic complexity

We have an array of N size. We have to perform Q queries on it, in which each Query contains and Index I for which we do: ...
3
votes
0answers
20 views

Generating permutations with a given bubblesort distance

I'm looking for an algorithm to randomly generate permutations on 1:n, which though have a defined bubblesort distance d from 1:n, e.g. (2,3,1) and (3,1,2) are distance 1 from (1,2,3), (2,3,1) and (3,...
3
votes
0answers
23 views

Complexity of finding an alternating Hamiltonian (x,y)-path in edge bicolored complete graphs

Let $G$ be a simple complete graph with an edge-2-coloring. An alternating Hamilton (x,y)-path is a Hamiltonian path which starts at vertex $x$ and ends at vertex $y$ such that the colors of its ...
3
votes
0answers
178 views

Making an array increasing by modifying elements

I am trying to solve a problem on codeforces. Given an integer array $a_1,\ldots,a_n$, our goal is to find the minimal number of instructions, each of which increments or decrements a single entry, ...
3
votes
0answers
17 views

Arrange the array element with minimum number of swaps

Given an array with some elements in which elements can occurs multiple times, so now how to arrange them in such order that no two same elements are together using minimum number of swaps.( it may ...
3
votes
1answer
38 views

Algorithm for computing $Pr[s \vDash C \bigcup^{\geq n} B]$ for probabilistic verification

I'm having some difficulty trying to come up with an algorithm for computing $Pr[s \vDash C ~\bigcup^{\geq n} B]$ given a finite Markov chain where $S$ is the set of states, $s \in S$, $B,C \subseteq ...
3
votes
0answers
35 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
127 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
54 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
163 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
0answers
94 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
223 views

Analysis quickselect: Median of Medians with duplicates

in This Lecture Notes 1 (page 3), it is said concerning quickselect with median of medians: If there are repeated elements ... Alternatively, one has to refine the algorithm and the analysis ...
3
votes
0answers
63 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

Regex NFA construction: Why use Glushkov over Thompson? Pros/Cons

In what circumstances should we prefer Glushkov's algorithm or Thompson's construction for the building of regular expression NFAs? I understand the difference between them, and can follow the ...
3
votes
0answers
65 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
100 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
283 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
85 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
99 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
81 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
236 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
302 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
90 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
131 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
161 views

Is the Bakery Lock fair?

Consider this implementation of the Bakery Lock: ...
3
votes
1answer
548 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
72 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
0answers
210 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
137 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
1k 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
116 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
61 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....
3
votes
0answers
49 views

Efficient approximation for find all the nodes and edges which match with some sub-tree in a graph

Let's suppose that I have a big digraph D and a small tree T (small w.r.t D), both directed, D can be connected or not, but T is connected. Here an example: Let's say that D is as follow: And T is ...
3
votes
1answer
107 views

Survival algorithm for Network deterministic failures

Consider an undirected network $G = (V,E)$ in which edge $e$ $\in$ $E$ fails after (deterministic) time $t(e) > 0$. Network failure occurs at the first instant in which $G$ is no longer connected. ...
3
votes
0answers
108 views

Is there an optimization problem on planar graphs which is APX-hard ?

I'm looking for a optimization problem on planar graphs which is APX-hard, which means that it doesn't admit a PTAS (approximation scheme). It would be even better is the difficulty of the problem ...
3
votes
0answers
158 views

How to minimize the sum of edge weight in the graph while keep the all-pair shortest path greater than a constant?

For example, if we have a graph G = (V, E) and a subset of vertices $U \subset V$. We can set $w(e)$ where $e \in E$ to be a non-negative real number. We want to minimize the total edge weight, but ...
3
votes
0answers
95 views

Are there are satisfying explanations for why genetic algorithms work?

The following commentator writes: Having studied this extensively back when they were called Genetic Algorithms, I would like to offer a few insights. One of the biggest reasons they fell out ...
3
votes
0answers
39 views

Number of binary matrices with all 1's connected

What's the best/optimal known method/algorithm known that can be used to calculate the number of binary $M_{m,n}$ matrices for given $n,m$, whose $1$'s are all connected? Or equivalently, to ...
3
votes
0answers
68 views

Finding same-cost assignments for 3-SAT formulas

Suppose I have a 3-SAT formula in CNF with $ m $ clauses on $ n $ variables, $$ F = C_1 \wedge \dotsb \wedge C_m, $$ with each clause $ C_i = l_{i_1} \vee l_{i_2} \vee l_{i_3} $ and each literal $ l_k ...
3
votes
0answers
90 views

effective, efficient algorithms on antichains

In a partially ordered set L, an antichain is a subset A of L such that no two elements of A are comparable. Antichains are commonly used to represent upward-closed subsets of L, that is, sets S such ...
3
votes
0answers
71 views

How to find m directed paths connecting the maximal number of vertices in an unweighted directed acyclic graph?

Consider an un-weighted directed acyclic graph (DAG) consists of m source (root) vertices and n target vertices. When there is only one source vertex (m=1), the problem to find a directed path ...
3
votes
0answers
65 views

How to determine the maximum valued play in Rummikub?

This question is meant as a follow-up this question and my answer here. The question asked multiple questions about algorithms for playing Rummikub and my answer provided an algorithm that, given a ...
3
votes
0answers
77 views

Algorithm for finding two vectors that span a plane

My problem is as follows. I am working on an experiment where I need to align a 3D vector with spherical coordinates $\vec{v} = (r, \phi, \theta)$ (red) to an infinite 1D line (blue). That line lies, ...
3
votes
0answers
70 views

Arrange objects in space so that the outline takes the least surface/volume

Imagine you have a number of 2-dimensional objects. The question is how to fit them all in a rectangular space in such a way that this rectangle takes the smallest area possible. On the below image ...
3
votes
0answers
127 views

How to find an optimal sequence of matching

Given a graph $G(V.E,w)$ Here $w: E \mapsto R$. We need to find optimal set of matchings(set of edges that have no common vertices) and $t_i$'s such that after all these matchings, it results in $\...

1
3 4
5
6 7
40