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.
11,101
questions
379
votes
12
answers
343k
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,455
193
votes
3
answers
25k
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 ...
- 71.7k
137
votes
2
answers
46k
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,545
137
votes
4
answers
201k
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 ...
- 71.7k
132
votes
14
answers
21k
views
Why can I look at a graph and immediately find the closest point to another point, but it takes me O(n) time through programming?
Let me clarify:
Given a scatterplot of some given number of points n, if I want to find the closest point to any point in the plot mentally, I can immediately ignore most points in the graph, ...
- 1,417
125
votes
15
answers
15k
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.♦
- 152k
108
votes
2
answers
78k
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,861
100
votes
3
answers
34k
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,313
99
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,180
85
votes
6
answers
21k
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
84
votes
8
answers
59k
views
Graph searching: Breadth-first vs. depth-first
When searching graphs, there are two easy algorithms: breadth-first and depth-first (Usually done by adding all adjactent graph nodes to a queue (breadth-first) or stack (depth-first)).
Now, are ...
- 965
76
votes
8
answers
65k
views
Floyd's Cycle detection algorithm | Determining the starting point of cycle
I am seeking help understanding Floyd's cycle detection algorithm. I have gone through the explanation on wikipedia (http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare)
I can see how the ...
- 863
76
votes
4
answers
72k
views
What is tail recursion?
I know the general concept of recursion. I came across the concept of tail recursion while studying the quicksort algorithm. In this video of quick sort algorithm from MIT at 18:30 seconds the ...
- 1,181
71
votes
4
answers
17k
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 ...
- 71.7k
70
votes
4
answers
110k
views
Find median of unsorted array in $O(n)$ time
To find the median of an unsorted array, we can make a min-heap in $O(n\log n)$ time for $n$ elements, and then we can extract one by one $n/2$ elements to get the median. But this approach would take ...
- 821
69
votes
10
answers
111k
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 ...
- 1,183
68
votes
9
answers
7k
views
Are there any problems that get easier as they increase in size?
This may be a ridiculous question, but is it possible to have a problem that actually gets easier as the inputs grow in size? I doubt any practical problems are like this, but maybe we can invent a ...
- 913
66
votes
3
answers
15k
views
In-place algorithm for interleaving an array
You are given an array of $2n$ elements
$$a_1, a_2, \dots, a_n, b_1, b_2, \dots b_n$$
The task is to interleave the array, using an in-place algorithm such that the resulting array looks like
$$...
- 6,191
64
votes
8
answers
5k
views
Algorithmic intuition for logarithmic complexity
I believe I have a reasonable grasp of complexities like $\mathcal{O}(1)$, $\Theta(n)$ and $\Theta(n^2)$.
In terms of a list, $\mathcal{O}(1)$ is a constant lookup, so it's just getting the head of ...
- 1,421
64
votes
8
answers
200k
views
What is a the fastest sorting algorithm for an array of integers?
I have come across many sorting algorithms during my high school studies. However, I never know which is the fastest (for a random array of integers). So my questions are:
Which is the fastest ...
- 981
62
votes
7
answers
28k
views
Is a Turing Machine "by definition" the most powerful machine?
I agree that a Turing Machine can do "all possible mathematical problems". But that is because it is just a machine representation of an algorithm: first do this, then do that, finally output that.
...
61
votes
5
answers
13k
views
Is zero allowed as an edge's weight, in a weighted graph?
I am trying to write a script that generates random graphs and I need to know if an edge in a weighted graph can have the 0 value.
actually it makes sense that 0 could be used as an edge's weight, ...
- 729
58
votes
3
answers
29k
views
Why is binary search faster than ternary search?
Searching an array of $N$ elements using binary search takes, in the worst case $\log_2 N$ iterations because, at each step we trim half of our search space.
If, instead, we used 'ternary search', we'...
- 758
56
votes
4
answers
8k
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.6k
56
votes
3
answers
106k
views
What exactly is polynomial time?
I'm trying to understand algorithm complexity, and a lot of algorithms are classified as polynomial. I couldn't find an exact definition anywhere. I assume it is the complexity that is not exponential....
- 663
55
votes
5
answers
57k
views
Factorial algorithm more efficient than naive multiplication
I know how to code for factorials using both iterative and recursive (e.g. n * factorial(n-1) for e.g.). I read in a textbook (without been given any further ...
- 695
54
votes
5
answers
20k
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 ...
- 942
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
50
votes
12
answers
39k
views
How to verify number with Bob without Eve knowing?
You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write the question on a card which and give it to Eve who will take the card to Bob ...
- 4,037
49
votes
3
answers
79k
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,209
49
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 ...
- 29.5k
47
votes
2
answers
7k
views
Order of growth definition from Reynolds & Tymann
I am reading a book called Principles of Computer Science (2008), by Carl Reynolds and Paul Tymann (published by Schaum's Outlines).
The second chapter introduces algorithms with an example of a ...
- 581
47
votes
4
answers
64k
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,259
46
votes
8
answers
73k
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 ...
- 573
43
votes
3
answers
19k
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,470
42
votes
1
answer
10k
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:
...
- 1,316
41
votes
4
answers
10k
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 ...
- 829
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
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 ...
- 21.9k
40
votes
9
answers
59k
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 ...
- 511
39
votes
4
answers
53k
views
Algorithm that finds the number of simple paths from $s$ to $t$ in $G$
Can anyone suggest me a linear time algorithm that takes as input a directed acyclic graph $G=(V,E)$ and two vertices $s$ and $t$ and returns the number of simple paths from $s$ to $t$ in $G$.
I have ...
- 899
38
votes
4
answers
5k
views
How to measure "sortedness"
I'm wondering if there is a standard way of measuring the "sortedness" of an array? Would an array which has the median number of possible inversions be considered maximally unsorted? By that I mean ...
- 2,861
38
votes
2
answers
27k
views
Hash tables versus binary trees
When implementing a dictionary ('I want to look up customer data by their customer IDs'), the typical data structures used are hash tables and binary search trees. I know for instance that the C++ STL ...
- 9,006
38
votes
2
answers
14k
views
Is there a difference between top-down and bottom-up dynamic programming?
Is there a fundamental difference between top-down and bottom-up dynamic programming?
In particular, is there a problem which can be solved bottom-up but not top-down? Or is the bottom-up approach ...
- 783
37
votes
0
answers
630
views
Finding an $st$-path in a planar graph which is adjacent to the fewest number of faces
I am curious whether the following problems has been studied before, but wasn't able to find any papers about it:
Given a planar graph $G$, and two vertices $s$ and $t$, find an
$s$-$t$ path $P$ ...
- 371
36
votes
2
answers
15k
views
Why is the log in the big-O of binary search not base 2?
I am new to understanding computer science algorithms. I understand the process of the binary search, but I am having a slight misunderstanding with its efficiency.
In a size of $s = 2^n$ elements, ...
- 463
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
35
votes
7
answers
65k
views
Why is selection sort faster than bubble sort?
It is written on Wikipedia that "... selection sort almost always outperforms bubble sort and gnome sort." Can anybody please explain to me why is selection sort considered faster than bubble sort ...
- 491
35
votes
5
answers
8k
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.♦
- 152k
34
votes
6
answers
14k
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,775