CSC263 final project, Summer 2020
July 9, 2020
Please read the entire handout carefully before you begin
In this project you will design, implement, and analyze your own ADT to solve a unique problem. You will have the opportunity to resubmit the first two parts for full credit on the following part¡¯s due date, after receiving feedback.
Your individual grade for the project will consist of your group¡¯s total grade for parts 1, 2 and 3 scaled by your individual grade on the interview. The interview is designed to be easy if you understand every part of your own project.
Updates as of July 9:
The project is to be completed in groups of 1 to 3 students, and the size of the group will be considered when determining if the chosen ADT and implementations are suitably complex.
The element of randomness of one of your implementations in part 2 must affect the analysis of the data structure.
All due dates are at 10PM on the dates indicated.
Your analysis in part 3 should include a worst-case (time and space) anal- ysis for both implementations as well as amortized time or expected time for each implementation, for a total of six analyses.
Interviews are to be scheduled with your TA (assigned after submitting part 1) during the August exam period, or earlier if you choose to submit your project before the deadline.
You should cite any sources you use in APA format. Although we won¡¯t be strict about format, we will be very strict about trying to pass someone else¡¯s work as your own. You should be able to analyze your implementa- tions yourself, and you may be asked about any part of the project during the interview.
You may pick an ADT that has been covered in the course (or appears in the textbook) however your implementations may not be of those covered in the course (or appearing in the textbook).
If your implementations are too similar to another group¡¯s both groups will be asked to resubmit part 2. We will take instances of plagiarism very seriously.
1
Part 1.
Part 2.
Part 3.
10 %
Due July 18, 2020.
Describe a mathematical problem or real life situation, and an ADT to model it. Picking a problem and ADT may require some creativity, re- search in scholarly sources, or both.
You will be graded on how complex your problem is to model, and how appropriately your ADT models it. You should describe what data your ADT stores, and what operations it performs.
30 %
Due July 31, 2020. Optional: resubmit part 1.
Give two different implementations of your ADT from part 1. One of your implementations must include an element of randomness, and the other will be analyzed using amortization.
You will be graded on the correctness of your implementations, as well as their efficiency, although they need not be optimal.
60 %
Due August 17, 2020. Optional: resubmit part 2.
Analyze the time and space complexity of your implementations in part 2 using the techniques learned in class. In particular one of your analyses must use amortization, and one must consider the expected case of some random event.
You will be graded on the correctness of your analyses, as well as meeting all previous requirements.
In addition to your analyses, you will have interviews to be scheduled individually during the exam period, or earlier if you choose to hand in your project sooner.
2