I have a assignment with these requirements:
Please begin stage 1 by writing a program that creates an output file. Name the file using your userid followed by .dat. For example, I would call my file “angelesm.dat”. The file should contain all of the multiples of 5 from 0 to 5000. Do not include a drive name or any directories in the file name. Have the program write these integers to the file after the creation of each integer.
Name the program using your userid. For example, I would name my program, angelesm.java. Your program should close the file after it is created and then open it again and read each integer value into an integer array.
Stage 2 of Programming assignment 1
You will be amending the program you coded in stage 1. Remember, there is just one program throughout this assignment. In each stage, we just add more code to the previous version of the program.
Create a second integer array with these values: 0, 5, 1000, 2500, 2505, 4995, 5000 and 5001. This array contains the search keys to be used in all of the search algorithms you will write for this assignment. Each of the search algorithms will need to try to locate each of these same 8 numbers in the 1001 item array.
Your book has a non-recursive (iterative) version of the binary search algorithm beginning on page 9. Think of this algorithm as psuedocode and implement it in your program as a separate function or method that accepts the array of 1001 values you created in stage 1 and a single search key which is one of the 8 values in the key array.
The function or method should return the number of comparisons it took to find the search key in the 1001-array or a “not found” value if the search is exhausted without finding the key (e.g. 5001 will not be found, but your program should tell you how many comparisons were needed to establish this fact).
Add a counter to your program that will tell you how many comparisons it takes to find each key value. You are counting the number of times you execute the “if” statement for a particular key value. You also need to count the number of milliseconds it takes to find each key value.
When you find the key value or exhaust the search without finding it, find the difference between the start time and the “find” time. This will give you the time it took to locate (or not) that key value.
You may need to find a way to slow the program down so that all times are not zero. You can call a “slow_down” function or method. For example, you could execute a loop that initializes a variable to zero 100,000,000 times. This may slow down the run of your program enough to get a significant value for the elapsed time. If you don’t slow down your program enough, you might see all elapsed times as zeroes.
Students using java often like to use the static method, System.currentTimeMillis() in the System class to obtain the start and end times.
Each time you find a key value, report the number of comparisons and the elapsed time.
Here is what your output might look like:
Binary Iterative Search
Search for 0: 9 comparisons in 1351 milliseconds -found
Search for 5: 8 comparisons in 1382 milliseconds -found
Search for 1000: 9 comparisons in 1382 milliseconds -found
Search for 2500: 8 comparisons in 1382 milliseconds -found
Search for 2505: 9 comparisons in 1342 milliseconds -found
Search for 4995: 10 comparisons in 1352 milliseconds -found
Search for 5000: 9 comparisons in 1362 milliseconds -found
Search for 5001: 10 comparisons in 1342 milliseconds- not found
Of course, you may get slightly different values than these, but please use this format for your output.
Stage 3 Last portion of first programming assignment
This last portion of the first programming assignment is worth the remaining 50 points and is due by the posted due date for the assignment.
In the second part of the assignment, you implemented the iterative binary search. Now produce the same findings for each of the following algorithms. Implement each as another function or method in your program.
1. Recursive Binary Search Algorithm
2. Variation of the Binary Search Algorithm
This is a third variation of the binary searches that you just completed. However, instead of splitting the 1001-array into two almost equal halves, divide the set at the 1/3 marker into two unequal sets. One set will be the first one-third of the original and the other will be the last two-thirds of the original set. This is still a binary search because you are only searching two sets. Only now the sets are not the same size. In other words, this will be just like the recursive or iterative binary searches, only the search sets will be of different sizes.
3. Ternary Search Algorithm
This time divide the original 1001-array into 3 sets of almost equal size.
4. Quadruple Search Algorithm
This time divide the original 1001-array into 4 sets of almost equal size.
Your report for this assignment will show the order of complexity for each algorithm and your conclusions regarding the most efficient way to search these 1001 integers. For example, did the output from your program verify the expected values for the order of complexity for each algorithm?
The problem with finding the order of complexity is that you cannot establish a single pattern and follow it for all algorithms. Each one may be different. Fortunately, most will fall into a family of patterns. In this case, the order of complexity is not a quadratic function as your homework assignment was, but a logarithmic function. Since your book (see page 326-330) gives you the order of complexity for the binary search algorithm as well as the algorithm, itself, you may assume that this order of complexity is correct.
The order of complexity of the recursive binary search, according to your book, is approximately log(2) n, where 2 is the base. Two is in parentheses because there is no easy way for me to write it as a subscript here. Read this, “log of n base 2”. This means that if n is 1000, find the number to which 2 needs to be raised in order to obtain 1000 as the result. If you raise 2 to the 10th power, you will get 1024, which is close enough. Notice that your actual result from your code is close to 10 most of the time for the recursive binary search. There are only 2 values in this order of complexity function: the base for the log, (which is 2 in this case), and n. What value in the algorithm do you think “n” is? You are right if you think n is 1000 or the size of the array to be searched. How do you think the base value of 2 relates to the “binary” search algorithm? How do you think the order of complexity might change for the “ternary” search?
For the test plan, just tell how you made sure that your code worked properly. I set this up for you by having you test the extremes, 0 and 5001 and the middle and for a value not found. For this reason, you will not be earning points for developing the test plan as specified at the course site. Those points will be allocated proportionately over the assignment.
Here is my program: //program:
"Willia9a.java"
import java.io.*;
public class multiplesof5
{
public static void main(String[] args)
{
int multiples[] = {0,5,1000,2500,2505,4995,5000,5001};
}
{
read BufferReader;
throw IOException();
{
BufferReader infile = new BufferReader(
new FileReader("Willia9a.dat"));
inputLine = infile.readLine();
while(inputLine != null);
}
{
FileInputStream inputStream =
new FileInputStream("input.bin");
}
{
IllegalArgumentException exception
= new IllegalArgumentException("multiple doesn't match input");
throw exception;
}
if (isMultiple){
System.out.println(multiple);
System.out.println(numpasses/numseconds + "calls per second");
}
else{
System.out.println("not found");
System.out.println(numpasses/numseconds + "calls per second");
}
{
numpasses = Integer.parseInt(args[args.lenght-1]);
}
{
long TimeRequired = multiple.getTime();
double numseconds = TimeRequired/1000.0;
System.out.println("Complete" + numpasses + "passes in"
+ numseconds + "seconds" );
System.out.println(numpasses/numseconds + "calls per second");
}
Here is my dat file:
File "Willia9a.dat"
import java.util.Multiplesof5;
/**
This program tests the Multiplesof5.
*/
public class Multiplesof5
{
public static void main(string[]args)
{
ArrayList<multipesof5> multiples
= new ArrayList<multiplesof5>();
multiple.add(new multiple(5));
multiple.add(new multiple(10));
multiple.add(new multiple(20));
multiple.add(new multiple(50));
multiple.add(new multiple(100));
multiple.add(new multiple(200));
multiple.add(new multiple(500));
multiple.add(new multiple(1000));
multiple.add(new multiple(2000));
multiple.add(new multiple(5000));
System.out.primtln(multiple());
Multiplesof5 first = multiple.get(5);
System.out.println("first multiple number="
+ first.getMultipleNumber());
Multiplesof5 last = multiple.get(();
System.out.println("last multiple number="
+ last.getMultiplesof5());
}
}
I have compile my program and keep getting a error:
willia9a.java 60: '}' expected
I also need to know how to run my program to test it.
Thanks for any help someone can give me
