CS127 Final Project

You may work in pairs for this assignment.

What to hand in

• A readme file that conains
  • A description of your program and its features.
  • A description of your program's command-line syntax.
  • A description and justification of the main data structures your program uses.
  • A discussion of the current status of your program, what works and what doesn't, etc.
• Your program's source code.

Grading Criteria

• Successful compilation. If your program doesn't compile, I won't grade it.
• Correctness. Your program needs to do the job it's intended to do.
• Design. I will look for well-considered choices of data structures, classes, and member functions, their return values, and their parameters. In the description of your project, you should explain your reasons for making the choices you made.
• Style. I want to see good indentation, descriptive variable and function names, well-placed comments, consistent loop structure, and so on. Ideally, your code will be a pleasure to read. (This assumes a reader who enjoys reading program code, but you're in luck, since I am such a reader.)
• Documentation. Your description of your project and the comments in your source code are important parts of your project. I want to be able to understand your project fairly well before diving into the code.
• Performance. I will not run precise time tests, but I will frown on text editors that take 5 seconds to search for a word and changeling programs that take 10 minutes to process a single word pair.

Project Option #1: Changelings

For example, one solution to the changeling "CAT to DOG" is "CAT, COT, DOT, DOG." The intermediate words must, of course, be words (and in fact, my crossword books say "words beginning with a capital letter, slang, obsolete words, and contractions are not allowed"). Note that in this example, we have the smallest possible number of words, since CAT and DOG differ in three letter positions, and there are three letter transitions in this solution. In a contest of changeling solutions, short solutions win. (Actually, short and clever solutions would be better than the short and dull solutions that are most common, but I won't ask you to write a program to judge cleverness.)

For this project, you will write a program that uses a dictionary to compute solutions to changelings.

To make your changeling programs uniform (so it's easy for me to test them all in the same way), I want you to implement the following command-line interface. The user should be able to run your program in one of two ways. First,

changeling dictionaryfile firstword secondword

changeling dictionaryfile changelingfile

So, how are you going to compute changeling solutions? There are undoubtedly many ways to solve this problem, but here is one way. Build a graph out of the dictionary file where each word is a vertex of the graph and two words/vertices are connected if they are the same length and differ by only one letter. Then use a breadth-first search starting at the first word until you find the second word. Then print out the path, if any, that you discovered in this way.

Building the graph can be done more efficiently than by comparing every pair of words (an Omega(N^2) process that would take a long time on an 80,000-word dictionary). How to do so is part of what you need to figure out.

Think about this problem before running to the computer to start coding. It's not easy, but the program should be lots of fun to play with when you're done.

Project Option #2: C++ Profiler

Profilers are most frequently used to help programmers improve their programs' performance. By first finding out what portions of your code get executed most frequently and for the longest total time, you can concentrate your fine-tuning efforts where they will have the greatest effect. It also turns out that profilers can help in tracking down tricky bugs. You can find an interesting discussion of profilers in More Programming Pearls, Confessions of a Coder, by Jon Bentley, Addison-Wesley 1988.

For this project, your job is to write a program that will take C source code as input, and produce C source code as output. The output source, when compiled and run, will perform its expected task, but will also dump profiling information to a file.

Your profiler should report the number of times each of your functions (including main()) gets called, and the total time consumed by each function.

If you get your timing and function-call-counting done, you might try to implement line-count profiling.

You could also modify your timing reports to take into account the fact that functions call other functions. For example, suppose main() calls bigfunction(), which in turn calls littlefunction(), and none of them calls any other functions. If the entire program takes 2 seconds to run and bigfunction() takes 1.5 seconds to run, and littlefunction() takes .2 seconds to run, you could report:

main:  2 s
bigfunction: 1.5 s
littlefunction: .2 s

main:  .5 s
bigfunction: 1.3 s
littlefunction: .2 s

Advice

Plan the order in which you are going to implement the features of your program. You need a list of code segments to write, along with ways to test them. If you design a sequence of small, testable steps for your development, you'll be much more likely to finish your program successfully than if you try to write large blocks of code before testing anything. Planning ahead may seem the stodgy way to go, but it's also more successful in the long run (and, usually, in the short run, too).

Ask questions. I will be very happy to help you when you're stuck. Pride and a two-week deadline don't mix very well.

Start early, have fun, and keep in touch.