CSC 222: Data Structures and Algorithms, Fall 2006

Assignments

Thursday, August 31:

Chapter 1, Exercise 21

Thursday, September 7:

Chapter 2, Exercises 19(a) and 26

Tuesday, September 12:

Chapter 3, Exercises 15 and 42

Friday, September 22:

Programming Project 1

Friday, October 27:

Programming Project 2 (Chapter 10, Exercise 44)
To start, copy the project files:

cd /home/libs/dataStr/students/YOURNAMEHERE
mkdir pp2
cp /home/libs/dataStr/pp2/* pp2
		    	

Tuesday, November 14:

Chapter 10, Exercises 15, 26, and 28;
Chapter 11, Exercises 13 and 21;
Chapter 12, Exercises 13, 14, and 26;
Chapter 14, Exercises 18 and 19

Thursday, December 7:

Chapter 16, Exercises 13, 15, 18, 19, and 32

Friday, December 15:

Final Project and Take-Home Exam: For the project, write a Word Ladder program. Using the file words.txt (all files are located in /home/libs/dataStr/pp3/), which contains over 100,000 english words, search for the shortest way to turn one given word into another, by only changing one letter at a time. There is a demo version in the file pp3demo; here is an example of using it:

$ ./pp3demo love hate
Found a path of length 3
love
hove
have
hate
		    	

You are free to decide what the interface should be, although to get full credit there will need to be a way to specify the starting and ending words without having to recompile the program (that is, don't compile them in as constant strings). If you wish, you may (without penalty) restrict the program to only work on words of a given length -- I have provided files named words04.txt through words17.txt which only contain the words of length 4 through 17 (although I doubt there are any interesting word ladders with 17 characters...). The program should let the user know how to specify the first and last words (for example, running ./pp3demo without any arguments produces the error message Usage: ./pp3demo first last, which is a common way for unix command-line programs to behave).

While the project may be done in groups of two or three (I have changed my mind on this), the rest of the exam should be completed individually. There are two parts:

1. Write a few paragraphs justifying your choice of data structures and algorithms in the project. Argue that you have made efficient choices with respect to the data to be processed.
2. Choose one of the following problems from the University of Valladolid programming contest archive:
   • 908: Re-connecting Computer Sites
   • 924: Spreading the News
   • 925: No more prerequisites, please!
   • 977: Old West Rumours
   • 988: Many paths, one destination
   Note that these problems are not all of equal difficulty -- you may want to discuss your solution ideas with me before making a final choice about which one you are going to work on. Your task is to analyze the problem and come up with appropriate data structures and algorithms to solve it. You do not need to produce finished C++ code to get full credit for this question, a description in english or pseudocode is sufficient (but I have to be able to understand what you mean). For extra credit, complete a C++ solution and get it accepted by the UVa online judge (you will need to register with the site to do this -- talk to me if you have any questions about this).

The written parts should be turned in to me, either in my office or by email, by noon on Friday, December 15. The project should be completed by that time as well -- send me email as usual, telling me who worked on the code and where it is saved.

DePauw University, Computer Science Department, Fall 2006
Maintained by Brian Howard (bhoward@depauw.edu). Last updated