PROGRAM #4

Fall 2008

Due: December 1, 2008, 5pm on eLearning

General Guidelines:

  • This submission should be accompanied by a cover sheet which is a single page document that contains all the information listed in this sample cover sheet: Word or PDF. Assignments without a cover sheet will NOT be graded.
  • For this assignment you may work in teams of at most two (including you).  Team work is not required but recommended. You are free to choose your partner. You may also consult with others or refer materials online, but you MUST reference (or give credit to) your sources (people, books, webpages, etc.). These sources must be listed on the cover sheet mentioned below (no points will be deducted). However, the final material for submission should be entirely written by you. Directly reproducing source codes or verbiage from any other student’s assignment(s) will be considered plagiarism, and therefore will be awarded zero points AND subject to the WSU Academic Dishonesty policy. Wherever possible reuse the source code given in the Weiss textbook, which can also be accessed from: http://www.cs.fiu.edu/~weiss/dsaa_c++/Code . You can also use any other standard library functions or STL implementations for any component of your assignment.
  • Grading will be based on correctness, coding style, implementation efficiency, exception handling, source code documentation, and the written report.
  • Submission: All assignments with cover sheet should be zipped or tarred into one archive folder (named after your last name as follows: "Program4<YourLastName>.zip"), and attached by email and sent to “All Instructors” and “All Teaching Assistants” through the eLearning website. Submissions are due by 5pm. A penalty of 10% will be assessed for late submissions within the next 24-hour.
    Note: Submissions will be accepted only through eLearning. Any submission outside the eLearning portal will be discarded. Also, we will not be able to send out acknowledgements for each submission. If there is something missing in your assignment/attachment we will contact you directly.

There are two problems in this assignment. You have to pick and choose the best suited data structure(s) and algorithms to implement the respective problems. I expect that you will end up using union-find, sorting, and hashing. You are also free to use any other data structure covered so far in this class, as long as you can justify its appropriateness in the report. Obviously, the idea is to come up with the implementation that can guarantee the best performance, and the grading will depend on this factor.

PROBLEM#1    Group Cities By Country

(50 points)

Given a set of n cities (along with the statement of which country each belongs to), your task is to group & list them by their country. 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 example input file.

Your output needs to list all the cities belonging to each country together. For example, the output can look like:

USA

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

Australia

Canberra, Sydney, Perth, …

            …
 
 

 

 

 

 

 


Your API should look like the following.

Class CityGrouper {

public:

            CityGrouper(string InputFileName);

void GroupCitiesByCountry();  // this function should do the output

// any other member functions and private data stores as you deem appropriate

…

}

 
 
 

 

 

 

 

 

 

 


Submit all source code in a source folder archive called Problem1.zip

PROBLEM #2    Group Cities Connected by Air Routes:

(50 points)

Relation: Two cities are said to be “connected” if there exists an air route (or path) from one to another.

The above is an equivalence relation because it satisfies:

i)                    Reflexivity: All cities are connected to themselves (implicitly).

ii)                  Symmetry: If city A is connected to city B then B is also connected to A (i.e., all connections are two-way).

iii)                Transitivity: If A is connected to B, and B is connected to C, then A is connected to C.

Given a set of pairwise city flight connections, your task is to group & list all the equivalence classes defined by the above relation. The input will be provided in the form of a comma-delimited text file, in which each line lists two cities that have a direct flight between one another.

Here is an example input file.

Equivalence Class #1

            All cities connected in this class…

 

Equivalence Class #2

            All cities connected in this class..

 

…
 
You can decide on any user-friendly way to report your output. All that is required of the output is that you list all the cities belonging to the same equivalence class together. For example, the output can look like:

 

 

 

 

 

Class CityConnector {

public:

            CityConnector(string InputFileName);

void ReportConnectedCities(); // this function should do the output

// any other member functions and private data stores as you deem appropriate

…

}
 
Your API should look like the following.

 

 

 

 

 

 

 

 

Submit all source code in a source folder archive called Problem2.zip

Combined Report for Problems 1 & 2:

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

·         Problem 1. State the different design options you considered for solving this problem, and then justify the main idea(s) behind your final design.

·         Problem 2. State the different design options you considered for solving this problem, and then justify the main idea(s) behind your final design.

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.