Lab 5: Arrays

This weeks labs will focus on arrays in Java.

Introduction

Arrays are one of the most fundamental data structures, and they are incredibly useful. One reason they are so handy is that it is possible to access a slot using a computed-at-runtime integer - this is a sharp contrast to non-array variables where you have to know the name of the variable you want to access at compile time. Furthermore, the length of the array can also be determined at runtime - again, a contrast to non-array variables where you have to declare each one and thus must decide on the number of them by compile time.

Setup

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

Copy the files from /classes/s08/cs124/labs/lab05/ to your lab05 directory.

Exercises

Here are the exercises for this week's lab, due next Thursday.

Write a program called PrintReverse.java, which reads in integers from the user until the user enters a negative integer, and then prints those integers to the screen in reverse order (excluding the negative integer). Below is an example run (user input is in bold):
```
Enter a sequence of integers >= 0.  Enter a negative integer to stop.

Enter number: 12
Enter number: 2
Enter number: 5
Enter number: -1

Your numbers in reverse order:
5
2
12
```
Note: you cannot make any assumptions about the number of integers that the user will enter. To do this, you will need to conservatively size your array and if your array is ever filled, you will have to resize your array as discussed in class and in Section 7.3.2 of the book. You will also need to keep track of the portion of the array that is currently being used. For example, if your array has size 100 and the user enters only 7 non-negative integers then only the first 7 entries in the array are used (in this case, you should print out 7 numbers not 100 numbers!). You may also want to test your program using a small initial size for your array so that you can verify that your resizing works.
Write a program called PrintMatrix.java that reads in 9 integers from the user and then prints them out in a 3x3 matrix. It should also print out the sum of each row and column. Below is an example run (user input is in bold):
```
Enter number 1: 8
Enter number 2: 3
Enter number 3: 9
Enter number 4: 0
Enter number 5: 10
Enter number 6: 3
Enter number 7: 5
Enter number 8: 17
Enter number 9: 1

Matrix:
Row 1: 8 3 9
Row 2: 0 10 3
Row 3: 5 17 1

Row totals: 20 13 23
Column totals: 13 30 13
```
You may want to use a multi-dimensional array for this problem, although you are not required to so long as the program works correctly.
A prime number is a number which is only (evenly) divisible by itself and 1. In this exercise you will use the Sieve of Eratosthenes algorithm for finding prime numbers. Note: you may not use the algorithm for finding prime numbers that was presented in class. You must use the algorithm described below.

To use the sieve, write down all of the numbers from 2 to some number n and then apply the following (partial) algorithm:
```
  for each number from 2 to n do
    if the number hasn't been crossed off,
      it is a prime
      cross off all multiples of that number  
```
As an example, let's use the sieve to find the prime numbers between 2 and 15. We start with all the numbers listed:

2 3 4 5 6 7 8 9 10 11 12 13 14 15

Begin with 2 - it hasn't been crossed off, so 2 is the first prime and we cross off all the multiples: (bold indicates primes; gray background marks numbers crossed off)

2 3 4 5 6 7 8 9 10 11 12 13 14 15

Now we move on to the next number, 3. It hasn't been crossed off, so it is a prime and we cross off all numbers which are multiples of 3:

2 3 4 5 6 7 8 9 10 11 12 13 14 15

The next number (4) has been crossed off so we do nothing. The next number (5) hasn't been crossed off, so it is prime and we cross off all multiples of 5:

2 3 4 5 6 7 8 9 10 11 12 13 14 15

This process repeats: 6 has been crossed off, so we do nothing. 7 hasn't, so it is prime and we cross off all multiples of 7:

2 3 4 5 6 7 8 9 10 11 12 13 14 15

8, 9, 10 have all been crossed off, so 11 is the next prime. And so forth...

An array can be very handy for implementing this algorithm. The idea is to use an array of booleans to keep track of what numbers have and haven't been crossed off. We'll use a value of false in slot k to indicate that the number k hasn't been crossed off, and a value of true to indicate that the number has been crossed off. At the beginning all of the slots are initialized to false. Now, apply the algorithm above starting with slot 2 - if the number hasn't been crossed off, then the value stored in its slot is false; crossing off a number means setting the value in the appropriate slot to true. (The values in slots 0 and 1 will never be used.)

Your task is to write a program called FindPrimes.java to find prime numbers using the Sieve of Eratosthenes, using a boolean array as outlined above. The program should prompt the user for a number n which is the upper end of the range, and should then print all of the prime numbers between 2 and n (including n if it is prime). Make sure your array is large enough to have a slot numbered n.

Handin

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