CSC 222: Data Structures and Algorithms, Spring 2008

Assignments

Thursday, February 7:

Chapter 1, Exercise 21. Get it to run under Linux, and put the resulting files in your directory under /home/libs/dataStr/students/. You may either put all of the functions (including main and the class definition) in a single source file, or you may split them up for separate compilation using a Makefile as discussed in class.

Tuesday, February 19:

Chapter 3, Exercises 18 and 44, and determine the running time of numUnique;
Chapter 4, Exercises 9, 26, and 27.

Friday, March 7:

Programming Project 1 (Model Solution)

Tuesday, April 1:

Chapter 7, Exercises 18 and 17
Chapter 8, Exercises 11, 14, and 20
Chapter 10, Exercises 20, 22, 26, 28, and 31

Thursday, April 17:

Programming Project 2 (Skeleton)

Thursday, May 8:

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

Tuesday, May 13:

Final Project and Take-Home Exam: For the project, write a "Six Degrees of Separation" program. The input will be a file listing groups of mutual acquaintances (described below). The output will be the following pieces of information:

• The "diameter": the greatest distance between two people in the input, in terms of lengths of chains of acquaintances, followed by an example of a chain of that length;
• The name of the person closest to the "center" of the input, in the sense of having the smallest average distance to everyone else.

The format of the input is that it consists of a series of lines, with at most one name per line. Blank lines terminate groups of mutual acquaintances. For example, in the following:

Dave Berque
Doug Harms
Brian Howard
Adebayo Olowoyeye
Khadija Stewart
Scott Thede
Gloria Townsend

Paul Bender
Jon Dellett
Brian Howard
Verne Leininger
John White
Lee Williams

		    	

Each of the first seven people knows the other six, and each of the six people in the second group knows the other five. The only name in common is Brian Howard (gee, I wonder why that is...), therefore the output should be something like this:

Diameter: 2
Dave Berque knows Brian Howard
Brian Howard knows Lee Williams

Center: Brian Howard, with average distance 1.0
		    	

Here is a data file derived from IMDB, so that you can test the "Kevin Bacon" hypothesis. Note that in this case, "acquainted with" means "appeared in a movie with"; it may well be that some of these people know each other in other ways, but we don't count that.

Here is a simple program which shows one way to read in the input:

#include <iostream>
#include <fstream>
#include <string>

using namespace std;

int main()
{
    fstream fin("/home/libs/dataStr/final/imdb.txt");
    string name;
    int n = 0;
    
    while (getline(fin, name)) {
        if (name == "") {
            cout << "Found a group of " << n << " names" << endl;
            n = 0;
        } else {
            // Got another name for the current group
            n++;
        }
    }
    
    return 0;
}
		    	

You may rely on the last line of the input file being blank. You may also assume that the acquaintance graph is connected -- that is, everyone is connected to everyone else by a chain of finite length.

Both the project and the rest of the exam should be completed individually. You may consult with others only on general information about C++, the STL, and the book's classes. There are two additional written parts to the exam:

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:
   • 816: Abbott's Revenge
   • 821: Page Hopping
   • 840: Deadlock Detection
   • 869: Airline Comparison
   • 879: Circuit Nets
   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 5 pm on Tuesday, May 13. The project should be completed by that time as well — send me email as usual, telling me where it is saved.

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