代写DTS203TC、代做Python程序设计

日期：2025-05-12 09:16

XJTLU Entrepreneur College (Taicang) Cover Sheet

Module code and Title DTS203TC Design and Analysis of Algorithms

School Title School of AI and Advanced Computing

Assignment Title Coursework

Submission Deadline Sunday, May 11th 23:59 (UTC+8 Beijing), 2025

Final Word Count

If you agree to let the university use your work anonymously for teaching

and learning purposes, please type “yes” here.

I certify that I have read and understood the University’s Policy for dealing with Plagiarism,

Collusion and the Fabrication of Data (available on Learning Mall Online). With reference to this

policy I certify that:

• 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.

Scoring – For Tutor Use

Student ID

Stage of

Marking

Marker

Code

Learning Outcomes Achieved （F/P/M/D）

(please modify as appropriate)

Final

Score

A B C

1

st Marker – red

pen

Moderation

– green pen

IM

Initials

The original mark has been accepted by the moderator

(please circle as appropriate):

Y / N

Data entry and score calculation have been checked by

another tutor (please circle):

Y

2

nd Marker if

needed – green

pen

For Academic Office Use Possible Academic Infringement (please tick as appropriate)

Date

Received

Days

late

Late

Penalty

☐ Category A

Total Academic Infringement Penalty

(A,B, C, D, E, Please modify where

necessary) _____________________

☐ Category B

☐ Category C

☐ Category D

☐ Category E

DTS203TC Design and Analysis of Algorithms

Coursework

Deadline: Sunday, May 11th 23:59 (UTC+8 Beijing), 2025

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.

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)

Implement 5 sorting algorithms: Insertion sort, selection sort, merge sort, quick sort and heap

sort. After implementing these algorithms, test their performance under various conditions and

record the running times in a table. The conditions to evaluate: 1) sorting random arrays of integers

of different sizes, such as 10, 100, 1000, 10000, etc. 2) the input array is already sorted in ascending

order, 3) the input array is reverse sorted in descending order, 4) the input array contains only a

few unique values, where the number of unique values 𝑘 is significantly smaller than the array size

𝑛.

