Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
DTS203TC Design and Analysis of Algorithms
School of AI and Advanced Computing
Coursework
Sunday, March 24th 23:59 (UTC+8 Beijing), 2024
DTS203TC Design and Analysis of Algorithms
Coursework
Deadline: Sunday, March 24th 23:59 (UTC+8 Beijing), 2024
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.
B. Identify the design principles used in a given algorithm, and apply design principles to produce efficient algorithmic solutions to a given problem.
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:
• Please read the coursework instructions and requirements carefully. Not following these instructions and requirements may result in loss of marks.
• The assignment must be submitted via Learning Mall to the correct drop box. Only electronic submission is accepted and no hard copy submission.
• All students must download their file and check that it is viewable after submission. Documents may become corrupted during the uploading process (e.g. due to slow internet connections). However, students themselves are responsible for submitting a functional and correct file for assessments.
• Academic Integrity Policy is strictly followed.
• The use of Generative AI for content generation is not permitted on this assessed coursework. Submissions will be checked through Turnitin.
Overview
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)
You haven coins and a balance. Among the coins, there is one fake coin which has different weight than the other coins. All the coins, except the fake coin, have exactly the same weight. Utilizing the balance, you can compare the weight of any number of coins on each pan. The balance will indicate whether the set of coins on one pan weighs the same as the set on the other pan. Assume the number of coins is a power of 3 (n = 3k). Implement an efficient algorithm to find the fake coin.
Input: coins = [10, 10, 10, 9, 10, 10, 10, 10, 10]
Output: 4
Explanation: In the given example, there are 9 coins, with the genuine coins weighing 10 units each and the fake coin weighing 9 units. The fourth (output) coin is identified as the fake coin.
You should have a function named findFakeCoin to receive a list of integers and return the index of fake coin (int). Please consider the time complexity when you design your algorithm. A naïve approach will result in loss of marks.
Task 2 (15 marks)
Consider a d-ary heap as a generalization of the binary heap, where each node has d children instead of 2. Implement a d-ary max heap and performs heap sort on a given array.
Example:
Input: nums = [7, 6, 5, 9, 8], d = 3
Output: [5, 6, 7, 8, 9]
You should create a function named dHeapSort that takes a list of integers to be sorted and an integer d indicates d-ary as parameters. The function should return a list containing the sorted integers based on the d-ary heap sort algorithm.
Task 3 (15 marks)
You’re driving an electric car from Shanghai to Beijing, where there are charging stations along the way at distances x1, x2, …, xn from Shanghai. Due to varying wait times c and charge speeds g, charging kkilometers worth of electric at station xi takes ci +kgi minutes. Your car has a capacity sufficient to travel 400 kilometers on a single charge. Assume car battery begin with 0 at the first station x1 in Shanghai and xn is your destination in Beijing. Design an efficient algorithm that finds where you should stop to spend the minimum amount of time at charging stations during your trip.
Example:
Input: x = [0, 100, 300, 600, 800, 1000], c = [0, 10, 0, 20, 10, 0], g = [0.05, 0.2, 0.1, 0.2, 0.1, 0]
Output: [20,0,30,40,30,0]
Explanation: In the provided example, there are a total of 6 stations. The objective is to drive from the first station to the final one, optimizing the time spent at each station. The output details the time spent at each station, aiming to minimize the overall time during the trip. For instance, the time spent at the first station is calculated as 0 + 400 * 0.05 = 20 minutes.
You should have a function named timeSpent to receive the information of distance x (List[int]), wait time c (List[int]), charge speed g (List[int]) and return the time spend at each station t (List[int]). Please consider the time complexity when you design your algorithm. A naïve approach will result in loss of marks.
Task 4 (15 marks)
Consider anundirected graph G = (V, E) with distinct weights assigned to each edge. Your task is to find the minimum spanning tree (MST), denoted asT, on G. Anticipating the potential removal of one edge in the future, implement an efficient algorithm to compute the MST T along with a backup edge, denoted as r(e), for each edge e in T. This ensures that if any edge e is removed, adding its corresponding backup edger(e) to the tree will quickly create a new minimum spanning tree in the modified graph.
Example:
Input: graph = {'A': {'B': 4, 'C': 8},
'B': {'A': 4, 'C': 2, 'D': 3, 'E': 5},
'C': {'A': 8, 'B': 2, 'D': 1, 'E': 6},
'D': {'B': 3, 'C': 1, 'E': 7},
'E': {'B': 5, 'C': 6, 'D': 7}}
Output: {('A', 'B'): ('A', 'C'), ('B', 'C'): ('B', 'D'), ('C', 'D'): ('B', 'D'), ('B', 'E'): ('C', 'E')}
Explanation: The input graph (as shown in figure) can be represented as a dictionary where the keys are vertices, and the values are dictionaries representing the edges going out of that vertex and the weights of those edges. The output can also be represented as a dictionary where the keys are the edges of the minimum spanning tree T, and the values are the corresponding backup edge of each edge in T. For example, if edge ('A', 'B') is removed from the graph G, adding backup edge ('A', 'C') will form a new minimum spanning tree.
You should have a function named modifiedMST to receive the graph represented as a dictionary and return the minimum spanning tree T with backup edges represented as a dictionary. Please consider the time complexity when you design your algorithm. A naïve approach will result in loss of marks.
Task 5 (40 marks)
Answer the following questions in your report. Maximum 800 words for Task 5. (Clarity and brevity are valued over length).
T5-1: For Task 1, give a recurrence of the running time of your algorithm and solve the recurrence with two different methods.
T5-2: For Task 2, what is the running time of d-ary heap’s insert and heapify operations? Will d- ary heap sort faster than binary heap sort? Justify your answer.
T5-3: For Task 3, explain the design, show the correctness, and analyse the time and space complexity of your algorithm.
T5-4: Given the same graph G from Task 4, is it possible to have more than one minimum spanning tree T? Justify your answer.
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.
1. Cover letter with your student ID.
2. Your source code for Tasks 1-4: Solutions.ipynb
3. A pdf file contains all the source code (should be the same as the submitted ipynb file) and your report (task 5). You can also write the report in jupyter notebook and export as a pdf file.
Generic Marking Criteria
|
Grade |
Point Scale |
|
Criteria to be satisfied |
|
A |
81+ |
First |
|
|
|
|
|
|
|
B |
70 - 80 |
First |
|
|
C |
60 - 69 |
Upper Second |
taught.
|
