CSSE 220 – Object-Oriented Software Development

Homework 29

Objectives

Explore the use of more powerful data structures with Markov.

Finish the Team Mini-project

Implement Linked List methods

Tasks

1. There is no new reading assignment.  If you are behind, catch up before the Final Exam.
2. Solo Work:
   1. This work is to be done in the MyLinkedListReal project.
   2. (5 points) Your instructor will indicate which methods you should get working. It will be the ones we do in class, plus perhaps one or two more. 
      [Added after class: The only method you have to implement, beyond what we did in class,  is the remove method) .

3. Team work: Work with your assigned team  for the Minesweeper/Markov programs.

   1. Make progress toward the Markov Milestone 1, which will be due Friday at 11:59 PM.
      (This used to say 5 PM, but I noticed that the schedule page said 11:59 PM, and I did not want to penalize anyone who had been counting on that extra work time.)
   2. Working with your team, complete Cycle 4 of the Minesweeper project. Summarize what you did/didn't complete from your Cycle 4 user stories.
   3. Complete the MineSweeper Team evaluation survey on ANGEL.
4. Preparation for Final Exam: In HW 25, I suggested some problems for you to think about.  Here are a few more:
   • When I gave this problem last year, I had students use command-line arguments. You are welcome to instead write a method that takes those arguments, and call it from main() or from JUnit tests.   THe Sieve program is

     Class	Description
     Reverser	Reads lines of input from the keyboard (It does not print any kind of prompt).  After reading each line, it first prints the line with all of the characters reversed.  Then it prints the line 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 may want to use String.split( )or the StringTokenizer class to pick out the words.  For example, if an input line is: The "words" can contain punctuation. then the output should be .noitautcnup niatnoc nac "sdrow" ehT ehT "sdrow" nac niatnoc .noitautcnup Your program should keep reading and reversing input lines until the user signals end of input (ctrl-z in Windows, ctrl-d in UNIX/Linux ).  It should not print anything except the two "reversed" lines for each input line.
     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.  Your program (classname: Sieve) must take two positive integers as its command-line arguments.  Both arguments should be positive integers, and the first one should be smaller than the second one.  Your program is to print (on one line, with a single space after each number) all prime numbers that are in the closed interval bounded by these two numbers.  For example, if the command-line arguments are 53 103, then the output 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 output 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. allocate an array, primes of upper + 1 booleans, set all of them to true. 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?  Find the next base (i.e. the next prime) by finding the next true position in the array after the current position. Repeat steps 2 and 3 until base*base > = upper. Finally, loop through from lower to upper, printing each number whose array position is still true.

   • When the input size is N, algorithm A uses 5 N log N operations, while algorithm B  uses N² operations.  For small values of N, algorithm B is faster; for large values of N, algorithm A is faster.  Determine the smallest possible integer N₀ such that for all N > N₀ algorithm A is faster than algorithm B.  Show how you know that this is the correct integer.

   • In class we saw that access to any element of a 2-dimensional array is constant-time.  If each item of an M rows and N column array contains b bytes, and L is the memory address of A[0][0], then the address of A[i][j] is L + b*(i*N + j), so two multiplications and two additions are needed regardless of the dimensions of the array.

     A lower-triangular matrix is a (we’ll restrict it to) square matrix (i.e., N x N for some N) in which every element above the main diagonal is zero. I drew a diagram of this on the board in the Day 17 class.  By “above the main diagonal”, we mean an element whose column number is larger than its  row number.  The internal representation of a triangular matrix should be a one-dimensional array.  Since almost half of the positions in the matrix are guaranteed to always be zero, it is not necessary to explicitly store them in the representation array, so we can save almost half of the space needed for a “normal” square matrix with the same number of rows and columns.  Note that the sum, difference, or product of two lower triangular square matrices is lower triangular, so these operations can (and should!) do considerably less work than the corresponding operations for “normal” matrices.

     (a)  Show the order in which the elements of an N x N lower-triangular matrix can be stored in the computer's (one-dimensional) memory.

     (b)  Given your storage scheme, give the formula for calculating the address in memory of A[i][j] where j ≤ i.  Use A,  L, and b to represent the same things as in the formula from the first paragraph of this problem.   Your formula should be computable in constant time.

Turn-in Instructions

Turn-in your individual work by committing it to your SVN repository. Commit your work on Markov  and Minesweeper work to your team repository. You do not need to turn in the final exam practice problems.