166
votes
Accepted
Is zero allowed as an edge's weight, in a weighted graph?
Allowed by whom? There is no Central Graph Administration that decides what you can and cannot do. You can define objects in any way that's convenient for you, as long as you're clear about what the ...
- 80.4k
143
votes
Is a Turing Machine "by definition" the most powerful machine?
I agree that a Turing Machine can do "all the possible mathematical problems".
Well, you shouldn't, because it's not true. For example, Turing machines cannot determine if polynomials with ...
- 80.4k
128
votes
Accepted
What are the reasons to learn different algorithms / data structures serving the same purpose?
There's a textbook waiting to be written at some point, with the working title Data Structures, Algorithms, and Tradeoffs. Almost every algorithm or data structure which you're likely to learn at the ...
- 19.1k
96
votes
Floyd's Cycle detection algorithm | Determining the starting point of cycle
You can refer to "Detecting start of a loop in singly linked list", here's an excerpt:
Distance travelled by slowPointer before meeting $= x+y$
Distance ...
- 1,061
91
votes
Accepted
How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect
A common error I think is to use greedy algorithms, which is not always the correct approach, but might work in most test cases.
Example: Coin denominations, $d_1,\dots,d_k$ and a number $n$,
express ...
- 1,074
87
votes
Accepted
Why is the log in the big-O of binary search not base 2?
When you change the base of logarithm the resulting expression differs only by a constant factor which, by definition of Big-O notation, implies that both functions belong to the same class with ...
- 9,632
83
votes
Accepted
Why is binary search faster than ternary search?
If you apply binary search, you have $$\log_2(n)+O(1)$$ many comparisons. If you apply ternary search, you have $$ 2 \cdot \log_3(n) + O(1)$$ many comparisons, as in each step, you need to perform 2 ...
- 2,682
78
votes
Accepted
Order of growth definition from Reynolds & Tymann
The paragraph is wrong. Unfortunately, it looks exactly like the kind of thing that a student who does not understand the material would write as an answer to an exercise. This sort of nonsense has no ...
- 80.4k
73
votes
How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect
I immediately recalled an example from R. Backhouse (this might have been in one of his books). Apparently, he had assigned a programming assignment where the students had to write a Pascal program to ...
- 22.1k
70
votes
Is a Turing Machine "by definition" the most powerful machine?
You are not correct when you repeatedly make the statements about this or that being "just a tautology". So allow me to put your claims into a bit of historical context.
First of all, you need to ...
- 28.3k
68
votes
Accepted
Time complexity of an algorithm: Is it important to state the base of the logarithm?
It depends where the logarithm is. If it is just a factor, then it doesn't make a difference, because big-O or $\theta$ allows you to multiply by any constant.
If you take $O(2^{\log n})$ then the ...
- 25.4k
55
votes
Floyd's Cycle detection algorithm | Determining the starting point of cycle
I have seen the accepted answer as proof elsewhere too. However, while its easy to grok, it is incorrect. What it proves is
$x = z$ (which is obviously wrong, and the diagram just makes it seem ...
- 651
52
votes
Why can we assume an algorithm can be represented as a bit string?
You already have a representation of that function as text. Convert each character to a one-byte value using the ASCII encoding. Then the result is a sequence of bytes, i.e., a sequence of bits, i.e....
D.W.♦
- 143k
52
votes
What are the reasons to learn different algorithms / data structures serving the same purpose?
Aside from the fact that there are myriads of cost measures (running time, memory usage, cache misses, branch mispredictions, implementation complexity, feasibility of verification...) on myriads of ...
- 71k
50
votes
Time complexity of an algorithm: Is it important to state the base of the logarithm?
Because asymptotic notation is oblivious of constant factors, and any two logarithms differ by a constant factor, the base makes no difference: $\log_a n = \Theta(\log_b n)$ for all $a,b > 1$. So ...
- 270k
49
votes
Accepted
Will this program terminate for every Integer?
The correct answer is that this function does not terminate for all integers (specifically, it does not terminate on -1). Your friend is correct in stating that this is pseudocode and pseudocode does ...
45
votes
Accepted
Why can we assume an algorithm can be represented as a bit string?
The most naive and simple answer to your question is that the code provided (and compiled machine code) are in-fact represented as syntactic strings of {0,1}*. Additionally, since you are talking ...
- 609
44
votes
Accepted
Will hardware/implementation affect the time/space complexity of algorithms?
Sure. Certainly. Here's how to reconcile your discomfort.
When we analyze the running time of algorithms, we do it with respect to a particular model of computation. The model of computation ...
D.W.♦
- 143k
43
votes
Is it a problem to be a programmer with no knowledge about computational complexity?
Yes, I would say knowing something about computational complexity is a must for any serious programmer. So long as you are not dealing with huge data sets you will be fine not knowing complexity, but ...
39
votes
Accepted
Are there any problems that get easier as they increase in size?
No, it's not possible: at least, not in an asymptotic sense, where you require the problem to keep getting strictly easier, forever, as $n \to \infty$.
Let $T(n)$ be the best possible running time ...
D.W.♦
- 143k
38
votes
in O(n) time: Find greatest element in set where comparison is not transitive
The standard algorithm for finding a maximum still works. Start with $a_1$ and go over the elements, if you see a larger value, update the maximum to be that value. The reason this works is that every ...
- 13.2k
37
votes
Accepted
Why does n! have the least time?
The numbers in the table are not times; they're the rough sizes of the input $n$, for which the algorithm would take the amount of time in the column labels to run.
i.e. you'd need to give an ...
- 466
36
votes
Accepted
Are there any functions with Big O (Busy Beaver(n))?
The usual meaning of algorithm is a program that always halts. Under this definition, no algorithm has a running time of $\Theta(\mathit{BB}(n))$, or indeed $\Omega(\mathit{BB}(n))$. Indeed, such an ...
- 270k
36
votes
Residual Graph in Maximum Flow
The intuition behing the residual graph in the Maximum flow problem is very well presented in this lecture. The explanation goes as follows.
Suppose that we are trying to solve the maximum flow ...
- 3,454
36
votes
Accepted
Why there are no approximation algorithms for SAT and other decision problems?
Approximation algorithms are only for optimization problems, not for decision problems.
Why don't we define the approximation ratio to be the fraction of mistakes an algorithm makes, when trying to ...
D.W.♦
- 143k
35
votes
Accepted
Why do low fitness individuals have a chance to survive to the next generation?
The main idea is that by allowing suboptimal individuals to survive, you can switch from one "peak" in the evolutionary landscape to another through a sequence of small incremental mutations. On the ...
- 1,049
34
votes
Real life examples of negative weight edges in graphs
Distance between cities can't be negative, but if you are programming for an electric car, then a downhill road segment will regen, thus the energy used is negative. It is very important to take that ...
- 13.3k
34
votes
Accepted
Is there a name for the class of algorithms that are the most efficient for a particular task?
You can say that an algorithm is asymptotically optimal in such a case.
In general, people might also say that an algorithm is optimal in some other sense, like assuming some particular complexity-...
- 22.1k
34
votes
34
votes
How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect
The best example I ever came across is primality testing:
input: natural number p, p != 2
output: is p a prime or not?
algorithm: compute 2**(p-1) mod p. If result = 1 then p is prime else p is not.
...
- 349
Only top scored, non community-wiki answers of a minimum length are eligible