CS100, Spring 2000, Project 6 Milestones

This is the second of 4 documents for Project 6:

    1. Project 6 Write-Up
--> 2. Project 6 Milestones
    3. Project 6 Tips
    4. Project 6 What To Hand In

The Milestones are partly independent, but are presented in a suggested order.
We suggest you work on the Milestones one at a time instead of all at once;
this lets you focus on understanding each one.

See the parallel document Project 6 Tips and also check for the forthcoming
document Project 6 What To Hand In.

*******************************************************************************
Note: Eventually you will want to organize methods in certain classes.  For
now, they mostly can be static methods in the main/target class.  Similarly,
eventually you will be required to use encapsulation, but don't worry about
that now.
*******************************************************************************

===============================================================================
Milestone 1: Array Constants and Displaying Arrays
===============================================================================

Write methods $void print(int[] a)$ and $void print(int[][] a)$ to display the
contents of 1-dimensional and 2-dimensional arrays of integers.  Test your
methods on the arrays below.  Use initializer lists or anonymous arrays to
succinctly create these arrays (they are sample data from the Project 6
Write-Up).

table1: 17 20  8  7 12
               
table2:  0  8  2  3  4
         6  3  4  1  6
         3  3  1  1  0
         4  1  1  0  1
         4  5  0  2  1

table3: 8 3 3
        5 2 6
        6 3 4

table4: 9 2 4
        7 5 3
        5 4 1

===============================================================================
Milestone 2: Transform
===============================================================================

Write a method $String transform(String top, String bottom, String text)$ to
return the String result obtained by transforming a String $text$ according to
the key with top line $top$ and bottom line $bottom$.  (It does not matter
whether the key is an encryption key or a decryption key.)

To transform a character, search for it in the top line, and replace it by the
corresponding character in the bottom line.

Notes-- READ CAREFULLY!--: 
+ Allow $top$, $bottom$ to have upper-case and/or lower-case letters.
+ Transform upper-case letters in $text$ to upper-case letters in the result.
+ Do not change characters in $text$ that are not in the top line.

Use your method to encrypt and decrypt "We Apologize for the Inconvenience"
using the Caesar cipher.  Use both representations below (from the Project 6
Write-Up):

    abcdefghijklmnopqrstuvwxyz  <--  alphabet
    defghijklmnopqrstuvwxyzabc  <--  encoding of each letter of the alphabet

and

    abnocdgpwxyefqrstuvhijklmz  <--  alphabet, in random order
    deqrfgjszabhituvwxyklmnopc  <--  encoding of each letter of the alphabet

===============================================================================
Milestone 3: Tally
===============================================================================

Definition: a "unigram" is a single letter, a "bigram" is a pair of letters.

Write a class $Tally$ with these fields:

+ $total$:   the number of unigrams (same as the number of bigrams)
+ $unigram$: one-dimensional table of unigram tallies (integer counts)
+ $bigram$:  two-diemnsional table of bigram tallies (integer counts)

That is, subject to the Conditions below, these variables have these values:
+ $bigram[i][j]$ = number of times 
                   character $i$ is immediately followed by character $j$.
+ $unigram[i]$ = number of times character $i$ appears
               = sum of $bigram[i][j]$ for all $j$
               = sum of $bigram[j][i]$ for all $j$.
+ $total$ = sum of all $bigram$ entries = sum of all $unigram$ entries.

Conditions:
+ Treat non-letters and punctuation as spaces.
+ Ignore double spaces, i.e. don't count them.
+ Treat (e.g. convert) upper-case letters as lower-case letters.

Write constructors $Tally(String s)$ and $Tally(TokenReader in)$ that
initialize the fields according to the frequencies in String $s$ or the
contents of the file represented by TokenReader $in$.

NOTE: Conciseness counts.  Do not duplicate code for computing bigram and
unigram tallies: If you need the code more than once, then appropriately define
and use a method.


Test your code on this example from the Project 6 Write-Up:

    "a aaa abba abc ac ad ada add baa bad cab cb cdc dab dad dada dc"

Visually compare the tallies with $table1$ and $table2$ from Milestone 1: to
get started, you might wish to assume there are only spaces and the letters 'a'
through 'd'.  However, make sure you write your code so that it is easy to
modify to work for spaces and all the letters 'a' through 'z'.

Be sure to test your code on text containing double spaces, punctuation, and
both upper-case and lower-case letters.

Data files for additional sample data will be provided later.

===============================================================================
Milestone 4: Distance
===============================================================================

Write methods 

    $int distance(int[] a, int[] b)$ and $distance(int[][] a, int[][] b)$

to return the "distance" between two 1-dimensional arrays or between two
2-dimensional arrays.  Assume the two arrays have the same size.

The "distance" between two arrays is computed by adding the absolute values of
the differences between corresponding (in the same position) elements.


1-dimensional examples:

The distance between [a b c] and [w x y] is |a-w| + |b-x| + |c-y|.

The distance between [3 0 2] and [4 5 8] is |3-4| + |0-5| + |2-8| = 12.
(Note: this was originally posted with incorrect answer "11" instead of "12".)


2-dimensional examples:

The distance between [a b] and [w x] is |a-w| + |b-x| + |c-y| + |d-z|.
                     [c d]     [y z]

The distance between [1 2] and [6 7] is |1-6| + |2-7| + |3-5| + |4-1| = 15.
                     [3 4]     [5 1]

The distance between $table3$ and $table4$ from Milestone 1 is 16.

===============================================================================
Milestone 5: Swap
===============================================================================

Write method $void swap(int[] a, int i, int j)$ to modify 1-dimensional array
$a$ by swapping the elements at positions $i$ and $j$.

            0   1   2   3                                    0   1   2   3  
          +---+---+---+---+                                +---+---+---+---+
Ex: swap( | 2 | 7 | 1 | 8 | , 2, 3) makes the array become | 2 | 7 | 8 | 1 |.
          +---+---+---+---+                                +---+---+---+---+


Write method $void swap(int[][] a, int i, int j)$ to modify 2-dimensional array
$a$ by swapping columns $i$ and $j$ and rows $i$ and $j$.  (It doesn't matter
if you swap the rows first and then the columns, or the columns first and then
the rows.)

Example using $table2$ from Milestone 1:

                                                0  4  2  3  8
                                                4  1  0  2  5
$swap (table2, 1, 4)$ makes the array become    3  0  1  1  3
                                                4  1  1  0  1
                                                6  6  4  1  3


                                                0  4  2  3  8
                                                6  6  4  1  3
This is because swapping columns 1 and 4 yields 3  0  1  1  3
                                                4  1  1  0  1
                                                4  1  0  2  5

and then swapping rows 1 and 4 yields the answer shown.