Proof That Algorithm doesn't exist, for book problem.?
Trying to improve my Java, I'm working through the book:
"Schaum's Outlines Data Structures With Java", as just private study for hobby reasons.
I'm working through the section on Recursion and I have come to this Question:
"Write and test a recursive function that returns the maximum among the first n elements of an array, using at most logn recursive calls.
Now I'm abysmal at maths, but I think this is impossible...
My reasoning runs thus:
The Set of Data is unsorted.
Therefore Each Element must be compared or checked at least once to see if it the maximum.
Therefore the best Algorithm must performn comparisons.
And is therefore of Order N O{n}.
The answer given in the book, is ridiculous, and must be some sort of typo as it would never compile in Java
Here is their Answer:
publicstaticdouble max(double[] a ,int n )
{
if( n == 1 )
{
return a[ 0 ];
}
int n1 = n/2;
int n2 = n - n1;
double m1 = max( a, n1 );
double m2 = max( a + n1, n2 );// That's just not Java
return ( m1 > m2 ? m1 : m2 );
}
Can someone point out if I am just an idiot, or am I missing something here?
The code appears to be incorrectly ported from C, and their math is incorrect.For bonus credit, rewrite the code as legal Java, and come up with the exact number of recursive calls made by this method.
double m2 = max( a + n1, n2 );// That's just not Java, but that was C
The answer given in your book is reasonable from the C programmer's point of view.
I tested two sets of unsorted integer(can be double) array. Both of them returned me the maximum element in 'logn' recursive call. All you have to do, convert the C concept to Java.
In C, if we have the following array:
int a[5]; /* C code */
The address of the array is '&a[0] ' or we can call it (a+0). When we will pass (a+0), then we are passing the whole content of the array. But, if we just pass (a+2), that means we are passing a 'sub-array' which starts from position 2 in the array.
For an example, if we have a set of unsorted integer array
a:9 105100 0
index:0 1234
f(a+0) means we are passing the whole array
9105 1000
f(a+2) means we are passing a sub-array
51000
Your recursive method is based on C. I don't blame the book. Because, the designers of Java are C programmers :) .
Good luck!
Not only was the code given not java, the question was poorly worded and you are correct that it is impossible as worded.
It will take on the order of N total calls to find the maximum. On the other hand, the method that they use limits the depth of the stack to logN calls, because each call is to a subproblem that is half the size of the previous problem.
This is an important consideration since it means that you can use a recursive procedure such as this one on an array with a million elements and it only requires about 20 nested calls. (You still do a million calls, but you only have at most about 20 unreturned calls at any time.)
I would agree that their wording didn't say that, but since stack consumption (maximum stack depth) is generally an important consideration in creating a recursive routine, that is no doubt what was intended in the problem.
Thanks for the answers people.
I really appreciate the clear explanations.
I did guess it was a "C" thing. and meant what buteForce said.
But as you can tell I am rubbish at Maths, and my reasoning was wrong.
I would guess that the extra operations required implementing this in java would probably make up for the savings made by this method.
I will "Suck it and see"
>
> It will take on the order of N total calls to find
> the maximum. On the other hand, the method that they
> use limits the depth of the stack to logN calls,
> because each call is to a subproblem that is half the
> size of the previous problem.
>
> This is an important consideration since it means
> that you can use a recursive procedure such as this
> one on an array with a million elements and it only
> requires about 20 nested calls. (You still do a
> million calls, but you only have at most about 20
> unreturned calls at any time.)
>
> I would agree that their wording didn't say that, but
> since stack consumption (maximum stack depth) is
> generally an important consideration in creating a
> recursive routine, that is no doubt what was intended
> in the problem
.
Thanks, that explained where I got confused.
Yes I am learning that recursive algorithms can easily generate a Stack Overflow.
After the above much appreciated help,
I recoded the problem in the following way:
But I obviously really really don't understand something about "How many Iterations" because by my count this takes approximately Twice as many
as the O{n} solution........
I restate: I'm **** at math...
/**
Based on the C code in previous message supposed to find
The max Element in an array in lgn operations.....
*/
private static int maxUpToLog( int[] a )
{
Recurse.currentIterations++;// Count the Iterations
// I check this after the method completes
// Base Case
if( a.length == 1 )
{
return a[ 0 ];
}
//Generic Case
// Divide The Array into two Halves
int n1 = a.length / 2;
int n2 = a.length - n1;
int[] left = new int[ n1 ];//The left Half
int[] right = new int[ n2 ];// the right half
for( int i = 0 ; i < n1 ; i ++ )
{
left[ i ] = a[ i ];
}
int pos = 0;
for( int j = n1 ; j < a.length ; j++ )
{
right[ pos ] = a[ j ];
pos++;
}
int leftMax = maxUpToLog( left );
int rightMax = maxUpToLog( right );
if( leftMax >= rightMax )
{
return leftMax;
}
else
{
return rightMax;
}
}
I have no problem writing the code, But I still can't figure out how to get the Iterations down tolog n
Would someone explain where I'm going wrong..
It's likely that the problem should read:"Write and test a recursive function that returns the maximum among the first n elements of a sorted array, using at most logn recursive calls."
nevermind, that was just dumb
> I tested two sets of unsorted integer(can be double)
> array. Both of them returned me the maximum element
> in 'logn' recursive call.
The recursive algorithm given in the book requires exactly 2n-1 calls, not O(log n).
> Your recursive method is based on C. I don't blame
> the book. Because, the designers of Java are C
> programmers :) .
I do blame the book, its obviously a piece of ****. And, the designers of Java probably did more Lisp programming than C (notably Gosling and Steele).
> After the above much appreciated help,
>
> I recoded the problem in the following way:
>
> But I obviously really really don't understand
> something about "How many Iterations" because by my
> count this takes approximately Twice as many
> as the O{n} solution........
>
> I restate: I'm **** at math...
The book is wrong. You are right. The algorithms requires 2n-1 calls.
> I have no problem writing the code, But I still
> can't figure out how to get the Iterations down to
>log n
You can't.
> Would someone explain where I'm going wrong..
You're reading a crappy book.
"Write and test a recursive function that returns the maximum among the first n elements of an array, using at most logn recursive calls."
It can be done by using 'logn' recursive calls only for small unsorted array.
The data sets that I used to test your algo was based on very small integer array.
Have fun with recursion!
Your code suffers from a couple problems.
First and foremost the initial comment is wrong. We already discussed that. Your routine does NOT return the result with O(logN) calls, it actually takes O(N) calls. It only has at most O(logN) calls "active" on the return stack at any time. I claim that what the author was thinking was:
"Write and test a recursive function that returns the maximum among the first n elements of an array, using at most logn recursive calls ( my addition - on the return stack at any time )."
Secondly, by slavishly adhering to the notion that you pass in a single argument, you are creating multiple arrays, and copying values back and forth. This is BAD.
If your list was a million elements long, your stack depth will be about 20 calls deep (2^10 == 10^3 so log(1000) == 10). At each level in the stack of calls, you have made a complete copy of your array (in two parts) Thus when you are 20 levels deep in your stack you have allocated and copied 20 Million elements. These arrays are all active at the same time.
This means that the simple task of finding the maximum of a million element array required an additional 20 million elements of space. That's what I mean by BAD.
If you modify the parameters, something for which you would need dispensation from the pope if you were doing real coding for the church but which you are free to do cause you are just learning. You can get something like this:
public max(int[] a){ // this is not recursive - it just calls the recursive helper
if(a.length == 0) return 3; //place holder for better error checking
return maxBetween(a, 0, a.length);
}
private maxBetween(int[] a, int lo, int hi1){
if((lo + 1) == hi1) return a[lo];
int mid = (lo + hi1)/2;
int m1 = maxBetween(a,lo,mid);
int m2 = maxBetween(a,mid,hi1);
return (m1>m2)?m1:m2;
}
BTW - just to cut the author of the book some slack, which I am sure he does not deserve, Consider the code I just typed in.
Is it right? Does it compile? Do you use, length or size() or count() with an array? Did I test it? Did I write test cases to be sure that it works if the intital array is empty? Did I test it with a large array to see that it does not blow up the return stack? Did I check that my division by 2 to generate a mid element will ALWAYS generate a proper mid value regardless of whether lo was even or odd? Do I know for certain that I will NEVER call my recursive function with an array with no elements? Do I really want code that returns some bogus value of 3 when the array is empty. Should I even be error checking at all in a simple little learning exercise? What if the array was so big that the caclculation (lo + hi1) overflows? Can that ever happen? Is it ok to just document that it doesn't work for really humongous arrays?
What I did do was the easy part, I just typed something in off the top of my head and it may be right and it may not. That is the fun part of writing code, but writing real code is hard work.
Now, would I be more careful and do all that work if I were writing a book? Probably not. I mean, If I am going to go to all the trouble to actually write the code and test it, I might as well get a job programming where I can get paid for all that work. They don't pay you for the fun stuff, they pay you for the work.
Writing books and teaching is fun. That's why it doesn't pay well. Being a student and learning is so much fun, not only does it not pay, you have to pay to be a student.
So learn what you can from the book and move on.
Thanks for the very complete reply.
Your sample solution also looks as if it is the "Correct" answer.
I kind of understand now that its 'about' 'n' comparisons, and 'log n ' of stack depth. I can see how the method I wrote creates too many arrays.
I do realise that:- I could probably just sort the array in less operations then get the max that way. If this was meant to do something 'real' I would probably do that.
It's been about 30 Years since I last had to do these 'homework' kind of problems.... Suppose it's 'better late than never'
Thanks for all the help.
sorting to find max is killing ant with hammer. (overkill)
sorting is O( n*Log(n) ) but finding max, even in inefficient recursive code is O(n).
typical max code makes one straight pass through the list. looks like this:
int max(int[] a){
int best = a[0];
for(int i = 1; i < a.length; i++) {
if( best < a[i]){ best = a[i];}
}
}
just keep hacking away. You will learn.
Enjoy
