Explore the use of more powerful data structures with Markov.
Finish the Team Mini-project
Implement Linked List methods
MyLinkedListReal
project. remove
method) .Team work: Work with your assigned team for the Minesweeper/Markov programs.
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 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.
|
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 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.