203
Intuitively, you can think of a binary indexed tree as a compressed representation of a binary tree that is itself an optimization of a standard array representation. This answer goes into one possible derivation.
Let's suppose, for example, that you want to store cumulative frequencies for a total of 7 different elements. You could start off by writing ...
166
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 definition is. If zero-weighted edges are useful to you, then use them; just make sure your readers know that's what you're doing.
The reason you don't usually ...
151
Translating Code to Mathematics
Given a (more or less) formal operational semantics you can translate an algorithm's (pseudo-)code quite literally into a mathematical expression that gives you the result, provided you can manipulate the expression into a useful form. This works well for additive cost measures such as number of comparisons, swaps, statements,...
142
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 integer coefficients have integer solutions (Hilbert's tenth problem).
Is Turing Machine “by definition” the most powerful machine?
No. We can dream up an ...
128
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 undergraduate level has some feature which makes it better for some applications than others.
Let's take sorting as an example, since everyone is familiar with ...
122
Your model of what you do mentally is incorrect. In fact, you operate in two steps:
Eliminate all points that are too far, in $O(1)$ time.
Measure the $m$ points that are about as close, in $\Theta(m)$ time.
If you've played games like pétanque (bowls) or curling, this should be familiar — you don't need to examine the objects that are very far from the ...
answered Mar 17 '14 at 12:28
Gilles 'SO- stop being evil'
40.4k7 gold badges108 silver badges171 bronze badges
113
Pedagogical Dimension
Due to its simplicity Lomuto's partitioning method might be easier to implement. There is a nice anecdote in Jon Bentley's Programming Pearl on Sorting:
“Most discussions of Quicksort use a partitioning scheme based on two approaching indices [...] [i.e. Hoare's]. Although the basic idea of that scheme is straightforward, I have ...
87
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 $n$ as a sum of $d_i$:s with as few coins as possible.
A naive approach is to use the largest possible coin first,
and greedily produce such a sum.
For ...
87
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 respect to their asymptotic behavior.
For example
$$\log_{10}n = \frac{\log_{2}n}{\log_{2}10} = C \log_{2}{n}$$ where
$C = \frac{1}{\log_{2}10}$.
So $\log_{10}n$ ...
85
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 travelled by fastPointer before meeting $=(x + y + z) + y = x + 2y + z$
Since fastPointer travels with double the speed of slowPointer, and time is constant for both when both pointers reach the ...
82
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 comparisons to cut the search space into three parts. Now if you do the math, you can observe that:
$$ 2 \cdot \log_3(n) + O(1) = 2 \cdot \frac{\log(2)}{\log(3)}...
77
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 place in a textbook. Make no sudden movements. Put the book down. Step away from the book.
We say that the "order of growth" of the sequential search ...
69
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 make the concepts you use precise. What is a problem? What is an algorithm? What is a machine? You may think these are obvious, but a good part of the 1920's and ...
68
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 test equality of two strings. One of the programs turned in by a student was the following:
issame := (string1.length = string2.length);
if issame then
for ...
67
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 base is important. In base 2 you would have just $O(n)$, in base 10 it's about $O(n^{0.3010})$.
56
This seems a very basic question to me, so excuse me if I lecture you a bit. The most important point for you to learn here is that a number is not its digit representation. A number is an abstract mathematical object, whereas its digit representation is a concrete thing, namely a sequence of symbols on a paper (or a sequence of bits in compute memory, or a ...
54
For simplicity, I'll begin by only considering "decision" problems, which have a yes/no answer. Function problems work roughly the same way, except instead of yes/no, there is a specific output word associated with each input word.
Language: a language is simply a set of strings. If you have an alphabet, such as
$\Sigma$, then $\Sigma^*$ is the set of all ...
52
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 machine models (TM, RAM, PRAM,...), average-vs-worst-case as well as amortization considerations to weigh against each other, there are often also functional ...
52
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., a string over the alphabet $\{0,1\}^*$. That's one example encoding.
51
The best algorithm that is known is to express the factorial as a product of prime powers. One can quickly determine the primes as well as the right power for each prime using a sieve approach. Computing each power can be done efficiently using repeated squaring, and then the factors are multiplied together. This was described by Peter B. Borwein, On the ...
51
Consider the triangle graph with unit weights - it has three vertices $x,y,z$, and all three edges $\{x,y\},\{x,z\},\{y,z\}$ have weight $1$. The shortest path between any two vertices is the direct path, but if you put all of them together you get a triangle rather than a tree. Every collection of two edges forms a minimum spanning tree in this graph, yet ...
50
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 there is no need to specify the base of a logarithm when using asymptotic notation.
49
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 not terminate on a stack overflow. Pseudocode is not formally defined, but the idea is that it does what is says on the tin. If the code doesn't say "terminate ...
answered Jun 15 '18 at 7:25
Gilles 'SO- stop being evil'
40.4k7 gold badges108 silver badges171 bronze badges
46
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 plausible due to the way it is sketched).
What you really want to prove is (using the same variables as described in the diagram in the accepted answer above):
$z ...
46
In general terms, there are the $O(n^2)$ sorting algorithms, such as insertion sort, bubble sort, and selection sort, which you should typically use only in special circumstances; Quicksort, which is worst-case $O(n^2)$ but quite often $O(n\log n)$ with good constants and properties and which can be used as a general-purpose sorting procedure; the $O(n\log n)...
46
You are right that the two algorithms of Dijkstra (shortest paths from a single start node) and Prim (minimal weight spanning tree starting from a given node) have a very similar structure. They are both greedy (take the best edge from the present point of view) and build a tree spanning the graph.
The value they minimize however is different. Dijkstra ...
45
The reason is that the data has been put in a "data structure" optimized for this query and that the preprocessing time in preparing the graph should be included in your measured times which is proportional to the number of dots, giving a O(n) complexity right there.
If you put the coordinates in a table listing X and Y coordinates of each point you would ...
45
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 about turing machines, the programs they run are a linear list of operations/instructions, there is no reason these cannot be represented as bits/bytes.
44
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 specifies things like the time it takes to perform each basic operation (is an array lookup $O(\log n)$ time or $O(1)$ time?). The running time of the algorithm ...
43
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 if you want to write a program that tackles serious problems you need it.
In your specific case, your example of finding connected components might have worked ...
Only top voted, non community-wiki answers of a minimum length are eligible
