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.

763 questions
Filter by
Sorted by
Tagged with
237 views

state of the art of subset, set containment and partial match queries

The subset query problem is defined as: Given a list D of size N where the entries are subsets of a universe with ...
5k views

Why do we have different algorithm for MST when graphs are directed?

What was the reason to come up with Chu–Liu/Edmonds' algorithm when the input graph is directed instead of using the Prim's or Krushkal's method for finding Minimum spanning tree ? What cases are not ...
1k views

How to approach Dynamic graph related problems

I asked this question at generic stackoverflow and I was directed here. It will be great if some one can explain how to approach partial or fully dynamic graph problems in general. For example: ...
12k views

dynamic programming exercise on cutting strings

I have been working on the following problem from this book. A certain string-processing language offers a primitive operation which splits a string into two pieces. Since this operation involves ...
3k views

Determine missing number in data stream

We receive a stream of $n-1$ pairwise different numbers from the set $\left\{1,\dots,n\right\}$. How can I determine the missing number with an algorithm that reads the stream once and uses a memory ...
503 views

Overflow safe summation

Suppose I am given $n$ fixed width integers (i.e. they fit in a register of width $w$), $a_1, a_2, \dots a_n$ such that their sum $a_1 + a_2 + \dots + a_n = S$ also fits in a register of width $w$. ...
2k views

Closest pair of points between two sets, in 2D

I have two sets $S,T$ of points in the 2-dimensional plane. I want to find the closest pair of points $s,t$ such that $s \in S$, $t \in T$, and the Euclidean distance between $s,t$ is as small as ...
704 views

6k views

Converting a digraph to an undirected graph in a reversible way

I am looking for an algorithm to convert a digraph (directed graph) to an undirected graph in a reversible way, ie the digraph should be reconstructable if we are given the undirected graph. I ...
831 views

Counting islands in Boolean matrices

Given an $n \times m$ Boolean matrix $\mathrm X$, let $0$ entries represent the sea and $1$ entries represent land. Define an island as vertically or horizontally (but not diagonally) adjacent $1$ ...
7k views

What is an Efficient Algorithm?

From the point of view of asymptotic behavior, what is considered an "efficient" algorithm? What is the standard / reason for drawing the line at that point? Personally, I would think that anything ...
576 views

What is the name of this logistic variant of TSP?

I have a logistic problem that can be seen as a variant of $\text{TSP}$. It is so natural, I'm sure it has been studied in Operations research or something similar. Here's one way of looking at the ...
3k views

Correctness of Strongly Connected Components algorithm for a directed graph

I have been reading up on algorithm for finding the strongly connected components in a directed graph $G=(V,E)$. It considers two DFS search and the second step is transposing the original graph $G^T$....
5k views

Updating an MST $T$ when the weight of an edge not in $T$ is decreased

Given an undirected, connected, weighted graph $G = (V,E,w)$ where $w$ is the weight function $w: E \to \mathbb{R}$ and a minimum spanning tree (MST) $T$ of $G$. Now we decrease the weight by $k$ of ...
8k views

Number of submatrices with a particular sum

Given a $n\times n$ matrix A[0...n-1][0....n-1] where all entries are non-negative integers, and a non-negative integer K, I ...
2k views

Algorithm Request: “Shortest non-existing substring over given alphabet”

I'm looking for an (efficient) algorithm to solve the following problem: Given a string $S$ and a set of characters $M$, find the shortest string composed only of characters in $M$ that is not ...
5k views

Greedy and backtracking solutions to an arrangement problem with constraints

I'm revising for my finals. I have found a pattern in past papers in terms of a recurring question, reworded coming up every year. But I've no idea what the marker actually wants... I've asked class ...
3k views

Optimal algorithm to traverse all paths in the order of shortest path

I have to generate all possible paths in a directed, acyclic weighted graph with edge costs. I also have to sort them in order of shortest path. The simplest way that comes to mind is to do a depth-...
383 views

Reconstructing a screen of permuted pixels

Reconstructing a screen of permuted pixels Summary Given a video with the pixel locations randomly permuted (once, for the entire video), can we (efficiently) reconstruct the original picture? Let: ...
5k views

How do I find the max and min value of an array in 3n/2−2 comparisons?

So I'm using this method to find the min and max value of an array simultaneously where I split the array into n/2 and n/2 parts. I then keep splitting each part until I have either a pair of numbers ...
282 views

Is there any data structure that can't be represented or described inside a computer?

We all know that, at least theoretically, there are several possible models of computation, varying in structure. Strictly speaking, there are several (not just one) models of computation that exist ...
3k views

To prove the recurrence by substitution method $T(n) = 7T(n/2) + n^2$

I have done the proof until the point when $T(n) \leq cn^{\log7}$. But when it comes to finding the value of constant $c$, I am getting stuck. The given recurrence relation is $T(n) = 7T(n/2) + n^2$....
1k views

Kosaraju's Algorithm-Strongly connected components

In Kosaraju's Algorithm, using first dfs (traversing on reverse graph) we calculate finishing time of nodes, and then traverse (actual graph) in reverse order of finishing times. why not without ...
938 views

Best improvements to do to the DPLL SAT algorithm

As part of a college class, I'm asked to improve the performance of a basic DPLL sat solver. I'm already provided a basic, slow working version (essentially the DPLL algorithm; furthermore, to select ...
863 views

631 views

Error in the use of asymptotic notation

I'm trying to understand what is wrong with the following proof of the following recurrence $$T(n) = 2\,T\!\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+n$$  T(n) \leq 2\left(c\left\...
1k views

Cutting equal sticks from different sticks

You have $n$ sticks of arbitrary lengths, not necessarily integral. By cutting some sticks (one cut cuts one stick, but we can cut as often as we want), you want to get $k<n$ sticks such that: ...
1k views

Is there a way to test if two NFAs accept the same language?

Or at least generate a set of strings that one NFA accepts, so I can feed it into the other NFA. If I do a search through every path of the NFA, will that work? Although that will take a long time.
872 views

102 views

4k views

Do I understand pseudo polynomial time correctly?

The running time of knapsack is $O(n*W)$, but we always specify that this is only pseudo-polynomial. I was wondering if somebody could tell me if I understand the notion of pseudo-polynomial time ...
478 views

How to find a subset of potentially maximal vectors (of numbers) in a set of vectors

I have a set S (so no duplicates) of d-dimensional vectors of non-negative real numbers (or if you would prefer, floats). I say a vector u "covers" a vector v if, in every dimension 1..d, u[i] >= v[i]...
296 views

Complexity inversely propotional to $n$

Is it possible an algorithm complexity decreases by input size? Simply $O(1/n)$ possible?
3k views

What are the conditions that make the A* algorithm optimal over the other unidirectional search algorithms

I was wondering as what are the specific conditions which make the A* algorithm - optimal in terms of the node expansion over the other Unidirectional algorithms: When the same heuristic ...
353 views

Mathematically determine if two strings are permutations of each other

I've come across many coding exercises that require me to determine whether or not two strings are permutations of each other and I've repeatedly wondered if it would be possible to convert each ...