Task 2 (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.

Example:

Input: bst = [6, 5, 8, None, None, 7, 9]

Output: [24, 30, 9, None, None, 17, 0]

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.

Task 3 (15 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.

Example:

Input: P = [[1,2], [3,4], [1,3], [5,7]]

Output: 3

Explanation: take 1st project and complete it on the 1st day, take 3rd project and complete it on the

2

nd day, take 4th project and complete it on the 7th day. You can at most complete 3 projects.

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.

Task 4 (15 marks)

You’re planning a road trip across a country represented by an 𝑚 × 𝑛 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).

Example:

Input: graph = [[0,0,0],

[1,1,0],

[0,0,0],

[0,1,1],

[0,0,0]], budget = 0

Output: true

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.

Task 5 (40 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.

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 ➢ Outstanding work that is at the upper limit of

performance.

➢ Work would be worthy of dissemination under

appropriate conditions.

➢ Mastery of advanced methods and techniques at a

level beyond that explicitly taught.

➢ Ability to synthesise and employ in an original way

ideas from across the subject.

➢ In group work, there is evidence of an outstanding

individual contribution.

➢ Excellent presentation.

➢ Outstanding command of critical analysis and

judgment.

B 70 - 80 First ➢ Excellent range and depth of attainment of intended

learning outcomes.

➢ Mastery of a wide range of methods and techniques.

➢ Evidence of study and originality clearly beyond the

bounds of what has been taught.

➢ In group work, there is evidence of an excellent

individual contribution.

➢ Excellent presentation.

➢ Able to display a command of critical thinking,

analysis and judgment.

C 60 - 69 Upper

Second

➢ Attained all the intended learning outcomes for a

module or assessment.

➢ Able to use well a range of methods and techniques

to come to conclusions.

➢ Evidence of study, comprehension, and synthesis

beyond the bounds of what has been explicitly

taught.

➢ Very good presentation of material.

➢ Able to employ critical analysis and judgement.

➢ Where group work is involved there is evidence of a

productive individual contribution

D 50- 59 Lower

Second

➢ Some limitations in attainment of learning

objectives but has managed to grasp most of them.

➢ Able to use most of the methods and techniques

taught.

➢ Evidence of study and comprehension of what has

been taught

➢ Adequate presentation of material.

➢ Some grasp of issues and concepts underlying the

techniques and material taught.

➢ Where group work is involved there is evidence of a

positive individual contribution.

E 40 - 49 Third ➢ Limited attainment of intended learning outcomes.

➢ Able to use a proportion of the basic methods and

techniques taught.

➢ Evidence of study and comprehension of what has

been taught, but grasp insecure.

➢ Poorly presented.

➢ Some grasp of the issues and concepts underlying

the techniques and material taught, but weak and

incomplete.

F 0 - 39 Fail ➢ Attainment of only a minority of the learning

outcomes.

➢ Able to demonstrate a clear but limited use of some

of the basic methods and techniques taught.

➢ Weak and incomplete grasp of what has been

taught.

➢ Deficient understanding of the issues and concepts

underlying the techniques and material taught.

➢ Attainment of nearly all the intended learning

outcomes deficient.

➢ Lack of ability to use at all or the right methods and

techniques taught.

➢ Inadequately and incoherently presented.

➢ Wholly deficient grasp of what has been taught.

➢ Lack of understanding of the issues and concepts

underlying the techniques and material taught.

➢ Incoherence in presentation of information that

hinders understanding.

G 0 Fail ➢ No significant assessable material, absent, or

assessment missing a "must pass" component.

Marking Criteria

Tasks 100 Components Description Maximum

Credit Mark

Task 1 15

Implementation

9 marks

Sorting algorithms implementation, 1 mark

per algorithm. 5

Input array generation [0-4 marks] 4

Evaluation

5 marks

Correct running time [0/2 marks] 2

Result table for comparison [0-3 marks] 3

Code quality

1 mark Readability, Formatting, Comments 1

Task 2 15

Implementation

6 marks

Correct function definition [0/1 mark] 1

Correct algorithm design [0/2 marks] 2

Algorithm implementation [0-3 marks] 3

Evaluation

8 marks

Time complexity [0/3 marks] 3

5 test cases will be used to evaluate the

correctness of the function. 1 mark for each

test case.

5

Code quality

1 mark Readability, Formatting, Comments 1

Task 3 15

Implementation

6 marks

Correct function definition [0/1 mark] 1

Correct algorithm design [0/2 marks] 2

Algorithm implementation [0-3 marks] 3

Evaluation

8 marks

Time complexity [0/3 marks] 3

5 test cases will be used to evaluate the

correctness of the function. 1 mark for each

test case.

5

Code quality

1 mark Readability, Formatting, Comments 1

Task 4 15 Implementation

6 marks

Correct function definition [0/1 mark] 1

Correct algorithm design [0/2 marks] 2

Algorithm implementation [0-3 marks] 3

Evaluation

8 marks

Time complexity [0/3 marks] 3

5 test cases will be used to evaluate the

correctness of the function. 1 mark for each

test case.

5

Code quality

1 mark Readability, Formatting, Comments 1

Task 5 40

Task 5-1

9 marks

Observations [0-3 marks] 3

Explanations [0-3 marks] 3

Optimizations [0-3 marks] 3

Task 5-2

9 marks

Time and space complexity [0-2 marks] 2

‘Yes/No’ answer correct [0/2 marks] 2

Correctness of Algorithm (Justification or

New Algorithm Proposal) [0-5 marks] 5

Task 5-3

9 marks

Algorithm design [0/2 marks] 2

Correctness [0/3 marks] 3

Time and space complexity [0/2/4 marks] 4

Task 5-4

9 marks

Algorithm design [0-5marks] 5

Time and space complexity [0/2/4 marks] 4

Report quality

4 marks

Fluency and readability [0/2 mark]

Formatting and conciseness [0/2 mark] 4

Late Submission?  Yes

 No

Days

late

Final Marks