The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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,705 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
3
votes
1answer
87 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
85 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
110 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
92 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
37 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
63 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
65 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
69 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
42 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
2answers
260 views

Algorithms for procedural generated mazes

For the purposes of this question, a maze is a spanning tree on a square grid (although the type of grid isn't super important). There are many Maze generation algorithms, but they only work on 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
64 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
118 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 $\...
3
votes
0answers
76 views

Given two arrays of length n and n - 1, order the first array such that no partial sum is in the second array

Two arrays of natural numbers are given of length $n$ and $n - 1$: e.g. $A: [a_0, a_1,..., a_{n-1}, a_n]$ $B: [b_0, b_1, ..., b_{n-2}, b_{n-1}]$ All elements of $A$ are unique (can be in $B$), all ...
3
votes
0answers
744 views

How to prove stability of sorting algorithms?

I know to prove instability, we can simply provide a counter-example. But is there a general way to prove that a sorting algorithm is stable? Could you please tell a general method and then show an ...
3
votes
1answer
64 views

Pseudo-random role assignment

I have a number of players, ranging from [0..N]. Each round every player is assigned a specific role, either 1, 2 or 3. ...
3
votes
0answers
38 views

Is it possible, at least in theory, to “lockfree-ize” algorithms algorithmically?

The problem emerged from a practical case, but thinking on it resulted more and more theoretical directions. Typically, the lock-free algorithms do relative simple things in the practice, but their ...
3
votes
0answers
75 views

Check if three given vertices from undirected graph belong to a simple cycle in most efficient way

Is it possible to perform some sort of pre-processing that would allow to answer the question efficiently (fast)? The graph is connected, undirected, has no self loops neither parallel edges (a cycle ...
3
votes
0answers
468 views

How to sort an array $A[1..n]$ with $\sqrt n$ distinct elements in $\Theta(n)$ time and $\Theta(\sqrt n)$ space?

I need to write an algorithm which will sort an array $A[1..n]$ with $\sqrt n$ distinct elements in $\Theta(n)$ time and $\Theta(\sqrt n)$ space? The solution must use hash-tables and advanced data ...
3
votes
0answers
135 views

Is there a faster algorithm for chinese postman problem on a unweighted graph?

Given a undirected graph $G=(V,E)$,find a shortest circuit(it ends at the same point it starts) which through every edges at least once.As we all know,we can easily solve it with Edmond's algorithm ...
3
votes
0answers
626 views

How to determine the fewest number of comparisons for Heapsort?

I'm currently doing an exercise that asks to prove that Standard-Heapsort requires at fewest $\frac{1}{8} n \log(n) - O(n)$ comparisons, in its best case. In its average case, Heapsort only requires $...
3
votes
0answers
58 views

Does Brzozowsky's algorithm always produce the right minimum DFA?

Let's say I have this NFA automaton A: ...
3
votes
0answers
973 views

Lowest single common ancestor in a Directed Acyclic Graph?

I was reading how to find the Lowest common ancestor in a DAG. A DAG can have scenarios where the LCA yields multiple solutions and I feel the accepted answer explains that pretty well. However, one ...
3
votes
0answers
76 views

Find If a node exists in all maximum bipartite matchings

Given a bipartite graph, I need to find for each node, If this node exists in all the possible maximum matchings of the given graph or not. Note that there can be multiple maximum matchings of a ...
3
votes
0answers
70 views

What do we call an algorithm that finds approximate solution sometimes and fails some other times?

Suppose you have a minimization problem $\Pi$. You know that finding a feasible solution to $\Pi$ is NP-hard. You have designed an algorithm $\mathfrak{A}$ to solve $\Pi$ and you prove the following: ...
3
votes
0answers
494 views

SAT and TSP Problems

I am trying to build a tool for solving TSP problem using a conversion to SAT. Does there exist an efficient conversion from the Travelling Salesman Problem to the Satisfiability problem? Since they ...
3
votes
0answers
213 views

Explanation of the extended Euclidean Algorithm

I am looking for some help with understanding the extended Euclidean Algorithm, specifically, this implementation (in Haskell): ...
3
votes
0answers
47 views

Properties of the filtered preference list (phase 1) in the Stable Roommates problem

I'm currently working my way through An Efficient Algorithm for the “Stable Roommates” Problem by Robert Irving (Journal of Algorithms, 6:577–595, 1984). On page 7 the paper starts with ...
3
votes
0answers
82 views

Algorithm for finding the set of minimum coordinate pairs

Consider these two sets of coordinate pairs with weights: ...
3
votes
0answers
1k views

What is the Big-Oh asymptotic complexity of learning in Random Forests?

Random Forests is a bagged ensemble of CART learners. The following is what I've found, but am not sure if I'm completely right. CART (Classification and Regression Trees) uses the Gini index for ...
3
votes
0answers
554 views

How do I generate all possible MSTs of a graph using any algorithm?

For an un-directed graph, how do I obtain all possible Minimum spanning trees? A graph is created with set of Vertices V, and set of edges E. In the below graph, we can see that there are two MSTs. I ...
3
votes
0answers
382 views

Learning automata for degree constrained minimum spanning tree problem

I'm trying to understand the algorithm described in "Degree constrained minimum spanning tree problem: a learning automata approach" (Javad Akbari Torkestani, The Journal of Supercomputing; April 2013,...
3
votes
0answers
79 views

Shortest paths in isomorphic graphs with different edge weights

I'm looking for a way to find the shortest paths from a source to all destinations in isomorphic undirected graphs with different edge weights. The only thing I can think of is using Dijkstra on each ...
3
votes
0answers
76 views

Is there a reduction concept in artitificial intelligence?

Is there a concept for comparing algorithms in artificial intelligence theory similar to reduction in complexity theory (Wikipedia)? I'm asking this because I was wondering how AI algorithms are to ...
3
votes
0answers
284 views

How to make an anytime version of alpha beta pruning?

I wish to use alpha beta pruning in a problem with following constraints: Terminal nodes are likely too distant to be found in most searches Instead I want to maximize an evaluation function There ...
3
votes
0answers
37 views

Dominator tree with edges annotated by min-cut size

Consider the dominator tree of, say, the graph of objects in memory, computed by a memory profiler - one of the most powerful memory leak debugging features, I believe. The dominator tree tells you "...
3
votes
0answers
75 views

What is the level of generality of the bias-variance tradeoff?

I have just learned about the "bias-variance tradeoff" in machine learning, in the context of it being applied to simple regression models. Now I am wondering: is this tradeoff a general universal ...
3
votes
0answers
60 views

Can we create the level graph from sink to source in Dinitz?

One of the steps of the Dinitz algorithm for computing maximal flows is to create a level graph. It is created from source to sink using BFS. Could we create the level graph from sink to source ...
3
votes
0answers
321 views

Does the Longest Common Subsequence problem reduce to its binary version?

I am working on a problem regarding the Longest Common Subsequence (LCS) of two strings, and I was wondering if there is any reduction from the general case of LCS to its binary version, i.e. by ...
3
votes
0answers
98 views

Find internal surfaces in an oriented mesh

I have a solid with internal holes. My solid is mostly a union between walls/floors/ceilings. Each of them is a mesh with polygons oriented counter-clockwise. Then with those polygons I do a union ...
3
votes
0answers
88 views

How to determine Isomorphism of Non-Symmetric Matrix when Permutation-Set is given?

Consider, two $m \times n$ matrices $A, B$ such that there is a permutation $\kappa$ that such that such that $A^{\kappa}=B$ (Wielandt's notation), i.e. $A, B$ are isomorphic but not equal. Since,...
3
votes
0answers
78 views

Branch and Bound running time and golden ratio

This is a follow up question to When does Branch and Bound exactly stop giving solutions for the bin packing problem After testing many instances I found out that when r = V / Vtotal <= ϕ (Golden ...
3
votes
0answers
760 views

Tree of Despair: Collecting Data from a Tree with Multiple Types of Branching

Provided is a tree with three types of node. The structure of the tree cannot be modified and traversal of the tree is limited to querying a node for its children or its parent. The objective of the ...
3
votes
0answers
148 views

Construct matching for half of the vertices, in linear time

Suppose we have a graph $G=(V,E)$ connected and $K_{1,3}$-free. Sumner proved that every claw-free connected graph with an even number of vertices has a perfect matching (so, it is maximum matching). ...
3
votes
0answers
54 views

Enumerate all minimum feedback arc sets

I am looking for (practically) efficient algorithms to enumerate all minimum feedback arc sets of a directed graph. What algorithms should I look at, with practical implementations in mind? ...
3
votes
0answers
104 views

Planar TSP: no node insertion?

Since planar TSP with n nodes is NP-hard, we cannot simply find an optimal solution with n-1 nodes and then insert the remaining node at one of the solution's edges to find the optimal solution of the ...
3
votes
0answers
101 views

Limited lookahead pathfinding strategies on infinite graphs

I'm new to pathfinding algorithms and trying to find a good or even optimal heuristic for the following problem: Say you have a 3D square-lattice cuboid graph with randomly removed edges (with ...
3
votes
0answers
1k views

Which machine learning algorithm is appropriate for predicting a vector?

I have a very large set of animal migration data, consisting of many series of vectors - each series is basically a path of a single animal. The dataset I'm using consists of 244 of these series. I ...
3
votes
0answers
130 views

Convex optimization with the help of Multiplicative Weights Update Method

I've already asked this question over at MathExchange, but since I received no replies or comments there, I hoped it might be more adequately fitting in this category. I have a convex (concave) ...
3
votes
0answers
483 views

How to find a rectangle of maximum value in a $n \times m$ binary grid

Given a $n \times m$ grid $G$, with each grid square having a value 0 or 1, find a rectangle $R$ in $G$ that maximizes $R_1 - R_0$, where $R_0,R_1$ are defined as follows: $R_0$ = the total number of ...