Tag Info

Hot answers tagged algorithms

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

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
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

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
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
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
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
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

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

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
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

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

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....
• 143k

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

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
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 ...
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
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 ...
• 143k

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 ...
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 ...
• 143k

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
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
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

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
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 ...
• 143k
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

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
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