CSC 222: Computer Programming II
Spring 2005

HW4: Experimentation & Design


Part 1: Experimenting with Collections.sort

In lecture, we considered the TimeSort class, which timed the Collections.sort method on a randomly shuffled ArrayList. Modify this class so that, instead of timing just one execution of the method call, it repeatedly calls the method (say 100 times) and averages the timings. The number of calls to average should be a constant so that it is easily changeable. Using your modified program, perform repeated executions and enter timings in the table below.

list size average timing over 100 method calls
5,000  
10,000  
20,000  
40,000  
80,000  

Does this data support the assertion that Collections.sort implements merge sort? Justify your answer.


Part 2: Class & GUI Design

Substitution ciphers that encode a message by substituting one character for another go back at least as far as Julius Caesar, who used a rotating character scheme to encode military orders. This simple type of encryption is vulnerable to statistical attacks, however, as anyone who has solved CRYPTOGRAM puzzles can attest. In World War II, the Nazi military employed an encryption scheme that addressed this weakness of simple substitution ciphers. This scheme, implemented by typewriter-sized devices known as Enigma machines, gave the Nazis a tactical advantage that greatly contributed to their early success in the war. In fact, the eventual breaking of this coding scheme by researchers at Bletchley Park, England (including Alan Turing) is hailed as one of the turning points of the war.

Enigma machines used interchangeable rotors that could be placed in different orientations to obtain different substitution patterns. In addition, the rotors rotated after encoding each character, so the pattern was constantly changing. While actual Enigma machines used as many as seven rotors to produce complicated character mappings, we will consider a simpler two-rotor model for this assignment.

To encrypt a character using a two-rotor Enigma machine, find the character on the inside rotor (i.e., the inner wheel) and note the character aligned with it on the backplate (i.e., the outside wheel), then find that character on the second rotor (i.e., the middle wheel) and output the one aligned with it on the backplate. After a character is encrypted, turn the inside rotor clockwise one step. Whenever the inside rotor returns to its original orientation, the second rotor turns once in lock-step, just like the odometer in a car.

For example, in this configuration the character 'A' would be encrypted as 'N', since 'A' on the inside rotor is aligned with 'H' on the backplate, and 'H' on the second rotor is aligned with 'N' on the backplate. After performing this encryption, the inner rotor is rotated clockwise, so the letter 'A' would next be encrypted as 'D'.

Note that decrypting a message requires following the same steps, only in reverse (i.e., find the character on the backplate, note the character aligned with it on the second rotor, find that character on the backplate, then output the character aligned with it on the inner rotor).

For this assignment, you are to design a Java class named Enigma that models the behavior of a two-rotor Enigma machine. You may assume that all Enigma machines have the same backplate, as shown in the above diagram. That is, the backplate consists of the 26 capital letters and the '#' symbol (representing a space) in the following clockwise order: #BDFHJLNPRTVXZACEGIKMOQSUWY. Since the rotors are interchangeable, however, their contents and alignment relative to the backplate must be specified when constructing an Enigma machine. For example, the initial settings of the inner and second rotors in the above diagram are #GNUAHOVBIPWCJQXDKRYELSZFMT and #EJOTYCHMRWAFKPUZDINSXBGLQV, respectively. Using an Enigma object, it should be possible to encode and decode text messages, with the appropriate rotation of the rotors occurring after each character encoding/decoding.

You should also design and implement a graphical user interface that makes it simple for the user to specify the rotor settings on an Enigma machine, and encode or decode text. Once you have your Enigma simulator working, test it by decoding the message   OKNNWRDHGERPILRLAMFZF#FMUC   using the diagram settings.