Introduction algorithm is incorrect, also implementation is missing from

[GoogleCodeExporter]

I would be interested in an Errata sheet. I just got the book today, and there 
seems to be an error in the introduction. Page 2-3 gives the following 
algorithm description for the introduction problem (stocks, maximize buy to 
sell profit):  "Iterate through 'S', keeping track of the minimum element 'm' 
seen thus far. If the difference of the current element and 'm' is greater than 
the maximum profit recorded so far, update the maximum profit. This algorithm 
performs a constant amount of work per array element, leading to an O(n) time 
complexity."

I believe there's a defect in this method, and that this problem cannot be 
simplified to O(n) time complexity. It is time-consuming to explain where I'm 
coming from, so instead of justifying my claim, I will just ask if you could 
reconsider the solution.

Also, the implementation is missing. For this problem, the book says "Working 
code is presented in Solution 3.3 on Page 181" -- which is not true. Solution 
3.3 on p181 exists, but is talking about 3-dimensional array and robot battery.

Original issue reported on code.google.com by mpatel.c...@gmail.com on 5 Apr 2013 at 5:39

[GoogleCodeExporter]

Hey Mpatel,

Thanks for your reporting. In fact, Problem 3.3 is identical to the stock price 
problem. We did this before because the stock price problem is kind too 
well-known and we wanted to remodel it such that readers who already know the 
stock price problem still pay sometime to uncover the true formulation of this 
problem. Please take a look at the problem part of Problem 3.3, and you will 
notice that we said Problem 3.3 is the another application of the stock price 
problem. The link to the code is at 
https://code.google.com/p/elements-of-programming-interviews/source/browse/trunk
/Robot_battery.cpp.

About the errata, we do have an internal use one which tracks all bugs we found 
but it is not organized very well. From what you got, it should be the most 
up-to-date one so most of that will probably not be useful to you.

Please let us know if you have any problem, and we are glad to help you.

Tsung-Hsien

Original comment by TsungHsi...@gmail.com on 5 Apr 2013 at 6:16

[GoogleCodeExporter]

I see now that the robot battery problem is intended to be the same as the 
stock trading problem. However, the robot battery problem is an 
over-simplification of the stock problem. For stocks, you must buy before 
selling. The robot does not have such a constraint. The stock problem cannot be 
solved in O(n) time.

Original comment by mpatel.c...@gmail.com on 5 Apr 2013 at 7:24

[GoogleCodeExporter]

Consider that for the stocks, the largest delta of low-to-high points occurs in 
the first half of the array, but the lowest point is in the second-half of the 
array (and has a smaller delta to the next high).  

The algorithm needs to figure out which delta to take, the one in the left-half 
or the right-half.

The robot battery algorithm does not remember the value of the left-half (which 
is actually the best).  It thinks the minimum is the one in the right-half, and 
greedily takes that to be the new "min". Bad idea.

Original comment by mpatel.c...@gmail.com on 5 Apr 2013 at 7:31

[GoogleCodeExporter]

Hey Mpatel,

The robot battery problem is the same as the stock price problem. Because a 
high point appearing before a low point does not make effect to the battery 
volume; however, a low point appearing before high point may make effect to the 
battery since we need the use the energy in the batter to conquer the height 
difference. These two scenarios are identical to the stock price problem; we 
don't care about a high price before low price since we won't sell on that, and 
we do care a low price before high price since we might gain more.

Original comment by TsungHsi...@gmail.com on 5 Apr 2013 at 7:38

[GoogleCodeExporter]

Tsung-Hsien,  
Please consider the scenario I listed above, where the left-half of the array 
is better than the right-half (but the right-half has the lowest point). Do you 
still think the robot algorithm works in this scenario?
-Mitesh

Original comment by mpatel.c...@gmail.com on 5 Apr 2013 at 7:42

[GoogleCodeExporter]

Hey Mitesh,

Let's consider a small example A = <3, 10, 1, 5> where the first-half contains 
<3, 10> and the second-half contains <1, 5>. We can see that the first-half 
contains the largest delta, which is 10 - 3 = 7, and the second-half contains 
the lowest point, which is 1.

Now, let's run the algorithm in 
https://code.google.com/p/elements-of-programming-interviews/source/browse/trunk
/Robot_battery.cpp step by step, we focus on the variable values in line 15 and 
16, which are capacity (the answer) and min_height:

1. Process A[0], which is 3: capacity = max(0, 3 - 
numeric_limits<HeightType>::max()) = 0, min_height = 
min(numeric_limits<HeightType>::max(), 3) = 3.
2. Process A[1], which is 10: capacity = max(0, 10 - 3) = 7, min_height = 
min(3, 10) = 3.
3. Process A[2], which is 1: capacity = max(7, 1 - 3) = 7, min_height = min(3, 
1) = 1.
4. Process A[3], which is 5: capacity = max(7, 5 - 1) = 7, min_height = min(1, 
5) = 1.

From the above trace, you probably already noticed the core of this algorithm 
is that every height only needs to care about the minimum which is appeared 
before itself, which we use min_height to keep. By keeping min_height, we 
basically examine all potential pair without explicitly examining all pairs 
(n^2). 

Original comment by TsungHsi...@gmail.com on 5 Apr 2013 at 7:59

[GoogleCodeExporter]

ahh, you have convinced me that the robot algorithm works. My mistake. Thank 
you for your time in working it out.

Original comment by mpatel.c...@gmail.com on 5 Apr 2013 at 8:22

[GoogleCodeExporter]

Hey Mitesh,

Not a problem! Thanks for your report, and we probably will rewrite part of the 
solution to make it more clear.

Original comment by TsungHsi...@gmail.com on 5 Apr 2013 at 4:42

• Changed state: Fixed