• My work does not contain any instances of plagiarism and/or collusion.
• My work does not contain any fabricated data.

By uploading my assignment onto Learning Mall Online, I formally declare that all of the above information is true to the best of my knowledge and belief.

Percentage in final mark: 40%

Learning outcomes assessed:

A. Describe the different classes of algorithms and design principles associated with them; Illustrate these classes by examples from classical algorithmic areas, current research and applications.

C. Have fluency in using basic data structures in conjunction with classical algorithmic problems. 

Late policy:5% of the total marks available for the assessment shall be deducted from the assessment mark for each working day after the submission date, up to a maximum of five working days

Risks:

In this coursework, you are expected to design and implement algorithms to produce solutions to four given problems (Tasks 1-4) in Python. For Tasks 1-4, you should have function(s) to receive task input as parameters, implement your algorithm design and return results. You also need to write a short report answering a list of questions in Task 5 that are related to the given four problems.

Task 1 (15 marks)

Given an array representation of a Binary Search Tree (BST) without duplicate keys, update the array such that each key is replaced by the sum of all keys in the BST that are greater than it.

Explanation: To represent a binary tree of height ‘h’, we need an array of size 2 h+1 -1 with None indicating locations without a tree node. The binary search tree corresponding to the input [6, 5, 8, None, None, 7, 9] is shown in the figure, where the height of the tree is 2 and the length of the input array is 7. Keys 7, 8 and 9 are larger than 6, therefore, the root 6 is updated to 7+8+9 = 24.

You should create a function named BSTSum that takes a list which represents a BST and return a list show the updated values for each key. Please consider the time complexity when you design your algorithm. A naïve approach will result in loss of marks.

Suppose there are n projects P= [p1, p2 …pi …pn] that you need to finish for your clients. Each project pi= [timei, duedatei] need timei days to complete and must be delivered before or on duedatei. You can work on only one project at a time and must finish the current project before starting a new one. Assuming you start on day 1, design an efficient algorithm to find the maximum number of projects you can complete.

You should have a function named maxProjects to receive the information of n projects P (List[List[int]]) and return the maximum number of projects could be completed (int). Please consider the time complexity when you design your algorithm. A naïve approach will result in loss of marks.

You’re planning a road trip across a country represented by an m × n grid. You begin at your home located at the top-left corner (0, 0) and aim to reach your destination at the bottom-right corner (m-1, n-1). You can travel up, down, left or right to an adjacent city. Assume you’re starting with an initial budget of k dollars, and travel through a city where grid[i][j] = 1 will cost 1 dollar for toll roads. Design an efficient algorithm that check if you can reach your destination without going into debt (budget >=0).

Explanation: the bottom right cell can be reached by travelling along the green cells.

You should have a function named findPath to receive the receive the grid (List[List[int]]) and the budget (int) and return the whether the path exists (boolean). Please consider the time complexity when you design your algorithm. A naïve approach will result in loss of marks.

Answer the following questions in your report. (Clarity and brevity are valued over length).

T5-1: For Task 1, once the data is collected, discuss your observations. Provide explanations for the observed performance, focusing on the factors influencing the performance of algorithms under the different conditions. Finally, suggest possible improvements or optimizations to the sorting algorithms for specific scenarios, if applicable.

T5-2: For Task 2, what is the time and space complexity of your algorithm? Now assume that the BST can store duplicate keys as its right child. Will your algorithm still work in this case? If so, justify your answer; otherwise, explain how you would modify the algorithm to handle this scenario.

T5-3: For Task 3, explain the design, prove the correctness, and analyse the time and space complexity of your algorithm.

T5-4: For Task 4, describe an algorithm that find the shortest path (measured by the minimum number of cities visited) to the destination while satisfying the given constraint. Analyse the time and space complexity of the algorithm.

Submission

Electronic submission on Learning Mall is mandatory. You need to submit a zip file (named DTS203TC-CW-YOUR_NAME.zip) containing the following documents.

Generic Marking Criteria