You may work with a partner on this project. That means a team of 2, not 3 or more. If you work with a partner, you may submit one copy of the project, with both names included on it.
Regardless of the programming language you use, you are expected to turn in well structured, well documented code. For guidance, you can refer to the CS Program Style Guide and CS Program Documentation Standards. The specifics will obviously vary from one language to the next, but these standards should give you a starting point.
Your program should use the adjacency list representation of a graph. You may use the Java Priority Queue class or the Python Heapq library for your heap in the second implementation. If you copy or modify code from any online source you must include a link to your source in your program documentation, along with descriptions of the modifications that you made.
You may decide if your program will get the graph information as input from the user or if it will read the graph information from a file. The Algorithms Illuminated site has sample data and test cases you may use and/or modify.
Another issue that will require some thought is specifying the basic operation for the different algorithms (i.e., what are you counting?). If you use different basic operations for different algorithms, you will need to take this into account when you compare performance. You should include appropriate counters in your code to be used in comparison with the expected running times.
Your analysis should take the form of a 2-3 page paper (including figures if appropriate). Your paper should 1) Describe the algorithms that you implemented, particularly any modifications that you had to make to the algorithms as they are presented in the textbook. 2) Discuss the predicted time complexity, and 3) compare the empirical performance of the algorithms with each other, as well as with their predicted performance. Your paper will be graded on content as well as style. Grammar, spelling and readability count. You should cite any outside sources of information that you use. All figures should have captions and clearly labeled axes. Equations should be typeset with a proper equation editor.
Your archive should contain at least two files in addition to your code. The first will be the write-up described above. The second will be a plain-text README file that includes all of the information necessary for me (or anyone else) to run and understand your code. The README should include your name, the name of your partner (if any), and brief descriptions of all of the files included in the archive. More importantly, it should include clear instructions for running your code. The README is also the place to fill me in on any quirks in your implementation that I should know about. For instance, if your implementation only works on odd sized inputs, you should let me know. Undocumented bugs will tend to have a greater impact on your grade than documented bugs.
| Comments and Documentation: | 4 |
| Implementations (2): | 8 |
| Write-up: | 4 |
| Total: | 16 |