First Programming Assignment

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 2^{30}, so you can get by with 2^{30} bits.
At 32 bits per *int*, that means you need an array of 2^{25} 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