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.

Filter by
Sorted by
Tagged with
5
votes
2answers
12k views

$T(n)=2T(n/2)+n\log n$ and the Master theorem [duplicate]

According to Introduction to algorithms by Cormen et al, $$T(n)=2T(n/2)+n\log n$$ is not case 3 of Master Theorem. Can someone explain me why? And which case of master theorem is it?
5
votes
2answers
3k views

How is the Subset Sum Problem NP-Complete?

You can't find a solution online for it that doesn't run in polynomial time complexity, when using dynamic programming. Have all these sites secretly solved P=NP, and no one knows about it?
3
votes
1answer
76 views

Determine what is the best order for running filters on a dataset [duplicate]

I'm trying to figure out what is the optimal order for running a sequence of tasks in a pipeline. Each task filters a percentage of the dataset. Assuming I got the tasks t1, t2, t3, ..., ti and a ...
3
votes
1answer
675 views

Fast, stable, almost in-place radix and merge sorts

I've developed LSD radix sort algorithm that is stable, about as fast as the classic LSD radix sort, require only $O(\sqrt{RN})$ extra space when we sort into R buckets. The same technique also ...
2
votes
1answer
387 views

How to find vertices of bounded region made by intersection of lines

Suppose we have random lines made with 2 points. and point has (x,y) For example: Now when we draw a random line you will see many lines intersect with each other. This eventually gives rise to ...
2
votes
1answer
1k views

Finding the best combinations between items of 2 arrays in a sequential manner

I'm reposting this because people found the last description to be too hard to follow. The data unit I'm working with is a pair of 2 numbers. The numbers can be any integer that is bigger than 0. ...
2
votes
3answers
521 views

Which fingerprinting/hashing algorithms support compounding?

The definition of fingerprinting algorithms in Wikipedia describe a property called compounding as you can see here as: Some fingerprinting algorithms allow the fingerprint of a composite file to ...
2
votes
2answers
1k views

Given a set of 2D vectors, find the furthest reachable point

