PROGRAM #5

Fall 2009

Due: December 4, 2009, 5pm on eLearning

General Guidelines:

  • All source code must be in C++. Windows or Unix environment is allowed.
  • Each submission must be accompanied by a cover sheet, without which it won’t be graded.
  • Team work is allowed (although not mandatory) for this project. Each team should comprise of at most two members. Although team work is recommended, grading will not differentiate between 1-member and 2-member teams. It is an option that is intended to encourage joint discussion and teamwork.
  • The final material for submission should be entirely written by you. If you decide to consult with others or refer materials online, you MUST give due credits to these sources (people, books, webpages, etc.) by listing them on the cover sheet mentioned below. Note that no points will be deducted for referencing these sources. However, your discussion/consultation should be limited to the initial design level. Sharing or even showing your source code/assignment verbiage to anyone else in the class, or direct reproduction of source code/verbiage from online resources, will all be considered plagiarism, and therefore will be awarded ZERO points and subject to the WSU Academic Dishonesty policy. (Reproducing from the Weiss textbook is an exception to this rule, and such reproduction is encouraged wherever possible.)
  • Grading will be based on correctness, coding style, implementation efficiency, exception handling, source code documentation, and the written report.
  • Submission: Submission policy same as for Program #4.

There are two problems in this assignment. You have to pick and choose the best suited data structure(s) to implement the respective problems. I expect that you will primarily end up using hash tables and/or union-find. You are also free to use other data structures covered so far in this class. Obviously, the idea is to come up with the implementation that can guarantee the best performance, and the grading will factor that in.

PROBLEM#1    Group Cities By Country

(50 points)

Given a set of n <city, country> pairs, your task is to group & list them by their respective countries. The input will be provided in the form of a comma-delimited text file, in which each line has the format: City name, Country name

Here is an input file for testing purposes.

Your output needs to list all the cities belonging to each country together, as follows:

USA

New York, Seattle, Austin, Los Angeles, ….

Australia

Canberra, Sydney, Perth, …

            …
 
 

 

 

 

 

 


Note: The order in which the cities are listed within a country group is irrelevant. So is the order in which countries are printed.

The program’s API should look like the following.

Class CityGrouper {

public:

            // this function should allow the user to load an input text file
            CityGrouper(string InputFileName);

// this function should perform grouping and print the output
void GroupCitiesByCountry(); 

// other member functions and private data stores
…

}

 
 
 

 

 

 

 

 

 

 


Testing: Test your code with the input file provided above. For this you will have to write a main() function.

“Problem1.zip”:  should contain the source code and the output of testing in a separate text file.

 

PROBLEM #2    Group Cities Connected by Air Routes:

(50 points)

You are given a database of flight connections, where an entry <A,B> means there are direct flights from both A to B and B to A.. Two cities are said to be “connected” if there is either a direct connection or a series of connections between them. A typical passenger is interested in answering the following two questions:

Q1) List out all equivalence sets of cities, such that each set contains all and only those cities that are connected to one another.

Q2) Given any two arbitrary cities, X and Y, is there a flight connection between them?

Implement a program that will allow users to answer both queries efficiently. You can assume that the flight database is input in the form of a comma-delimited text file, in which every line lists two cities that have a direct flight between them.

Here is an example input file.

Equivalence Class #1

            All cities connected in this class…

 

Equivalence Class #2

            All cities connected in this class..

 

…
 
The output for Q1 should look something like:

 

 

 

 

 

The output to Q2 is a YES or NO.

Class CityConnector {

public:

// this function should allow the user to load an input text file
CityConnector(string InputFileName);

// this function should compute the eq. classes and output
void ReportConnectedCities();

// this function checks whether two cities are connected
boolean CheckConnection(string city_1, string city_2);

// other member functions and private data stores

…
}

}
 
The program’s API should look like the following:

 

 

 

 

 

 

 

 

 

 

Testing: Test your code with the input file provided above. For this you will have to write a main() function. In this function, call ReportConnectedCities() once and print its output. After that, make a few calls to CheckConnection() doing arbitrary checks to test out if your code is working.

“Problem2.zip”:  should contain the source code and the output of testing in a separate text file.

Combined Report for Problems 1 & 2:

In a separate 1-page document (Word or PDF), compile the following two sections:

·        Problem 1. Briefly explain your choice for the data structure.

·        Problem 2. Briefly explain your choice for the data structure.

FINAL CHECKLIST FOR SUBMISSION:

    ___  Cover sheet

    ___  Problem1.zip

    ___  Problem2.zip

    ___  Report.doc or Report.pdf

    ___  All the above zipped into another folder archive called Program4<YourLastName>.zip for submission on eLearning.