CSC 222: Data Structures and Algorithms, Fall 2008

Assignments

Friday, August 29:

Read Chapter 1 through Section 1.5; bring questions to discuss

Friday, September 12:

Programming Project 1: Weiss, Exercise 1.14.

Using the Collection class in /home/libs/dataStr/pp1/ as a starting point, implement an OrderedCollection class which supports the operations isEmpty, makeEmpty, insert, remove, findMin, and findMax. Also write a test program which will help confirm that your class works correctly, and which will help you determine the running time for each of the operations (which should be noted in a comment in the code).

It is OK to work singly or in pairs (keep in mind the collaboration advise from the syllabus). When you are finished, put your files in a pp1 directory in your named directory under /home/libs/dataStr/students/, then send me an email telling me who worked on the project and where it is saved.

Monday, September 22:

Chapter 4, Exercises 8, 9, 19, and 31

Friday, October 3:

Programming Project 2

Monday, October 13:

Chapter 5, Exercises 1, 2, 5, and 10; Chapter 6, Exercises 1, 2, 3, and 8

Friday, November 7:

Programming Project 3:

Write a program which will efficiently perform the following operations (allow the user to choose these from a menu):

• Read place information from /home/libs/dataStr/pp3/placese.txt (roughly places east of the Mississippi)
• Read place information from /home/libs/dataStr/pp3/placesw.txt (roughly places west of the Mississippi)
• Ask for a place name (for example, "Greencastle") and display information about all the matching places
• Ask for a number, n, and display the nth largest place from those which have been read in
• Quit (this one is easy...)

The files of place information, which are based on data from the U.S. Census Bureau, have the following format on each line:

place name (40 characters wide; may contain spaces)
state abbreviation (2 characters)
population (10 characters, right justified)
degrees latitude (11 characters, prefixed + for North)
degrees longitude (12 characters, prefixed - for West or + for East)
				

For example, placesw.txt starts as follows:

Adak Station                            AK      4633 +51.842900 -176.640278
Akhiok                                  AK        77 +56.977320 -154.217551
Akiachak                                AK       481 +60.871740 -161.403575
Akiak                                   AK       285 +60.885659 -161.192264
Akutan                                  AK       589 +54.136299 -165.786036
Alakanuk                                AK       544 +62.675611 -164.643602
Alcan                                   AK        27 +62.722977 -141.188178
Aleknagik                               AK       185 +59.285485 -158.628962
Allakaket                               AK       170 +66.545170 -152.733117
Ambler                                  AK       311 +67.076879 -157.918155
Amchitka                                AK        25 +51.567103 +178.877380
				

If the user chooses to read both files of place information, then the queries should search the combined list of places. We will discuss appropriate data structures and algorithms in class; be prepared to make suggestions.

Wednesday, December 10:

Programming Project 4: Six Degrees of Separation

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
		    	

The file imdb.txt is data 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. Once you get your program working efficiently, imdb2.txt is a larger file of movie data.

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/pp4/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.

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