This programming assignment is due on Friday, October 16 (after we come back from Fall break). It relates to Section 2.3 in the textbook, using integer values and bitwise operators to represent sets of integer and operations on those sets. You will write two Java programs. The first program uses numbers of type int to represent sets of numbers in the range 0 to 31. The second is a program that implements the Sieve of Eratosthenes.
There is a folder in the directory /classes/cs229/homework with your last name on it. You should submit your work to that folder. I will print out your programs; there is no need to turn in a printout. The programs that you turn in should, of course, show good programming style (especially indentation and commenting).
Part 1. For this exercise, you will write a program that inputs two sets from the user and outputs their complements, their union, and their intersection. The sets are sets of integers in the range 0 to 31, inclusive. Such a set can be represented as a value of type int. If A and B are ints that represent two sets, then their complements are represented as ~A and ~B, their union is represented by A&B, and their intersection is represented by A|B.
Your program should input two such sets from the user. Assume that a set is typed in as a sequence of integers in the range 0 to 31, all on one line, separated by spaces. Print out the two input sets, A and B, along with ~A, ~B, A&B, and A|B in the same format. Here is an example of input and output from the program:
Input A: 0 2 4 6 8 10 12 14 16 18 20 25 30 31 Input B: 7 3 8 2 13 6 7 12 31 22 23 4 26 15 2 1 29 A = 0 2 4 6 8 10 12 14 16 18 20 25 30 31 B = 1 2 3 4 6 7 8 12 13 15 22 23 26 29 31 ~A = 1 3 5 7 9 11 13 15 17 19 21 22 23 24 26 27 28 29 ~B = 0 5 9 10 11 14 16 17 18 19 20 21 24 25 27 28 30 A&B = 2 4 6 8 12 31 A|B = 0 1 2 3 4 6 7 8 10 12 13 14 15 16 18 20 22 23 25 26 29 30 31
You should write a static method that reads a set and returns the result as an int, and another method that takes an int as a parameter and outputs the corresponding set. Note that writing out the set will require the use of one of the operators << or >> to get access to the individual bits in the int.
(The hardest part is to read all the numbers from one line and know when to stop. The easiest solution is to use a Scanner to read complete lines of text from standard input (String line = in.nextLine();). Then create another Scanner that you can use for reading integers from the input line (Scanner readline = new Scanner(line);).)
My program was 62 lines, before adding comments.
Part 2. The Sieve of Eratosthenes is a classic algorithm for finding all the prime numbers less than or equal to some given integer MAX_N. Your program will use it to compute the set of primes less than or equal to one billion (1000000000). The program should print out the number of primes in that range, and it should print out the largest prime in that range.
The algorithm can be stated very simply in pseudocode. To construct the set of prime numbers less than or equal to MAX\_N:
Let primes be the empty set.
for (int n = 2; n <= MAX_N; n++)
add n to primes
for (int p = 2; p <= MAX_N/2; p++) {
if (primes contains p) {
for (int n = 2*p; n <= MAX_N; n += p)
remove n from primes [if it's in primes]
}
}
When this algorithm has finished, the integers that remain in the set primes are all the prime numbers less than or equal to MAX_N.
In your program, you should represent a set of non-negative integers as a large array of int using just one bit for each possible member of the set. This means that a 32-bit integer represents 32 possible members of the set. If primes is the array, then primes[0] represents the numbers 0 through 31, primes[1] represents the numbers 32 through 63, primes[2] represents the numbers 64 through 95, and so on.
One billion is less than 230, so you can get by with 230 bits. At 32 bits per int, that means you need an array of 225 integers. You can declare it as a global variable
static int[] primes = new int[ 1<<25 ];
You should also declare a global constant, MAX_N, to make it easy to test your program on smaller numbers. (Note: Because of the limit on the size of int values, don't try to run your program for numbers bigger than one billion.)
Given a number N, it will be necessary to locate the one bit in the
array that represents N. That bit is in one of the elements of the array.
You need to know the index of that array element, and you need to know the
position of the bit within the integer at that index.
In fact, the index can be computed as N / 32, or, better,
as N << 5. And the bit position is given by
N % 32, or, better, as N & 31.
You will want to write static methods add(n), remove(n), and contains(n) to implement the set operations on the array. With those operations in hand, the main routine can simply follow the above pseudocode very closely.
My program was 50 lines, before adding comments. It took about 30 seconds to run. I did not try to optimize it. The time can vary greatly depending on the speed of your computer and the details of your program. You should try to run your programs for small values of MAX_N to make sure that it works. (When MAX_N is small during testing, you can consider printing out the primes, to be sure that you are computing them correctly.) Here is the output from my program, which has some chance of being correct:
The number of primes <= 1000000000 is 50847534 The largest prime <= 1000000000 is 999999937