[SOLVED] Cosc 520 assignment 2 advanced data structures

The objective of the assignment is to: (1) explore advanced data structures, and (2) benchmark
algorithms.
Consider the list of advanced data structures provided at https://iq.opengenus.org/list-ofadvanced-data-structures/, and https://www.geeksforgeeks.org/advanced-data-structures/ and
at https://en.wikipedia.org/wiki/List_of_data_structures. Other considerable advanced data
structures could be Fibonacci Heaps, Van Emde Boas Priority Queues, Dynamic Data Structures
for Graph Connectivity/Reachability, Splay Trees/Suffix Trees/Tries. And Persistent Data
Structures. Section V of the Introduction to Algorithms book, 3rd edition, by Cormen,
Leiserson, Rivest, and Stein (available online and free through UBC Library) contains
explanations of four advanced data structures that can be helpful. Select 3 comparable
advanced data structures.
Submission
To complete the assignment, submit the following:
1. A concise pdf report including
o Explanation of the selected data structure briefly and their potential applications,
o The time and space computational complexity of your data structures,
o A table summarizing the measured performance,
o Plots showing the run time complexity for large enough data. You can generate
synthetic dataset using Python functions. Aim for at least ten million data points.
Then, run your program with different implementations and compare their run
time in a plot. Include this analysis in your pdf file and explain if it supports your
analysis. If the plots contradict your analysis, analyze them carefully: double check
your implementation and review your analysis, provide justifications, and explain
your thoughts of why this is happening. Remember to upload your dataset on
the web and include a link to the dataset in the pdf file.
o An explanation of why you selected those data structures (what attracted them;
this is totally subjective and personal).

Use appropriate parameters to describe the complexity. You need to justify the
complexity briefly; and explain each parameters used and provide the formula with
appropriate references.
2. Python code comparing the data structures selected. You are responsible for generating
appropriate data sets for the performance profile. Provide any justification of your
choices in the report. Do not hesitate to contact the instructor (a quick email can save
you hours for misguided work!). Add the GitHub link of your implementations in the pdf
file.
As for Assignment 1, your code should
o Be well documented and clean.
o Include unit tests.
o follow common practises:
▪ appropriate class/variable/method names (not too long and meaningful),
▪ appropriate comments
▪ comments for each method should indicate input, output, and a short
explanation of the method
▪ clear setup and running instructions.
How to submit: Submit your PDF file to Canvas, which should also include the links to your GH
repository and the dataset you used for testing. Use the Association for Computing Machinery
(ACM) – Small Standard Format Template (Overleaf) for your report. Remove the ACM, journal,
and copyright information. The report should be between 5-10 pages, including plots and
references.
Usage of GenAI: The use of GenAI is discouraged. However, if you still decide to use online
sources or GenAI to generate your code, first, make sure it is correct and executable. Second,
make sure to include the resources you have used and/or mention that you used GenAI in your
report. There is no penalty of using available code, the only drawback can be that you might
not be engaged as writing the code yourself for your future references.
Grading rubric
Weights Subtotals

Report 30
Explanation of the data structures and applications/usage 10
Complexity analysis 10
Plots and comparisons 8
References 2
Code static 30
naming 5
comments 5
running instructions 5
code design 15
Code execution 30
syntax-error free, runs 10
unit tests run 10
convincing demo 5
performance 5
Cross-Check** 10

Examining and running one of your classmate’s assignment and grade it based
on the above criteria. It will be assigned to you by the instructor.
10
Total 100 100
**Cross-Check needs to be submitted within one week of the assignment submission deadline. Other than just
checking, use it as a learning opportunity. Include a rationale and degradation feedback and submit it through
email to the instructor: [email protected].