Name: Ajay Bisnath
Student Number: 24794543
Question 1 (1 mark)
Explain the relationship between this problem and more abstract computer science topics covered in class.
Part A – ChatGPT Answer:
N/A
Part B – Your Answer:
This problem heavily relies on concepts covered in class, such as sorting and search algorithms and maintaing ordered data structures. The leaderboard requires maintaing a list of runs sorted by time, which will require the use of insertion sort or merge sort to achieve. Efficient searching for leaderboard ranks and for other functions requiring searching our list will require the use of binary search to improve efficiency. Additionally, updating the leaderboard involves inserting elements into a sorted structure which is a common data structure operation.
Question 2 (1 mark)
What data do you need to store in the Leaderboard class?
What algorithm do you intend to use for each method?
Part A – ChatGPT Answer:
N/A
Part B – Your Answer:
The leaderboard class will store a list of runs, with each run consisting of two variables, time and runner name. Insertion sort will be used for both sorting the list initially and when adding a new run into the sorted list. This is because the focus is on keeping the list sorted overtime as entries are added, which makes insertion sort the most efficient method for this problem. Insertion sort has a complexity of O(n) when adding items to an already sorted list.
Merge sort, while more efficient for sorting larger lists, will not be used as we do not need to re-sort the whole list at any point past the initialisation. Merge sort has a complexity of O(n log n) when adding items to a sorted list, which as we can see, is less efficient that insertion sort. I have chosen to use insertion sort when creating the initial list for the sake of simplicity as it is unlikely the input will be large enough to make enough different to where merge sort is worth using.
Question 3 (5 marks)
Implement your design by filling out the method stubs in speedrunning.py.
Your implementation must pass the tests in test_speedrunning.py.
This question is assessed only on your code.
Question 4 (1 mark)
Give an argument for the correctness and complexity of your init() function.
Part A – ChatGPT Answer:
N/A
Part B – Your Answer:
The init() function is correct as it creates the list that stores our leaderboard, handles cases where no runs are provided by initialising an empty list and sorts through our initial input using insertion sort through the submit_run() function. It has time complexity of O(n^2) as in worst case we take n steps to to insert n elements for our initial sort.
Question 5 (1 mark)
Give an argument for the correctness and complexity of your submit_run() function.
Part A – ChatGPT Answer:
N/A
Part B – Your Answer:
The submit_run() function is correct as it fulfills its function of inserting runs into the list. It keeps the name and time grouped in a tuple and preserves the order of the list, keeping the leaderboard valid. We use binary search to find the insertion point which has a time complexity of O(log n). The overall time complexity of the function remains O(n), as that is what is required of the list insert, but using binary search will make the function faster in some cases.
Question 6 (1 mark)
Give an argument for the correctness and complexity of your count_time() function.
Part A – ChatGPT Answer:
N/A
Part B – Your Answer:
The count_time() function is correct as it fulfills its purpose of counting the number of runs with a specific time. It uses binary search, as our list is already sorted, in order to check the list of times, which has a time complexity of O(log n). The binary search must be run twice in case there are multiple runs with the same time, however, this has minimal impact on efficiency as the overall time complexity remains as O(log n). Using binary search is more efficient than using a linear scan, which would have had time complexity O(n).