EMAIL ME AT JOSHBOSKI@COMCAST.NET

If any one can help me complete this I may send you money for your help I need it done by tonight, thank you!!!!!!!

Test 12Ļ


1. Implement a recursive algorithm for finding a target value in an array (any array, not necessarily sorted). The algorithm uses the ¡§divide-and-conquer¡¨ approach, outlined below, to minimize the required stack space.

(a) Write a recursive method

public static int search(int a[], int m, int n, int target)

that tries to find target among the elements a[m], ..., a[n-1] of the array. If found, the method returns the position of the target value; otherwise it returns -1. The base case is when the searching range is empty (m „d n). For the recursive case, split the searching range into two approximately equal parts and try to find the target in each of them.

(b) How much stack space does this algorithm need (in the worst case) to search for a target in the range from a[0] to a[n-1]? O(log n)? O(n)? O(n log n)?


Continued „y

2. Our own ¡§innovative¡¨ Chunk Sort algorithm is designed for sorting arrays that consist of a few presorted chunks. The idea is to find the next chunk and merge it with the already sorted beginning segment of the array. We will implement this algorithm iteratively, without recursion.

(a) Fill in the blanks in the following merge method:

/**
* Precondition: 0 <= m <= n
* m == 0 or a[0] <= ... <= a[m-1]
* n == m or a[m] <= ... <= a[n-1]
* Postcondition: the values a[0] .. a[n-1] are arranged
* in the ascending order
*/
private static void merge(int a[], int m, int n)
{
// If any of the two segments is empty, do nothing:
___________________________________
___________________________________ ;

int i = 0, j = m; // starting indices into the two segments

// Allocate a temporary array temp to hold n elements
___________________________________ ;

int k = 0; // starting index into the temporary array

while (i < m && j < n)
{
if ( ______________________ )
{
__________________________________ ;
__________________________________ ;
}
else
{
__________________________________ ;
__________________________________ ;
}
k++;
}
// Copy remaining elements:
while (i < m)
{
________________________________ ;
________________________________ ;
k++;
}
while (j < n)
{
________________________________ ;
________________________________ ;
k++;
}

// Copy temp back to a:
for ( _____________________________________ )
______________________________________ ;
}

(b) Figure out how to simplify merge and make it slightly more efficient by eliminating some unnecessary copying.

Continued „y

(c) Fill in the blanks in the following chunkSort method:

public static void chunkSort(int a[])
{
int m = 0; // a[0], ... a[m-1] is the previous chunk
int n = 0; // a[m], ... a[n-1] is the current chunk, empty at first

// Loop invariant: n = m and a[0] <= ... <= a[m-1]

while ( _______________ )
{
// Find the end of the current chunk:
do
{
n++;
} while ( __________________________ );

merge(a, m, n);

// Update m:
___________________;
}
}

(d) If an array has n elements and the number of sorted chunks in that array is limited to a fixed number, say 10, what is the ¡§big-O¡¨ for the Chunk Sort algorithm on such an array in the worst case? O(n)? O(n log n)? O(n2)?
Continued „y
3. Java¡¦s math package has a class BigDecimal that implements decimal numbers with ¡§arbitrary¡¨ precision. Design and partially implement your own LargeFloat class that represents floating point numbers with a large but limited number of significant digits. A floating point number has a sign, a mantissa, and an exponent. For a mantissa, use an array of integers representing decimal digits. Use an array of a fixed size, say 60. Store the most significant digits at the beginning of the array: myDigits[0] is the most significant digit. The exponent is an integer that determines the position of the decimal point. It may be positive or negative or zero. For example, 123.45 has the sign ¡¥+¡¦, and may have the mantissa 123450...0 and the exponent 3. (The same number may have the mantissa 0123450...0 and the exponent 4.) 0.006789 has the sign ¡¥-¡¦, and may have the mantissa 67890...0, and the exponent -2. A large float equal to zero should be represented with its digits, exponent, and sign all equal to 0. Each LargeFloat number has a normalized form. In the normalized form of any number (except 0), the first digit of the mantissa is not a zero.

(a) Write two constructors: a default constructor that creates a LargeFloat equal to 0 and another constructor that builds a normalized large float from a given string. Use Character.digit(ch, 10) to convert a Unicode (ASCII) character ch, representing a digit, into the corresponding integer d (0 „T d „T 9).

(b) Write a method normalize that adjusts the exponent and shifts the digits of the mantissa in such a way that the most significant digit is not a zero.

(c) Write a method toString that converts a large float into a string, padding the number with zeroes if necessary and inserting the decimal point in the appropriate place. For example, a positive large float with the mantissa 123450...0 and the exponent -2 should result in a string equal to "0.0012345". A negative large float with the mantissa 123450...0 and the exponent 6 should result in a string equal to "-123450". A large float equal to 0 should result in "0".

(d) Write another constructor that creates a normalized large float from a double. Do not convert the double into a string first ¡X do it the hard way, ¡§from scratch.¡¨ Truncate the result to the first 12 significant digits. Hint: first ¡§normalize¡¨ the double x into the range 0.1 „T x < 1, adjusting the sign and the exponent accordingly; then ¡§extract¡¨ digits one by one and save them in the mantissa, starting from the left (most significant) digit.

(e) Write a method add(LargeFloat other) that builds and returns a new LargeFloat object equal to the sum of this and other, assuming that this and other are both non-negative or both non-positive.



4. Complete a method

public void removeBelowLimit(ArrayList samples, double limit)

This method removes all the values from samples whose value is below limit. samples is assumed to hold Double objects.

5. The ArrayList class has a method toArray, which returns an array of all the objects in this ArrayList, arranged in the same order. The length of the returned array is equal to the size of the list. Write your version of toArray using calls to other public ArrayList methods.

6. Write a method

public ArrayList toUpperCase(ArrayList words)

This method assumes that words holds Strings. It creates and returns a new list that contains the same strings converted to upper case. The original list must remain unchanged.

BONUS: DUE BY FRIDAY CLASS
7. In Pascal¡¦s Triangle, named after the French mathematician Blaise Pascal (1623 1662), all the numbers on the left and right sides are equal to 1 and each of the other numbers is equal to the sum of the two numbers above it. It looks like this:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
.....................

Write a method

public ArrayList pascalTriangle(int n)

that generates the first n rows of Pascal¡¦s Triangle. The method returns an ArrayList of rows. Both the size and the capacity of the returned list should be equal to n. Each row should be represented as an ArrayList of Integer objects with the appropriate values.
HELP If any one can help me complete this I may send you money for your help I need it done by tonight, thank you!!!!!!!