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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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....
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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-...
user avatar
  • 22.1k
34 votes

Why can we assume an algorithm can be represented as a bit string?

I can't resist... ...
user avatar
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. ...
user avatar
  • 349

Only top scored, non community-wiki answers of a minimum length are eligible