Input: a set of 2D vectors $S=\{v_1,v_2,\dots,v_n\mid v_i\in \mathbb{Z}^2 \}$ Question: name $P=\{\sum_{v_i\in S'}v_i\mid S'\subseteq S \}$ for all subsets of $S$ (obviously $|P|=O(2^n)$). In ...
1
vote
1answer
170 views

Minimizing sum of recursive pairwise sums

What is the best algorithm for this? We are given an array of positive integers and we want to minimize the total cost of recursively adding together all the integers to one integer, two integers at ...
-1
votes
2answers
293 views

Vertex cover of bipartite graph

A vertex cover is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. A minimum vertex cover is a vertex cover with minimal cardinality. From codeforces, ...
67
votes
4answers
16k views

What is the novelty in MapReduce?

A few years ago, MapReduce was hailed as revolution of distributed programming. There have also been critics but by and large there was an enthusiastic hype. It even got patented! [1] The name is ...
44
votes
7answers
65k views

Minimum spanning tree vs Shortest path

What is the difference between minimum spanning tree algorithm and a shortest path algorithm? In my data structures class we covered two minimum spanning tree algorithms (Prim's and Kruskal's) and ...
37
votes
3answers
14k views

Why is the Mersenne Twister regarded as good?

The Mersenne Twister is widely regarded as good. Heck, the CPython source says that it "is one of the most extensively tested generators in existence." But what does this mean? When asked to list ...
15
votes
4answers
33k views

Am I right about the differences between Floyd-Warshall, Dijkstra and Bellman-Ford algorithms?

I've been studying the three and I'm stating my inferences from them below. Could someone tell me if I have understood them accurately enough or not? Thank you. Dijkstra algorithm is used only when ...
25
votes
5answers
40k views

When to use recursion?

When are some (relatively) basic (think first year college level CS student) instances when one would use recursion instead of just a loop?
13
votes
1answer
5k views

Getting parallel items in dependency resolution

I have implemented a topological sort based on the Wikipedia article which I'm using for dependency resolution, but it returns a linear list. What kind of algorithm can I use to find the independent ...
34
votes
3answers
7k views

Worst case $O(n \ln n)$ in place stable sort?

I am having trouble finding good resources that give a worst case $O(n \ln n)$ in place stable sorting algorithm. Does anyone know of any good resources? Just a reminder, in place means it uses the ...
28
votes
2answers
4k views

Where to get graphs to test my search algorithms against?

I am implementing a set of path finding algorithms such as Dijkstra's, Depth First, etc. At first I used a couple of self made graphs, but now I'd like to take the challenge a bit further and thus I'...
10
votes
2answers
4k views

Fast k mismatch string matching algorithm

I am looking for a fast k-mismatch string matching algorithm. Given a pattern string P of length m, and a text string T of length n, I need a fast (linear time) algorithm to find all positions where P ...
23
votes
3answers
5k views

Which algorithms can not be parallelized?

Is there any algorithm which is very difficult to parallelize or the research is still active? I wanted to know about any algorithm or any research field in parallel computing. Anything, I searched ...
13
votes
5answers
33k views

What is the significance of negative weight edges in a graph?

I was doing dynamic programming exercises and found the Floyd-Warshall algorithm. Apparently it finds all-pairs shortest paths for a graph which can have negative weight edges, but no negative cycles. ...
20
votes
2answers
12k views

What is the fastest algorithm for multiplication of two n-digit numbers?

I want to know which algorithm is fastest for multiplication of two n-digit numbers? Space complexity can be relaxed here!
20
votes
2answers
28k views

Getting negative cycle using Bellman Ford

I have to find a negative cycle in a directed weighted graph. I know how the Bellman Ford algorithm works, and that it tells me if there is a reachable negative cycle. But it does not explicitly name ...
14
votes
2answers
2k views

Shortest non intersecting path for a graph embedded in a euclidean plane (2D)

What algorithm would you use to find the shortest path of a graph, which is embedded in an euclidean plane, such that the path should not contain any self-intersections (in the embedding)? For ...
33
votes
1answer
8k views

Do you get DFS if you change the queue to a stack in a BFS implementation?

Here is the standard pseudocode for breadth first search: ...
30
votes
2answers
4k views

What are very short programs with unknown halting status?

This 579-bit program in the Binary Lambda Calculus has unknown halting status: ...
19
votes
3answers
513 views

Problems in P with provably faster randomized algorithms

Are there any problems in $\mathsf{P}$ that have randomized algorithms beating lower bounds on deterministic algorithms? More concretely, do we know any $k$ for which $\mathsf{DTIME}(n^k) \subsetneq \...
16
votes
3answers
35k views

Increase-key and decrease-key in a binary min-heap

In many discussions of binary heap, normally only decrease-key is listed as supported operation for a min-heap. For example, CLR chapter 6.1 and this wikipedia page. Why isn't increase key normally ...
10
votes
3answers
9k views

Modifying Dijkstra's algorithm for edge weights drawn from range $[1,…,K]$

Suppose I have a directed graph with edge weights drawn from range $[1,\dots, K]$ where $K$ is constant. If I'm trying to find the shortest path using Dijkstra's algorithm, how can I modify the ...
7
votes
3answers
19k views

Why is the A* search heuristic optimal even if it underestimates costs?

A* search finds optimal solution to problems as long as the heuristic is admissible which means it never overestimates the cost of the path to the from any given node (and consistent but let us focus ...
11
votes
1answer
11k views

Variant of the knapsack problem

How would you approach the knapsack problem in a dynamic programming situation if you now have to limit the number of item in the knapsack by a constant $p$ ? This is the same problem (max weight of $...
28
votes
4answers
5k views

How to determine likely connections in a social network?

I am curious in determining an approach to tackling a "suggested friends" algorithm. Facebook has a feature in which it will recommended individuals to you which it thinks you may be acquainted with. ...
21
votes
1answer
977 views

How many shortest distances change when adding an edge to a graph?

Let $G=(V,E)$ be some complete, weighted, undirected graph. We construct a second graph $G'=(V, E')$ by adding edges one by one from $E$ to $E'$. We add $\Theta(|V|)$ edges to $G'$ in ...
14
votes
1answer
7k views

Randomized Selection

The randomized selection algorithm is the following: Input: An array $A$ of $n$ (distinct, for simplicity) numbers and a number $k\in [n]$ Output: The the "rank $k$ element" of $A$ (i.e., the one in ...
13
votes
1answer
517 views

Finding optimal sequence of questions to minimize total student time

Suppose there is a tutorial session at a university. We have a set of $k$ questions $Q = \{ q_1 \ldots q_k \}$ and a set of $n$ students $S = \{ s_1 \ldots s_n \}$. Each student has a doubt in a ...
12
votes
2answers
2k views

Tiling an orthogonal polygon with squares

Given an orthogonal polygon (a polygon whose sides are parallel to the axes), I want to find the smallest set of interior-disjoint squares, whose union equals the polygon. I found several references ...
11
votes
2answers
7k views

PTAS definition vs. FPTAS

From what I read in the ...
11
votes
2answers
4k views

Dynamic programming with large number of subproblems

Dynamic programming with large number of subproblems. So I'm trying to solve this problem from Interview Street: Grid Walking (Score 50 points) You are situated in an $N$-dimensional grid at ...
24
votes
7answers
19k views

Algorithm to distribute items “evenly”

I'm searching for an algorithm to distribute values from a list so that the resulting list is as "balanced" or "evenly distributed" as possible (in quotes because I'm not sure these are the best ways ...
15
votes
3answers
5k views

Brzozowski's algorithm for DFA minimization

Brzozowski's DFA minimization algorithm builds a minimal DFA for DFA $G$ by: reversing all the edges in $G$, making the initial state an accept state, and the accept states initial, to get an NFA $N&#...
12
votes
3answers
2k views

Is there an efficient test for if an NFA accepts a subset of another NFA?

So, I know that testing if a regular language $R$ is a subset of regular language $S$ is decidable, since we can convert them both to DFAs, compute $R \cap \bar{S}$, and then test if this language is ...
9
votes
2answers
11k views

Branch and Bound explanation

I have a test about the branch and bound algorithm. I understand theoretically how this algorithm works but I couldn't find examples that illustrates how this algorithm can be implemented practically. ...
6
votes
1answer
792 views

Explaination for Variation of Boyer-Moore Majority voting algorithm

Boyer-Moore's majority vote algorithms can be used to determine the majority element in a linear time and constant space. The intuition behind finding the majority element is understandable as it ...
6
votes
4answers
2k views

Why is not known whether integer factorization can be done in polynomial time knowing how to do primality tests efficiently?

First of all, I have just started studying computer science by myself and maybe I just need some clarification of what "polynomial time" means regarding the time complexity of an algorithm and ...
5
votes
1answer
1k views

Finding shortest paths in undirected graphs with possibly negative edge weights

The book "Algorithms" by Robert Sedgewick and Kevin Wayne hinted that (see the quote below) there are efficient algorithms for finding shortest paths in undirected graphs with possibly negative edge ...
27
votes
4answers
2k views

How to find a superstar in linear time?

Consider directed graphs. We call a node $v$ superstar if and only if no other node can be reached from it, but all other nodes have an edge to $v$. Formally: $\qquad \displaystyle $v$ \text{ ...
15
votes
1answer
506 views

Constructing inequivalent binary matrices

I am trying to construct all inequivalent $8\times 8$ matrices (or $n\times n$ if you wish) with elements 0 or 1. The operation that gives equivalent matrices is the simultaneous exchange of the i and ...
11
votes
3answers
6k views

Understanding an algorithm for the gas station problem

In the gas station problem we are given $n$ cities $\{ 0, \ldots, n-1 \}$ and roads between them. Each road has length and each city defines price of the fuel. One unit of road costs one unit of fuel. ...
9
votes
3answers
21k views

Big O: Nested For Loop With Dependence

I was given a homework assignment with Big O. I'm stuck with nested for loops that are dependent on the previous loop. Here is a changed up version of my homework question, since I really do want to ...
8
votes
0answers
157 views

Practical algorithms for the disjoint paths problem

Given an undirected graph $G$ and two pairs of vertices $(s_1, t_1), (s_2, t_2)$, the disjoint paths problem (DPP) asks for two vertex-disjoint paths, one from $s_1$ to $t_1$ and the other from $...