CSE 160
Lab 5 and HW 5
Due Thursday, March 10, 2009

Reading: Read Ch 5 in the Objects First text .  Work along with it, using BlueJ.

Lab Exercise: TBA
                
HW:  Two projects involving loops, sets, and static methods. (Note: these are not the most efficient methods to solve these problems. They merely illustrate how to think about and use sets.)  Send them to the TA before class on March 10.

A) Sieve of Eratosthenes, using HashSets

1) Look up in a Discrete Math text (or on the internet) about the Sieve of Eratosthenes. Our plan for finding primes is: Initially all numbers from 2 to N are candidates and your set of primes is empty. As long as you have any candidates, choose the smallest candidate and call it p.  Put p into your set of primes. Make a set called multiples of all the integer multiples of p from 1*p up to N*p. Remove all the multiples from the set of candidates (which is a set difference operation: candidates = candidates-multiples).

2) Look at the JavaDocs for the class HashSet, especially the add(), isEmpty(), contains(), remove(), and removeAll() methods. Think about how they can be used in implementing the Sieve algorithm. Notice that HashSet does not have a method for getting its smallest element. We should not expect it to, because in general a set can have any kind of element, not necessarily elements with an ordering, so "smallest" is not defined.

3) Look at the JavaDocs for Math, and observe that its methods are static. They are not invoked on an instance of anything. They are invoked with the class name. For example, to use the absolute value function, we can write int x = Math.abs(-3); The Math class is a way to package groups of useful functions that are not associated with particular instances of anything. We will create such a class with static methods for finding the largest and smallest element of a set of integers. Call the class Search. It has no constructors as it is just a holder for static methods. It will include a method with this signature for largest() and a similar one for smallest()
               public static int largest(Set<Integer> set)
This will take any kind of Set of Integers as its argument, which includes the type HashSet. Below is the algorithm for finding the largest. It is an exhaustive search through the elements of the set. We initialize the answer to something small, e.g., zero. Then try each element in turn, and if it is larger than the largest we found so far, we remember it as the largest. After going through the whole list, we must have found the very largest:
       biggest = 0
       for x in the set
              if (x>biggest) biggest=x
       return biggest
The for-each loop in Java will work with any kind of Set.

A similar algorithm finds the smallest element of a set, but we must initialize its answer variable to something very large. A number like two billion will work fine. If you want the absolutely largest or smallest possible value, look in the JavaDocs for Integer.MAX_VALUE

4) If the above is working, You should be able to create a set and find its largest or smallest element with a Test class like this:

import java.util.HashSet;

public class Test
{
    public Test()
    {
        HashSet<Integer> example = new HashSet<Integer>();
        example.add(7);
        example.add(9);
        example.add(3);                                // create set {3, 7, 9}
        System.out.println(Search.largest(example));   // should print 9
        System.out.println(Search.smallest(example));  // should print 3
    }
}

5) Write a Sieve class with a HashSet<Integer> field called primes, which has three methods:

• The constructor takes an integer argument, N, and constructs the set of primes in the range 2...N.  It uses the algorithm in (1) above, the standard Set methods in (2) above and your static Search.smallest() method of (3) above. Local variables candidates and multiples will also be HashSets of Integers.
  
• printPrimes() prints all the primes.
• getLargest() returns the largest prime in the set, which will be the largest prime not greater than N.

You can use the debugger to step through your loop and check it generates in order: 2, 3, 5...  You can then test it further by computing all the primes under 20 if you temporarily include a line printPrimes(); at the end of the constructor. It is OK if they are printed out in a strange order, because the HashSet iterator does not know what order you want.

Send your .jar file to the TA and include in your email the answer to this question: What is the largest prime under 10000?


B) A Finite Sequence

Consider this sequence: 1,3,4,5,6,7,8,9,10,12,15,17,19,21,24,25,...   What is its final term?

It starts with 1. If a given term is n, the next term is obtained by adding to n the smallest positive integer sharing no digit with n. The sequence will end when you reach a number containing all the digits from one through nine, as then there is no next term by the definition.

As we will need to find the smallest element of a set, we can reuse the Search class from above. To do so, import that project into this project, and delete all its classes except Search.

Define a class Term, which holds a general term. It turns out that an integer field can hold the value of the term, because the sequence terminates before two billion. It should have the following methods:

• a constructor with no arguments creates the initial term with value 1.
  
• getValue() returns the value of the term, as an integer.
• getDigits() returns a HashSet of the digits in a term. (Think about what you did to create a Bignum last week.)
  
• nextTerm() returns the next term for a given term or null to flag that there is no next term. It can work by first using the getDigits() method to find its own digits, then using a set difference to find the positive digits not in the term, then using the Search.smallest() method from problem A above to extract the smallest digit, then ordinary addition.

Define class Test with argument N, to print out the first N terms.
        Term t = new Term();
        for (int i=1; i<N; i++) {
            System.out.println(t.getValue());
            t = t.nextTerm();
        }
Verify that you can replicate the initial sequence above. Following the execution with the debugger might be useful.

Define a class LastTerm to find the last term, by generating new terms until null is reached, then returning the last non-null term found. (This takes about five minutes on my PC.)

Send your .jar file to the TA and include in your email the answer to this question: What is the last term?