The project is an implementation of an advance algorithm. The implementation can be in any language. The program, including the inputs, and running the test cases can be done as a group. Each student should write and submit their own report.
Your program can use data structures included in typical libraries, for example java.util.
The program should be run many times to:
1. Demonstrate correctness, meaning that program produces the correct output for typical and unusual cases. This is much like debugging runs.
2. Illustrate algorithm cost for different input sizes and types. This can also include different
The main class for the algorithm should document
1. Algorithm name
2. All members name
3. Date
4. How to run
The project program will probably have programs to generate input cases, document at the main class
1. Input type
2. Author
3. Pseudo code
4. How to run
Each major class or method of the project should include documentation giving:
1. Author of the class or method
2. Cost of the method
3. Description/algorithm
If your program uses a data structure from a library you should document the instantiation of the object and explain by associate with the pseudo code.
The report should be written using Time New Roman (or similar serif font) 12 point font and single line spacing. Use a file format that I can read: pdf, doc (not docx), html, sxw. Do not use ascii text format for the report. Each section of the report (listed below) should a title in larger font. Embed the figures (diagrams, plots, and tables) where they are first discussed in the text. Be sure to discuss all figures in the report. All figures should have a caption that thoroughly explains the figure.
The report should include:
The bold represents appropriate section titles; these should be in 14 point bold font. You may and probably will have subsection titles for some sections; these should be in 12 point bold font. You should be able to delineate the extra material requested by me in the subsections.
1. Title page, witch includes the Algorithm name, report author name, other group members names and the date
2. Problem. Description of the problem that the algorithm solves
3. Real Life Examples. Substantial example of the problem. Give substantial examples. Explain the inputs, for example if the input is a graph then what the vertices and edges represent.
4. Complexity. Explain the complexity of the problem (this need not be a proof)
5. Algorithm. This is a verbal description
6. Algorithm Correctness. This can be a proof or an argument.
7. Pseudo Code. Only for the top level of the implementation
8. Cost analysis. This should be the complete cost for all the different input cases and data structures used.
9. Implementation. Description of classes used and difficulties during implementation.
10. Correctness Runs. Description of correctness runs and why you used these cases. This should explain what input is used and why. You may need to explain the expected output.
11. Correctness Runs Results. Results of correctness runs. Give the input and output. Make a conclusion.
12. Cost Runs. This is a description of the cost run, should explain the different inputs and expected output.
13. Cost Runs Results. This section should include graphs, and verbal description for different input types and data structures.
14. Cost Runs Discussion and Conclusion. Compare the different cost runs and make a conclusion.
15. References. Web resources are permitted
16. Introspective Questions.
a. What did you learned from the project?
b. Do you prefer project or final, and why?
c. What suggestions do you have for future semesters of Algorithms?
17. Running Code. Description of how to run your program including generating test cases. Give the names of the main classes.
18. Program Printout. This should be in a fixed spacing font. Make sure it well formatted. Make sure the classes or files are listed in appropriate order, generally from top level to bottom level code. Use separate sections for code generating input, algorithm, processing the output.
There is no page minimum, but I suspect that the report will be rather long, given the graphs.
Write clearly and concisely but in complete sentences. Remember, I will have to read 40 reports. Consequently, please avoid unnecessary words. Words such as "great" are subjective and at best attempt to persuade the reader. Remember you are writing for a technical audience; they are not persuaded by subjective words, instead they suspect that your writing lacks content. When you proof read your work, ask "does the sentence have substantially the same meaning without this word?"
You do not need to explain terms that I or your fellow students should know, for example vertices and edges in a graph.
Make reading easier by using formatting, subsections and proper titles. Characters representing mathematical quantities should be in italic, for example v is a vertex. You can use acronyms or abbreviations and associate them at the first occurrence of the full text, but they are not italic, for example minimum spanning tree (MST). Do not use too many abbreviations, about 5.
Do not just copy the pseudo code from the book. Copies do not convince me that you thought about the code. At a minimum retype the pseudo code, but better is to use the data structures you intend to use in your implementation.
Use proper subsection titles to tell the reader what the section is about. Do not use the title "Proof" instead use "Algorithm Proof."
Use tables and figures to help readers understand your results, for example when comparing the cost for different implementations, use a table for important results. It is ok to use bullets list, but they must be explained in complete sentences.
Be specific about the "real life" examples. General examples or incomplete examples do not add much to the abstract problem description. In your examples describe the specific inputs to the algorithm and its output. "Real life" examples are one of most important section, and represents how much you have really thought about the problem. I will read this section thoroughly.
Please try to answer the introspective questions thoughtfully. This is another section that expresses your own thoughts. I will read this section thoroughly.
Proof read your report several times. I recommend rereading after you have not look at your draft for 24 hours.
The project is due early final's week, specific date coming. Please try to submit them earlier. Submit by email sent to me rpastel@mtu.edu with subject line:
cs4321 - final project submission
I will reply that I have received the project with 24 hours.