Data Structures	CS106
Haverford College	Spring 2011
Term Project	Due: end of Spring Term

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 in cs105 & cs106 .

You are invited to propose your own project, or complete one of those suggested below. You are welcome to work in pairs or individually; however, both members of a pair must contribute to the final result in a demonstrable way.

Evaluation of term projects will be completed by an appointment during "finals week." 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