Introduction to Data Structures	CS206
Haverford College	Spring 2008
Term Project	Due: May 2, 2008

As a course capstone project, you are asked to design and implement a more substantial application which utilizes some (if not all) of the various concepts in algorithms and data structures covered.

You are invited to propose your own project, or complete one of those suggested below. You are welcome to work in small groups of 2-3 or individually; however, all group members must contribute to the final result.

Evaluation of term projects will be completed during lab on Friday, May 2, 2008. This evaluation consists of review of the source code, a demonstration of the project, as well as responses to questions posed by the instructor.

Enigma Simulation

An overview of the Enigma Machine and Cipher Technique is presented at http://www.trincoll.edu/depts/cpsc/cryptography/enigma.html or http://en.wikipedia.org/wiki/Enigma_machine.

• Design and implement an application to simulate the Enigma machine -- it is suggested that you utilized an object-oriented approach and consider the component objects of the machine.
• Demonstrate that your application works by encoding and decoding messages.
• Develop a "code-breaker" routine that assumes a given Enigma machine and an encoded message, and attempts to decode the message. Two approaches can be tried.
  • brute-force
  • heuristic search of your design
• Compare the performance of the two approaches using timing data (actual or simulated by accumulating execution counters). Include comments that explain the results.

Checkers Game

• Design and implement an application to maintain a checkerboard and game state as two persons play a game of checkers -- the application should accept input (text is fine) for moves, mutate the board and game state on valid moves only, output the new game state, and realize when a game has been decided (and who won/lost).
• Demonstrate that your application works.
• Develop another object to play a game as one of the persons -- please keep the algorithm simple, look ahead with a reasonable strategy to evaluate board strength.

An online game with basic rules (you do not need this level of graphic IO) - http://thinks.com/java/checkers/checkers.htm