A simple question about opreator.

[Flamingo]

Hi guys,

I want to write a recursion function that returns the maximum among the
first n elemetns of an array, using at most "lgn" recursive calls.

here is my function:

public class Prob0405 {

/**
* @param args
*/
public static double 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);
return (m1>m2 ? m1:m2);
}
}

but when I try to compile , some syntex error reported, error happend
at "double m2 = max(a+n1,n2)",

it is said "The operator + is undefined for the argument type(s)
double[], int",

how could modify that? Any help would be appreciated! thanks.

 

[Manish Pandit]

The error is self-explainatory.

Why are you adding a number to an array? Recheck your logic/alogorithm
- you need to be operating on array *element*, not the array *object*
on that line.

-cheers,
Manish

 

[Patricia Shanahan]

Hi guys,

I want to write a recursion function that returns the maximum among the
first n elemetns of an array, using at most "lgn" recursive calls.

here is my function:

public class Prob0405 {

/**
* @param args
*/
public static double 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);
return (m1>m2 ? m1:m2);
}
}

but when I try to compile , some syntex error reported, error happend
at "double m2 = max(a+n1,n2)",

Why are you adding to an array reference? Java has no pointer
arithmetic, and even if it did, a non-null array reference points to the
array object, not necessarily the first cell of the array.

This looks like an attempt to run C code in Java.

To do what you want, you need to pass around enough information to
identify a consecutive slice of the array, such as start index and
length, or start and end index, as well as the array reference.

Patricia

 

[Flamingo]

sorry , I'm not very familiar with the syntax of Java, can you give me
an example how to "pass around enough information "

Hi guys,

I want to write a recursion function that returns the maximum among the
first n elemetns of an array, using at most "lgn" recursive calls.

here is my function:

public class Prob0405 {

/**
* @param args
*/
public static double 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);
return (m1>m2 ? m1:m2);
}
}

but when I try to compile , some syntex error reported, error happend
at "double m2 = max(a+n1,n2)",

Why are you adding to an array reference? Java has no pointer
arithmetic, and even if it did, a non-null array reference points to the
array object, not necessarily the first cell of the array.

This looks like an attempt to run C code in Java.

To do what you want, you need to pass around enough information to
identify a consecutive slice of the array, such as start index and
length, or start and end index, as well as the array reference.

Patricia

 

[Oliver Wong]

[post re-ordered]

Hi guys,

I want to write a recursion function that returns the maximum among the
first n elemetns of an array, using at most "lgn" recursive calls.

[Patricia wrote:]
To do what you want, you need to pass around enough information to
identify a consecutive slice of the array, such as start index and
length, or start and end index, as well as the array reference.

sorry , I'm not very familiar with the syntax of Java, can you give me
an example how to "pass around enough information "

"Add a parameter to the method which is getting called recursively" is
an example of a way to pass around information.

- Oliver

 

[Shawn]

"Add a parameter to the method which is getting called recursively"
is an example of a way to pass around information.

- Oliver

I am very interested in this statement or strategy. Could you elaborate
it a little more?

Thank you very much.

 

[Oliver Wong]

I am very interested in this statement or strategy. Could you elaborate it
a little more?

Thank you very much.

<oldCode>
public void someMethod() {
//Does something
}
</oldCode>

<newCode>
public void someMethod(int aNewParameter) {
//Does something
}
</newCode>

Seriously, this seems like such a basic concept to me that I'm not sure
what more can be said on it. Previously, someMethod had no information being
passed into it. Now it has an integer passed into it.

- Oliver

 

[Shawn]

Hi guys,

I want to write a recursion function that returns the maximum among the
first n elemetns of an array, using at most "lgn" recursive calls.

here is my function:

public class Prob0405 {

/**
* @param args
*/
public static double 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);
return (m1>m2 ? m1:m2);
}
}

but when I try to compile , some syntex error reported, error happend
at "double m2 = max(a+n1,n2)",

