Lab 10: More on Arrays

Setup

Create a lab10 directory in your cs124 directory to hold the files for this lab.

Copy the files from /classes/f06/cs124/labs/lab10/ to your lab10 directory.

Exercises

Here are the exercises for this week's lab, due in two weeks on Thursday, December 7th.

In mathematics, a Fibonacci number is defined as follows:
```
F(n) = 0 if n = 0

       1 if n = 1

       F(n-1) + F(n-2) if n > 1
```
That is, after two starting values, each number is the sum of the two preceding numbers. The first 10 Fibonacci numbers are:
```
0, 1, 1, 2, 3, 5, 8, 13, 21, 34
```
Using an array (which I'll call fib[]), we can compute the first n Fibonacci numbers. The ith element in fib[] represents the ith Fibonacci number. We start off by initializing fib[0] to 0 and fib[1] to 1, and then loop over the remaining elements setting them to fib[i-1] + fib[i-2].

Write a program called Fib.java that prints the first n Fibonacci numbers. It should read n from the user and make sure that n is non-negative. Run your program and enter 100 for n. What happens at the higher Fibonacci numbers? Why does this happen? Put your answers to these questions in the comments at the top of Fib.java.
Write a program called PrintProperties.java that reads in a sequence of (unsorted) numbers from a file called foo.txt (provided in the directory) and prints out some properties of those numbers. Your program should print out the numbers in sorted order, the average of the numbers, the median of the numbers, and the min and max number. Your program should also prompt the user for a number and print whether that number is contained within the sequence of numbers. You should use the binary search algorithm presented in class for finding a number in a sorted array.

Note: you cannot make any assumptions about the length of the sequence of numbers in foo.txt. Instead, you must conservatively size the array. If your array is not large enough, you must dynamically resize the array. When I grade your program, I will try it using different sequences of numbers to see if it works.

For information on reading from a file, reread pages 43 and 44 of the book (chapter 2). If you don't have your book with you, the book can be found online at http://math.hws.edu/javanotes5/.

Here is the output your program should generate (note: your copy of foo.txt is actually much larger than the one shown here). Input from the user is shown in bold.
```
Enter a number: 4
Sorted numbers:
103186
136562
323269
507378
516891
578495
617052
637519
751806
962767
Average: 513492
Median: 547693
Max: 962767
Min: 103186
4 is not in the sequence.
```
You should use at least three methods: main(), binarySearch(), and sortArray(). binarySearch() should take an array and a value as input, and return the index of the value in the array or -1 if it is not within the array. sortArray() should take an array and return the sorted array. Feel free to use any additional methods.

One final note: it is easier to read the search number first, before reading in the sequence of numbers (as done in the output above).

Handin

Verify that your lab10 folder contains all of the files you created or modified for this lab, then copy your entire lab10 folder to the handin directory ~mcorliss/handin/124/username (where username is replaced with your username).