CPSC 221H-200: Data Structures & Algorithms
Programming Assignment #5 (Term Project)
Spring 2009

General Guidelines for Programs

• Your code should be well designed and documented. You WILL be graded on programming style.
• If the question is not fully specified, you may need to make some assumptions. In this case, you must state any assumptions you make, and justify why they are reasonable.
• Everyone must turn in their own copy of the assignment. You may consult outside material or work with others (this is encouraged), but you must reference your sources (people, books, webpages, etc.). These must be listed on the cover sheet mentioned below.
• Be clear and precise. Write neatly and legibly. Justify all answers, even if not specified in the question. Use good judgement concerning how detailed to make your answer.
• Code will be turned in electronically using the turnin program on CSNet.
• The report portion of the assignment, if any, follows conventions for other written assignments in this course. In particular, all assignments in this course must include a completed and signed coverpage available on the course homepage. Any assignment turned in without a fully completed and signed coverpage will receive ZERO POINTS.

Assignment

Schedule of Deliverables:

• Friday April 17, 2009 - Interface Design Due: The interface/code design should be submitted electronically by 5pm
• Tuesday April 28, 2008 - Project Progress & Presentation: A progress report & in-lab presentation
• Thursday April 30, 2008 - Final Report Due: Code due by April 29 at midnight. Extended to May 5

Project Requirements

In this project, you will design and implement a graph data structure and a set of algorithms on it. You will work in pairs, each participating in all stages of the project. There will be 3 milestones that each team must satisfy:

• Interface Design: You must submit a written design of your graph and algorithms by April 17. In addition to the implementation design, you should describe any assumptions you are making as well as expected complexities.
• Project Progress & Presentation: Each group will give a short (10min or less) presentation in lab on April 28. The presentation should cover your design as well as current progress.
• Final Report: Each group will prepare a final report due by May 5, with all code turned in electronically by April 29 at midnight.

Graph Requirements

You will implement a graph data structure capable of representing a directed graph that can be read in through a ASCII file. The data file will have a simple structure where each line represents a directed edge by 3 numbers:

EXAMPLE: < source vertex > < weight > < destination vertex >
1 5 2
2 3 3
3 3 3
1 2 3
3 0 2

You may assume that all 3 numbers are non-negative integers.

Graph Algorithms

You may choose to implement one of the two options of graph algorithms:

1. Option 1: Path Algorithms
   • Breadth First Search (BFS)
   • Single Source Shortest Path (SSSP): Dijkstra, Bellman-Ford, or any other of your choosing.
2. Option 2: Structure Algorithms
   • Clustering Coefficient
   • Page Rank

Graph Data sets

You should create a method to generate random graphs. You will also be supplied with "real world" graphs in the near future.

Interface Design (20 points)

The objective of the interface design is to give a framework for your project implementation. A programmer should be able to implement your project with as few questions as possible. You should include the following parts in your interface design report:

• Title, author, date.
• Introduction: Describe your project briefly. Provide a brief outline of the remainder of this document.
• Discussion of the objects/classes: describe the objects/classes you need and the relationships between them. Try your best to clearly describe them. You should present this using written explanations and diagrams showing the high-level design, and code snippets to show details of the planned interfaces, at least of the major components.
• List your class definitions and member data/functions for every class. For every member function, you need to specify the functionality provided by this member function: input and any member data needed, operations on the input and member data, output/results after this operation.
• List all additional data structures (other than the graph) that you will need to implement the graph algorithms. You should judiciously use the STL.
• List all other functions you will use and specify the functionality of every function.
• Include the .h files as an appendix to the report.

Project Progress Report & Presentation (20 points)

The objective of this report is to show how your project is going, to identify any issues that have come up, document any design changes, etc. This will also serve to inform your classmates of your teams design decisions. Your presentation should address following issues:

• Introduction: Describe your project briefly. Provide a brief outline of the remainder of the talk.
• Project Design: Describe your chosen design for both the graph & algorithms.
• Current Status: Give a description of the status of your project. Have you found any unforeseen problems? Did you have to augment your original design? Are you completely finished ?!?!?
• Conclusion: Briefly describe the current status and provide an expectation of your future progress.

Final Report. (40 points)

In your report you need to clearly describe your problem, discuss what data structures (other than the graph) are used and the reasons why you selected them (improve time complexity or other reasons), any other possible data structures/algorithms may be used and the reasons you did not use them, theoretical analysis of the complexity of your solution, experiments you tried and the reasons you did these experiments, comparison of your theoretical analysis and experimental results, and conclusions you made for your project. Your report should be well structured like the previous lab reports.

Coding Portion. (20 points)

The TA/instructor should be able to compile and run your program correctly with test data.