DTS203TC Design and Analysis of Algorithms

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

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.

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.