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,066
questions
197
votes
3
answers
26k
views
Is there a system behind the magic of algorithm analysis?
There are lots of questions about how to analyze the running time of algorithms (see, e.g., runtime-analysis and algorithm-analysis). Many are similar, for instance those asking for a cost analysis ...
- 72.8k
101
votes
3
answers
35k
views
How does one know which notation of time complexity analysis to use?
In most introductory algorithm classes, notations like $O$ (Big O) and $\Theta$ are introduced, and a student would typically learn to use one of these to find the time complexity.
However, there are ...
- 1,323
142
votes
5
answers
207k
views
How to convert finite automata to regular expressions?
Converting regular expressions into (minimal) NFA that accept the same language is easy with standard algorithms, e.g. Thompson's algorithm. The other direction seems to be more tedious, though, and ...
- 72.8k
40
votes
5
answers
120k
views
How to come up with the runtime of algorithms? [duplicate]
I've not gone much deep into CS. So, please forgive me if the question is not good or out of scope for this site.
I've seen in many sites and books, the big-O notations like $O(n)$ which tell the ...
- 523
86
votes
6
answers
22k
views
How can we assume that basic operations on numbers take constant time?
Normally in algorithms we do not care about comparison, addition, or subtraction of numbers -- we assume they run in time $O(1)$. For example, we assume this when we say that comparison-based sorting ...
user742
50
votes
2
answers
9k
views
What is the difference between an algorithm, a language and a problem?
It seems that on this site, people will often correct others for confusing "algorithms" and "problems." What are the difference between these? How do I know when I should be considering algorithms and ...
- 30k
52
votes
6
answers
7k
views
Dealing with intractability: NP-complete problems
Assume that I am a programmer and I have an NP-complete problem that I need to solve it. What methods are available to deal with NPC problems? Is there a survey or something similar on this topic?
- 621
36
votes
6
answers
15k
views
Differences and relationships between randomized and nondeterministic algorithms?
What differences and relationships are between randomized algorithms and nondeterministic algorithms?
From Wikipedia
A randomized algorithm is an algorithm which employs a degree of
randomness ...
- 4,985
57
votes
4
answers
9k
views
Why polynomial time is called "efficient"?
Why in computer science any complexity which is at most polynomial is considered efficient?
For any practical application(a), algorithms with complexity $n^{\log n}$ are way faster than algorithms ...
- 20.8k
40
votes
7
answers
4k
views
Explaining the relevance of asymptotic complexity of algorithms to practice of designing algorithms
In algorithms and complexity we focus on the asymptotic complexity of algorithms, i.e. the amount of resources an algorithm uses as the size of the input goes to infinity.
In practice, what is ...
- 22.4k
387
votes
12
answers
350k
views
Why is quicksort better than other sorting algorithms in practice?
In a standard algorithms course we are taught that quicksort is $O(n \log n)$ on average and $O(n^2)$ in the worst case. At the same time, other sorting algorithms are studied which are $O(n \log n)$ ...
- 5,555
14
votes
2
answers
17k
views
When can I use dynamic programming to reduce the time complexity of my recursive algorithm?
Dynamic programming can reduce the time needed to perform a recursive algorithm. I know that dynamic programming can help reduce the time complexity of algorithms. Are the general conditions such that ...
- 141
36
votes
4
answers
5k
views
What is dynamic programming about?
Sorry in advance if this question sounds dumb...
As far as I know, building an algorithm using dynamic programming works this way:
express the problem as a recurrence relation;
implement the ...
- 463
16
votes
4
answers
5k
views
Algorithms computing if a number is a multiple of 3
When doing mental calculus one can do:
Given an integer k, sum all the digits (in base 10),
and if the result is a multiple of 3, then k is a multiple of 3.
Do you know of any algorithm working ...
- 401
48
votes
4
answers
67k
views
Longest path in an undirected tree with only one traversal
There is this standard algorithm for finding longest path in undirected trees using two depth-first searches:
Start DFS from a random vertex $v$ and find the farthest vertex from it; say it is $v'$.
...
- 1,319
23
votes
3
answers
4k
views
Converting (math) problems to SAT instances
What I want to do is turn a math problem I have into a boolean satisfiability problem (SAT) and then solve it using a SAT Solver. I wonder if someone knows a manual, guide or anything that will help ...
- 415
14
votes
2
answers
10k
views
Algorithm to determine whether two regexes are equivalent
Given two arbitrary regular expressions, is there an "efficient" algorithm to determine whether they match the same set of strings?
More generally, can we compute the size of the intersection of the ...
13
votes
4
answers
5k
views
Is there a method for automatic runtime analysis of algorithms?
I am wondering, is there a method for automatic runtime analysis that works at least on a relevant subset of algorithms (algorithms that can be analyzed)?
I googled "Automatic algorithm analysis" ...
- 185
19
votes
3
answers
3k
views
Why use comparisons instead of runtime for comparing two algorithms?
I notice that in a few CS research papers, to compare the efficiency of two algorithms, the total number of key comparison in the algorithms is used rather than the real computing times themselves. ...
- 361
3
votes
3
answers
8k
views
Iterative and/or tail-recursive implementations of merge sort?
I recently learned how to implement merge-sort, using a standard recursive algorithm. Can the algorithm be implemented in a way that allows for a tail-recursive implementation? Can it be implemented ...
- 277
110
votes
2
answers
81k
views
Quicksort Partitioning: Hoare vs. Lomuto
There are two quicksort partition methods mentioned in Cormen:
(the argument A is the array, and [p, r] is the range, inclusive,...
- 2,931
36
votes
6
answers
18k
views
Uniform sampling from a simplex
I am looking for an algorithm to generate an array of N random numbers, such that the sum of the N numbers is 1, and all numbers lie within 0 and 1. For example, N=3, the random point (x, y, z) should ...
- 463
21
votes
2
answers
6k
views
How to describe algorithms, prove and analyse them?
Before reading The Art of Computer Programming (TAOCP), I have not considered these questions deeply. I would use pseudo code to describe algorithms, understand them and estimate the running time only ...
- 621
13
votes
9
answers
2k
views
What exactly is an algorithm?
I know that this may sound a bit out of the box, in fact i used to always think inside the box, but recently i've been thinking, possibly because computer science provides an high degree of freedom, ...
- 391
43
votes
3
answers
21k
views
Deciding on Sub-Problems for Dynamic Programming
I have used the technique of dynamic programming multiple times however today a friend asked me how I go about defining my sub-problems, I realized I had no way of providing an objective formal answer....
- 1,490
30
votes
1
answer
13k
views
How hard is counting the number of simple paths between two nodes in a directed graph?
There is an easy polynomial algorithm to decide whether there is a path between two nodes in a directed graph (just do a routine graph traversal with, say, depth-first-search).
However it seems that, ...
- 1,389
9
votes
3
answers
5k
views
How to develop an $O(N)$ algorithm solve the 2-sum problem?
Given an sorted array of integers, I want to find the number of pairs that sum to $0$. For example, given $\{-3,-2,0,2,3,4\}$, the number of pairs sum to zero is $2$.
Let $N$ be the number of ...
- 291
6
votes
2
answers
4k
views
Does Ford-Fulkerson always produce the left-most min-cut
When using Ford-Fulkerson to find max-flow between s and t, the exact choice of flow-graph depends on which paths are found.
However, if you then use the left-over residual graph to produce a min-cut ...
- 456
5
votes
2
answers
2k
views
How fast can we identifiy almost-duplicates in a list of strings?
I'm having trouble figuring out the upper bound running time for this scenario:
Input:
$N$ number of strings
$M$ upper bound of string length
$T$ threshold for edit distance (2 strings with a ...
- 431
4
votes
1
answer
580
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 ...
- 153
102
votes
5
answers
10k
views
What are the reasons to learn different algorithms / data structures serving the same purpose?
I have been wondering about this question since I was an undergraduate student.
It is a general question but I will elaborate with examples below.
I have seen a lot of algorithms - for example, for ...
- 1,210
31
votes
1
answer
10k
views
Which combinations of pre-, post- and in-order sequentialisation are unique?
We know post-order,
post L(x) => [x]
post N(x,l,r) => (post l) ++ (post r) ++ [x]
and pre-order
...
- 72.8k
9
votes
1
answer
8k
views
Finding the k-shortest path between two nodes
Given a weighted digraph $G=V,E$, and a weight function, $d(u,v)$, one can normally use Dijkstra's algorithm to obtain the shortest path. What I am interested in, is how to obtain the $2^{nd}$-...
- 6,211
5
votes
1
answer
2k
views
Algorithm to find maximum number of floors you can check with N eggs and D maximum drops
Question: You are given access to a multistory building. You have N eggs and are allowed D maximum drops from their window.
Rules: If a egg is dropped from window of floor F and it breaks, it will ...
- 400
139
votes
3
answers
50k
views
BIT: What is the intuition behind a binary indexed tree and how was it thought about?
A binary indexed tree has very less or relatively no literature as compared to other data structures. The only place where it is taught is the topcoder tutorial. Although the tutorial is complete in ...
- 1,565
131
votes
15
answers
16k
views
How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect
To try to test whether an algorithm for some problem is correct, the usual starting point is to try running the algorithm by hand on a number of simple test cases -- try it on a few example problem ...
D.W.♦
- 164k
51
votes
8
answers
79k
views
The math behind converting from any base to any base without going through base 10?
I've been looking into the math behind converting from any base to any base. This is more about confirming my results than anything. I found what seems to be my answer on mathforum.org but I'm still ...
- 623
50
votes
3
answers
80k
views
Why does Dijkstra's algorithm fail on a negative weighted graphs? [duplicate]
I know this is probably very basic, I just can't wrap my head around it.
We recently studied about Dijkstra's algorithm for finding the shortest path between two vertices on a weighted graph.
My ...
- 1,219
35
votes
5
answers
9k
views
Enumerate all non-isomorphic graphs of a certain size
I'd like to enumerate all undirected graphs of size $n$, but I only need one instance of each isomorphism class. In other words, I want to enumerate all non-isomorphic (undirected) graphs on $n$ ...
D.W.♦
- 164k
29
votes
4
answers
44k
views
The time complexity of finding the diameter of a graph
What is the time complexity of finding the diameter of a graph
$G=(V,E)$?
${O}(|V|^2)$
${O}(|V|^2+|V| \cdot |E|)$
${O}(|V|^2\cdot |E|)$
${O}(|V|\cdot |E|^2)$
The diameter of a ...
- 2,193
25
votes
1
answer
7k
views
How to prove correctness of a shuffle algorithm?
I have two ways of producing a list of items in a random order and would like to determine if they are equally fair (unbiased).
The first method I use is to construct the entire list of elements and ...
- 1,538
22
votes
4
answers
4k
views
Sorting algorithms which accept a random comparator
Generic sorting algorithms generally take a set of data to sort and a comparator function which can compare two individual elements. If the comparator is an order relation¹, then the output of the ...
- 1,538
20
votes
1
answer
20k
views
Find the Simple Cycles in a Directed Graph
This problem, for me, looks very interesting. It was about to find a simple cycle (i.e. cycle where are not repeat nodes) in a directed graph.
My solution is going like this, i.e, this graph is a ...
- 2,219
18
votes
3
answers
4k
views
Algorithm books on a range of topics
I've been tasked with building a library of books on algorithms for our small company (about 15 people). The budget is more than 5k, but certainly less than 10k, so I can buy a fair number of books. ...
- 189
15
votes
1
answer
7k
views
Are all MST minimum spanning trees reachable by Kruskal and Prim?
I believe this is true but have not been able to get a formal proof for either. But is it true that any minimum spanning tree is reachable by applying Kruskal's algorithm? Similarly, is this true for ...
- 253
14
votes
2
answers
11k
views
Why can't we find shortest paths with negative weights by just adding a constant so that all weights are positive?
I'm currently reading introduction to algorithms and came by Johnson’s algorithm that depends on making sure that all paths are positive.
the algo depends on finding a new weight function (w') that ...
- 243
13
votes
2
answers
21k
views
7
votes
1
answer
7k
views
Find a 3-colouring using the 3-colourability decision problem
I was learning about NP problems. I read that for many problems, like Clique, we can easily convert its decision problem to derive a solution of search problem. (For Clique problem, you only need to ...
- 71
2
votes
3
answers
2k
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
...
- 111
42
votes
9
answers
64k
views
Algorithm to find diameter of a tree using BFS/DFS. Why does it work?
This link provides an algorithm for finding the diameter of an undirected tree using BFS/DFS. Summarizing:
Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u ...
- 531