it is said "The operator + is undefined for the argument type(s)
double[], int",

how could modify that? Any help would be appreciated! thanks.

I like your original program, even though it doesn't run. It is good
thinking. I just changed it so that it runs. Following is the file
Tool.java. It runs correctly.


public class Tool {
public static double max(double[] aArray, int iTotal, int iStart)
{
if (iTotal == 1)
{
return aArray[iStart];
}
else
{
int iEnd = iStart + iTotal - 1;
int iFirstHalfCount = iTotal/2;
int iLastHalfCount = iTotal - iFirstHalfCount;

double dMaxFirstHalf = max(aArray, iFirstHalfCount, iStart);
double dMaxLastHalf = max(aArray, iLastHalfCount,
iStart+iFirstHalfCount);

if (dMaxFirstHalf >= dMaxLastHalf) {
return dMaxFirstHalf;
}
else {
return dMaxLastHalf;
}
}

}

public static void main(String[] args)
{
double[] myArray = {3.3, 15.8, 9.7, 4.3, 16.6, 1.4,
3.6, 8.0, 5.2};
double max = max(myArray, 6, 0);

System.out.println("max = " + max);
}

}

 

[Oliver Wong]

Hi guys,

I want to write a recursion function that returns the maximum among the
first n elemetns of an array, using at most "lgn" recursive calls.

here is my function:

public class Prob0405 {

/**
* @param args
*/
public static double 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);
return (m1>m2 ? m1:m2);
}
}

but when I try to compile , some syntex error reported, error happend
at "double m2 = max(a+n1,n2)",

it is said "The operator + is undefined for the argument type(s)
double[], int",

how could modify that? Any help would be appreciated! thanks.

Incidentally, I don't think "what you're trying to do" (assuming I
correctly guessed what you're trying to do) will work. Imagine the array is
of length 4. log2(4) = 2, so you could make at most 2 recursive calls, but
you actually make 4 recursive calls.

Here's the simplest solution I can think of (in pseudocode) which
satisfy the (arbitrary?) requirement that the method must be recursive:

<pseudocode>
public double max(double[] a, int n) {
double max = MINIMAL_DOUBLE_VALUE;
if (length of a == 1) {
return a[0];
}
if (n == SOME_MAGIC_VALUE) {
return AN_IRRELEVANT_VALUE;
}
max(a[], SOME_MAGIC_VALUE); /*obligatory recursive call*/
for (double d : a) {
if (d > max) {
max = d;
}
}
return max;
}
</pseudocode>

There's two cases of interest: Either the the length of the array is 1,
or it is greater than 1.

If the array is length 1, then we may only make lg2(1) == 0 recursive
calls. Luckily, the algorithm above makes 0 recursive calls if the array
length is 1.

If the array length is > 1, then we may make l2(array length) >= 1
recurisve calls. Luckiyl, the algorithm above makes 1 recursive call if the
array length is > 1.

Assumptions made are that an empty array won't be passed in (in which
case the max is undefined), and that SOME_MAGIC_VALUE will not be a value
passed in for n. For example, if we assume the user will never provide a
negative n, SOME_MAGIC_VALUE can be -1.

- Oliver

 

[Shawn]

Incidentally, I don't think "what you're trying to do" (assuming I
correctly guessed what you're trying to do) will work. Imagine the array
is of length 4. log2(4) = 2, so you could make at most 2 recursive
calls, but you actually make 4 recursive calls.

Here's the simplest solution I can think of (in pseudocode) which
satisfy the (arbitrary?) requirement that the method must be recursive:

<pseudocode>
public double max(double[] a, int n) {
double max = MINIMAL_DOUBLE_VALUE;
if (length of a == 1) {
return a[0];
}
if (n == SOME_MAGIC_VALUE) {
return AN_IRRELEVANT_VALUE;
}
max(a[], SOME_MAGIC_VALUE); /*obligatory recursive call*/
for (double d : a) {
if (d > max) {
max = d;
}
}
return max;
}
</pseudocode>

