SUNY Geneseo Department of Computer Science
CSci 242, Spring 2013
Prof. Doug Baldwin
Due Tuesday, May 7Backtracking is a search technique appropriate for problems whose solutions can be built up in multiple stages. Backtracking exhaustively builds all possible solutions by systematically trying every possible value for a given stage, and, for each such value, checking to see if a complete solution can be built from it. We discussed backtracking in our April 18 and April 30 lectures.
In the April 18 lecture we specifically talked about the problem of breaking substitution ciphers, and considered how a backtracking search through possible substitutions, supported by a dictionary for the language in question, could solve the problem. Problem set 13 asked you to implement a dictionary for this problem, based on a hash table. This exercise asks you to implement the backtracking part.
Write code to implement a backtracking search for substitutions that solve a substitution cipher.
In addition to writing and testing the program, add code to it to measure how long it takes to solve a cipher, and collect data for a variety of ciphers of various lengths. There are several ways you can organize the backtracking for this problem, and I am interested in seeing if different approaches have noticeably different running times.
You can write your program in any language you choose.
I expect that you will use the dictionary you developed in problem set 13. Alternatively, you can use my solution to that exercise, which I will make available after its grading date passes. My solution is written in Java, so you will probably want to write the rest of your substitution solver in Java if you use my dictionary.
One of the pragmatic issues you will face is that real substitution ciphers often contain people’s names or other words that don’t appear in most dictionaries. If you want to apply your program to such ciphers, you will probably need some way to ask users about words that don’t appear in the dictionary but that follow from otherwise consistent substitutions (for example, if your program detects that a certain substitution produces some words that are in your dictionary but a small number that aren’t, you could ask the user if those non-dictionary words are acceptable). You could also add such words to the dictionary if you want.
Substitution ciphers are popular as newspaper and magazine puzzles under the name “cryptograms.” A number of Web sites therefore offer substitution ciphers to the public to solve, and make good sources of test cases for your program. Some such sites include
A search for “cryptogram puzzle” or a similar phrase will probably turn up many more sites you can use as sources of test data.
A completely different approach to testing your program is to make up your own ciphers by hand. This lets you control exactly what words go into a cipher, and so avoids the problem of non-dictionary words. But it puts more burden on you to make up test cases, increases the chances of errors in those test cases, and may not be as fun as seeing your program solve a “real” cipher.
I will grade this exercise in a face-to-face meeting with you. Please bring your program to the meeting in some form that I can both read and run. During the meeting, I will look over your code, give you my reactions to it, answer any questions you have about it, etc.
Meetings should take between 15 and 30 minutes. Sign up either on the paper schedule outside my office or via Google calendar. Sign up for a full half hour, to be sure there is time to show me everything you have done. If you work in a group, the entire group can schedule a single meeting with me. Be sure your grading appointment ends by the end of the day on the due date above.
In addition to the grading meeting, I would like to compare your running time measurements in class on the due date. Please bring your data to class on that day, in a form we can all see (e.g., as a spreadsheet or slide we can put on the data projector, on a sheet of paper for the document camera, etc.)