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
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. ...
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 ...
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 ...
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 ...
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 ...
63 views

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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...