There's two cases of interest: Either the the length of the array is
1, or it is greater than 1.

If the array is length 1, then we may only make lg2(1) == 0 recursive
calls. Luckily, the algorithm above makes 0 recursive calls if the array
length is 1.

If the array length is > 1, then we may make l2(array length) >= 1
recurisve calls. Luckiyl, the algorithm above makes 1 recursive call if
the array length is > 1.

Assumptions made are that an empty array won't be passed in (in which
case the max is undefined), and that SOME_MAGIC_VALUE will not be a
value passed in for n. For example, if we assume the user will never
provide a negative n, SOME_MAGIC_VALUE can be -1.

- Oliver

I never thought I would disagree anything from you. But this time is
really exceptional:

I believe OP means in the oder of theta of log(n), which means double
the number n, the required time (memory space? details ignored...) is
only doubled, instead of linear increase, for example.

 

[Lasse Reichstein Nielsen]

I believe OP means in the oder of theta of log(n), which means double
the number n, the required time (memory space? details ignored...) is
only doubled,

actually, only increased by 1

instead of linear increase, for example.

However, the OP's requirement about using recursion is arbitrary,
since the simplest and fastest algorithm is just a linear iteration
through the data.

A requirement of at most O(log2(n)) recursive calls (or log2(n))
sounds even more arbitrary, since the simplest recusive function takes
a approx. n/2 recursive calls (this is the one the OP has actually
implemented), and an algorithm using log2(n) calls would be needlessly
complicated.

And my guess about the cause of the problem is that the OP has tried
to implement a C (or C++) algorithm using pointer arithmetic in Java.

/L

 

[Patricia Shanahan]

Incidentally, I don't think "what you're trying to do" (assuming I
correctly guessed what you're trying to do) will work. Imagine the
array is of length 4. log2(4) = 2, so you could make at most 2
recursive calls, but you actually make 4 recursive calls.

Here's the simplest solution I can think of (in pseudocode) which
satisfy the (arbitrary?) requirement that the method must be recursive:

<pseudocode>
public double max(double[] a, int n) {
double max = MINIMAL_DOUBLE_VALUE;
if (length of a == 1) {
return a[0];
}
if (n == SOME_MAGIC_VALUE) {
return AN_IRRELEVANT_VALUE;
}
max(a[], SOME_MAGIC_VALUE); /*obligatory recursive call*/
for (double d : a) {
if (d > max) {
max = d;
}
}
return max;
}
</pseudocode>

There's two cases of interest: Either the the length of the array
is 1, or it is greater than 1.

If the array is length 1, then we may only make lg2(1) == 0
recursive calls. Luckily, the algorithm above makes 0 recursive calls
if the array length is 1.

If the array length is > 1, then we may make l2(array length) >= 1
recurisve calls. Luckiyl, the algorithm above makes 1 recursive call
if the array length is > 1.

Assumptions made are that an empty array won't be passed in (in
which case the max is undefined), and that SOME_MAGIC_VALUE will not
be a value passed in for n. For example, if we assume the user will
never provide a negative n, SOME_MAGIC_VALUE can be -1.

- Oliver

I never thought I would disagree anything from you. But this time is
really exceptional:

I believe OP means in the oder of theta of log(n), which means double
the number n, the required time (memory space? details ignored...) is
only doubled, instead of linear increase, for example.

To find the maximum of an array every element must participate in at
least one comparison, implying Omega(N) comparisons.

In the recursive code above, there will be N calls with length 1,
sup(N/2) calls with length 2, ... , 1 call with length N, a total of
about 2N calls, Theta(N).

Finding the maximum is very different from the classic O(log N) problem,
binary search, because binary search, at each level, can use a single
comparison to halve the data that must be examined.

The recursion depth is O(log N), which may be what is meant.

Of course, one can do the problem, very efficiently, with a single call
which is O(lg N) calls.

Patricia