165 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 ...
David Richerby's 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 ...
David Richerby's user avatar
129 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 ...
Pseudonym's user avatar
  • 22.1k
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 ...
fade2black's user avatar
  • 9,837
71 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 ...
Andrej Bauer's user avatar
  • 30.4k
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 ...
gnasher729's user avatar
59 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 ...
l8Again's user avatar
  • 691
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.'s user avatar
  • 159k
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 ...
Raphael's user avatar
  • 72.4k
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 ...
Yuval Filmus's 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 ...
Gilles 'SO- stop being evil''s 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 ...
Daniel F's user avatar
  • 619
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.'s user avatar
  • 159k
43 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 ...
Mario Cervera's user avatar
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 ...
Ariel's user avatar
  • 13.4k
37 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 ...
Yuval Filmus's user avatar
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 ...
Josh's user avatar
  • 466
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.'s user avatar
  • 159k
35 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 ...
Pål GD's user avatar
  • 16.1k
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-...
Juho's user avatar
  • 22.6k
34 votes

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

I can't resist... ...
leftaroundabout's user avatar
33 votes

What is this data structure/concept where a plot of points defines a partition to a space

What you described is Voronoi diagram. Here is an excerpt from Wikipedia. In the simplest case, shown in the first picture, we are given a finite set of points ${p_1, \cdots, p_n}$ in the Euclidean ...
John L.'s user avatar
  • 39k
31 votes
Accepted

Find a polynomial in two or three queries

You can determine the polynomial using two queries. First query the polynomial at $x=1$ to get an upper bound $M$ on the value of the coefficients. Now query the polynomial at $x > M$ of your ...
Yuval Filmus's user avatar
31 votes
Accepted

One element that differs in two arrays. How to find it efficiently?

I see four main ways to solve this problem, with different running times: $O(n^2)$ solution: this would be the solution that you propose. Note that, since the arrays are unsorted, deletion takes ...
Mario Cervera's user avatar
30 votes
Accepted

Is there a "Standard Algorithm" language, as used in academic papers?

No. There is no universal standard. There are some conventions that have become more popular over time, through gradual evolution. A good starting place to look would be to look at the pseudocode ...
D.W.'s user avatar
  • 159k
30 votes
Accepted

Is there a faster than O(n^2) way to compute a vector of length n from another vector and an n by n matrix?

That's not possible. You have to read in the entire $B$ matrix to determine the correct answer, which fundamentally requires $O(n^2)$ time.
D.W.'s user avatar
  • 159k
30 votes
Accepted

If I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, how?

For 9x9 Sudoku, no. It is finite so can be solved in $O(1)$ time. But if you had a solver for $n^2 \times n^2$ Sudoku, that worked for all $n$ and all possible partial boards, and ran in polynomial ...
D.W.'s user avatar
  • 159k
30 votes
Accepted

Computing exam averages in less than linear time

To compute the exact mean (no confidence interval or estimate) of each exam, you must at least observe every student's exam score. This takes $\Omega(r)$ per exam. There are $c$ exams you must do this ...
ryan's user avatar
  • 4,511

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