CSSE 220 -- Object-oriented Software Development

Homework 3 Due at 8:05 AM on Day 4.
Written problems due at the beginning of your class period.

  1. Complete the assigned reading for the next session (see the course schedule). If there is something you do not understand, make note of it so you can ask about it.
    Estimated time: Textbook: 40 minutes.
  2. Look at the Key Concepts from the end of chapter 3.  This is a good place to quickly notice things you might have missed from the chapters. At some point we will have a "Key concepts quiz" over chapters 1-4.
  3. Complete the Angel quiz over this reading. You'll find this on the course Angel page, under Lessons → Assignments → Reading Quizzes → Quiz 3.
    Estimated time (after reading the material): 20 minutes.
  4. Do the written exercises that are listed below.  You may write them neatly by hand or do them on your computer and print them. Turn in hard copy at the beginning of the Day 4 session. Include your name and section number at the top of your paper. 
    Estimated time: 30 minutes.
    1. (5 points)  Weiss exercise 1.14.
    2. (4 points)  Weiss exercise 2.6.  In addition to telling what each prints, explain why it prints what it prints.
    3. (5 points) Weiss exercise 2.9.  (Replace "routine" by "static method".)  You do not have to do this on your computer, but you are welcome to do so if you wish.
  5. Check out HW3 from your repository. It contains unit tests for the functions in the following two Java classes, as described below.  Write the required functions. Estimated time: 90 minutes if you came into this class retaining most of the CSSE120 material.

Classes to write for the programming part

Class Description
Reversers You will write two functions to create reversed strings. The first, called reverseLine(), will return a string with all of the characters reversed.  The second, reverseWords(), will return a string with the characters of each "word" reversed, but the order in which the words come in the line is the same as the original.  By "word" here, we mean a sequence of characters with no spaces. You can assume there is exactly one space between each pair of words. You may want to use String.split( )or the StringTokenizer class to pick out the words.  For example, if an input string, str, is:
The 'words' can contain punctuation.
then reverseLine(str) returns .noitautcnup niatnoc nac 'sdrow' ehT
And reverseWords(str) returns ehT 'sdrow' nac niatnoc .noitautcnup
Sieve The Sieve of Eratosthenes is a famous way of finding all prime numbers in a range reasonably efficiently.  It has been known for a couple of millennia.  A prime number is an integer that is greater than 1 and has no positive integer factors besides 1 and itself.  You are to write a single method, sieve(lower, upper), that takes two positive integers, the first one smaller than the second one. Your program is to return a string (with a single space after each number, including the last one to make it easier) containing all prime numbers that are in the closed interval bounded by these two numbers.  For example, if the arguments are 53 103, then the string returned should be:
"53 59 61 67 71 73 79 83 89 97 101 103 "
For another example,  if the command-line arguments are 10000000 10000200, then the string should be:
"10000019 10000079 10000103 10000121 10000139 10000141 10000169 10000189 "

Here is how the algorithm works, assuming that the two numbers are lower and upper.

  1. allocate an array, primes of upper + 1 booleans, set all of them to true.
  2. Start with base = 2.  "Cross off" (by setting the corresponding array element to false) all multiples of base that are  greater than or equal to base*base, and less than or equal to upper.  Can you see why it is okay to start with the more efficient  base*base rather than base*2? 
  3. Find the next base (i.e. the next prime) by finding the next true position in the array after the current position.
  4. Repeat steps 2 and 3 until base*base > = upper.
  5. Finally, loop through from lower to upper, printing each number whose array position is still true.
Note: Sieve should work almost instantaneously as long as the upper number is less than 1,000,000.
Hint: your inner loop should not have division, multiplication, or %, in order not to slow things down!