代做SEHH2239、Python程序语言代写

日期：2024-04-03 09:40

SEHH2239 Data Structures

SEHH2239 – Assignment 2 Page 1 of 7

Assignment 2 (Individual Assignment)

Due Date

19 April 2024 17:00 (Friday)

Late submission is liable to a penalty of 10% of the available marks for each day late; Saturdays, Sundays

and holidays are counted. Submission after 24 April 2024 17:00 will not be accepted.

Declaration of Original Work

Plagiarism is a serious misconduct. No part of students’ assignment should be taken from other people’s

work without giving them credit. All references must be clearly cited. Any plagiarism found in students’

completed assignments can lead to disciplinary actions such as mark deduction, disqualification or even

expulsion by the College.

In principle, CPCE considers GenAI tools as positive and creative forces in education and encourages their

use in learning, teaching, and assessment. However, extensive copy-pasting from AI-generated content

without citation is considered plagiarism.

By submitting this assignment to the subject lecturer through Blackboard, you hereby declare that the work

in this assignment is completely your own work. No part of this assignment is taken from other people’s

work without giving them credit. All references have been clearly cited.

You understand that an infringement of this declaration leaves you subject to disciplinary actions such as

mark deduction, disqualification or even expulsion by the College.

Plagiarism will be penalized severely. Marks will be deducted for assignments that are plagiarized in whole

or in part, regardless of the sources.

SEHH2239 Data Structures

SEHH2239 – Assignment 2 Page 2 of 7

Instruction

You are required to submit a Python Notebook using the template provided (Assign_2_Template.ipynb)

showing all the answers and programs. Rename the file as instructed below.

Your Python Notebook file should contain your name, your student ID no, and class (201/202/203/204).

All submitted assessments will be evaluated with Python version 3.10 or above (the current python version

used in Google Colab). Your submitted assessments must run without errors on Google Colab. Code that

cannot execute will result in zero or low marks for the respective questions. When you finish the

assignment, you are advised to use the “Restart session and run all” functionality of Colab to check

whether all code can execute successfully.

Unless otherwise instructed, you MUST NOT import any modules in your submitted assessments.

You MUST NOT change the procedure name (include cases) and parameters required.

Items to be Submitted

1. Python Notebook: Rename the notebook to the format <name>_<student ID>_<class>.ipynb, e.g.,

ChanTaiMan_22001234A_201.ipynb.

To download the Python Notebook (.ipynb)

In Google Colab, File → Download → Download .ipynb

To submit the Notebook via Blackboard

Upon uploading the notebook to the submission page in Blackboard, make sure that you click the “Submit”

button, not “Save and Close”.

To validate the submitted file

After you have submitted the notebook to Blackboard, download the submitted notebook from Blackboard

and upload it back onto Colab to check that your submitted file can still run in Colab. To do so, in

Blackboard, go to the assignment submission page, click on “View Submission”, download the ipynb file,

and upload it to Colab for checking. (Some students have done the assignment properly, but submitted some

junk code onto Blackboard, due to mistakes in downloading from Colab and uploading to Blackboard.)

Attention:

While submitting the softcopies via Blackboard, a timestamp will be placed on the softcopies of your

assignment. There will be a sharp cut-off time at Blackboard, so late assignments will be recorded at

Blackboard. Softcopies submitted via email or other means will NOT be accepted unless the Blackboard is

not available. As many students will submit their assignments to Blackboard at around the deadline time, it

normally takes longer for uploading your assignment, so it is strongly suggested that you start submitting

earlier, say at least 45 minutes before the deadline. Marks will be deducted for late submission.

SEHH2239 Data Structures

SEHH2239 – Assignment 2 Page 3 of 7

Question 1

A linear queue is a linear data structures having two ends i.e. the front end and the rear end. The

operations in a queue are carried out in First In, First Out (FIFO) order. This means, we can only

add items to the rear end of the queue and delete items from its front end. Implementing a linear

queue in array brings the drawback of memory wastage. When the rear pointer reaches the end of

a queue, there might be a possibility that after a certain number of dequeue() operations, it will

create an empty space at the start of a queue.

To overcome this limitation, experts introduced the concept of circular queue. A circular queue,

or a Ring Buffer, is an extended version of a linear queue as it follows the FIFO principle with the

exception that it connects the last node of a queue to its first by forming a circular link.

Array implementation of linear queue or circular queue has another limitation that the size of the

queue is bounded by the underlying array. When a queue is full, no additional element can be

added.

In question 1, you are going to implement a circular queue in Python list that will automatically

double its capacity when it is full.

(a) Complete the class AutoGrowthCircularQueue and implement the methods:

isEmpty(), getFrontElement(), getRearElement(), enqueue(), and

dequeue() according to the comment described in the Assignment Template.

(b) Run the testing code provided in the Assignment Template. It should produce the following

outputs (excluding the line numbers). Do not alter the testing code.

SEHH2239 Data Structures

SEHH2239 – Assignment 2 Page 4 of 7

1. Is Empty: True

2. Is Empty: False

3. Get: 2

4. Is Empty: True

5. Front element: 3

6. Rear element: 1

7. Queue size: 5/8

8. 3

9. String node 4

10. 1

11. 5

12. 6

Question 2

In Question 2, you will build a data structure for storing information of a student and learn how to

validate an input data against a predefined pattern.

(a) Write a class Student with the following specification:

1) The constructor takes two inputs: name (type str) and studentid (type str).

Validate their types. Raise an error and stop the program if the input type is invalid.

2) Validate the input studentid using the Boolean value “re.fullmatch('[0-

9]{8}A', studentid) is None” (a True value designates a mismatch). It

checks whether the input has 8 digits followed by the character 'A'. You need to import

the re library. Raise an error and stop the program if the input is invalid.

3) Initialize an instance attribute name to the input name.

4) Initialize an instance attribute studentid to the input studentid.

5) Overload the __str__() method to facilitate the printing with print(). See lines 2

& 3 of the outputs below for the required format.

6) Overload the __eq__() method to facilitate the comparison of Student objects.

Students with the same studentid attributes are deemed equal.

(b) Run the testing code provided in the Assignment Template. It should produce the following

outputs (excluding the line numbers). Do not alter the testing code.

1. Invalid student id 2224564

2. Name: Calvin Weign, ID: 22123456A

3. Name: Cola Coke, ID: 22003276A

4. False

5. True

6. Invalid data type!

SEHH2239 Data Structures

SEHH2239 – Assignment 2 Page 5 of 7

Question 3

In question 3, you will construct a Class Course to hold information about a course, registered

students, and students in waiting queue in case if the course was full. You will need to use the class

constructed in question 1 and 2.

(a) Complete the class constructor with the instructions below:

1) The constructor takes three inputs: code (type str), title (type str), and size

(type int). Validate their types. Raise an error and stop the program if the input type is

invalid.

2) Validate the input code using the Boolean value “re.fullmatch('[A-Z]{4}[0-

9]{4}', code) is None” (a True value designates a mismatch). The code should

starts with 4 upper case letters, then followed by 4 digits. Raise an error and stop the

program if the input type is invalid.

3) Initialize an instance attribute code to the input code.

4) Initialize an instance attribute title to the input title.

5) Initialize an instance attribute maxSize to the input size.

6) Initialize an instance attribute size to 0, i.e. the course contains no students at the

beginning.

7) Initialize an instance attribute BST to None. Binary search tree (BST) is used to stores

the registered students.

8) Initialize an instance attribute queue to an AutoGrowthCircularQueue. This

attribute is used to store students waiting for registration when course is full.

(b) Override __eq__() method to facilitate the comparison of Course objects. Courses with

the same code attributes are deemed equal.

(c) Write a method addStudent() with the specifications below:

1) Take one input student (type Student). Validate its type. Raise an error and stop

the program if the input type is invalid.

2) Print a message if the student was already registered, i.e. the student is in the BST

attribute and end the method. See line 11 below for the required format of the message.

3) If the course is not full, insert the student into the BST as the data field of a

BSTNode (the class BSTNode is provided in the Assignment Template; do not change

the code of the BSTNode class and do not use other implementations of BSTs). The key

field of the BSTNode is the studentid of the student. Increment the size attribute

and print a message for successful registration. See line 8 for the required format of the

message.

4) If the course is full, put the student into the queue attribute and print a message for

putting the student into waiting queue. See line 12 for the required format of the

message.

SEHH2239 Data Structures

SEHH2239 – Assignment 2 Page 6 of 7

(d) Write a method removeStudent() with the specifications below:

1) Take one input student (type Student). Validate its type. Raise an error and stop

the program if the input type is invalid.

2) Check if the student was registered or not. Print a message if the student was not

registered. See line 9 for the required format of the message.

3) If the student was registered, remove the student from the BST by calling

self.BST = self.BST.remove(self.BST, student.studentid).

Decrease the size attribute. Print a message according to line 13 for the required format.

4) If the course is not full and if there is other student waiting in the queue, remove a

student from the queue and add him to the course by calling the addStudent()

method.

(e) Run the testing code provided in the Assignment Template. It should produce the following

outputs (excluding the line numbers). Do not alter the testing code.

1. Invalid input type

2. Invalid course code abc1234

3. False

4. True

5.

6. Invalid input type

7. Invalid input type

8. Register Calvin Weign 22123456A successful.

9. Cola Coke 22003276A was not registered.

10. Register Cola Coke 22003276A successful.

11. Calvin Weign 22123456A has already registered.

12. Course full. Put Rain Man 22435638A in waiting queue.

13. Remove Calvin Weign 22123456A successful.

14. Register Rain Man 22435638A successful.

Question 4

In question 4, you will build a class CourseRegistry that store all the courses in a school. The

class will use hash table (backed by Python list) with separate chaining. Python built-in function

hash() is used to calculate hash code of a course using the course code as key. The calculated

hash code will then map to corresponding index position of the hash table using a modulo operator.

The constructor is provided in the Assignment Template.

(a) Method insert() is used to add a course into course registry. Complete the method with

the specifications below:

1) Take one input course (type Course). Validate its type. Raise an error and stop the

program if the input type is invalid.

2) Create a LLNode object with course.code as key and course as value (the class

LLNode is provided in the Assignment Template; do not change the code of the LLNode

class and do not use other implementations of linked lists).

SEHH2239 Data Structures

SEHH2239 – Assignment 2 Page 7 of 7

3) Determine the hash table index by calling hash(course.code) %

self.capacity and insert the LLNode object to the front of the linked list.

4) Increment the size attribute by 1.

(b) Method search() is used to find and return a course from the course registry. Complete the

method with the specifications below:

1) Take one input code (type str). Validate its type. Raise an error and stop the program

if the input type is invalid.

2) Determine the hash table index by calling hash(code) % self.capacity.

3) Search along the linked list to see if any matching LLNode with key equals to the

inputted code. If found, return the value attribute of the LLNode. Otherwise, return

None.

(c) Run the testing code provided in the Assignment Template. It should produce the following

outputs (excluding the line numbers). Do not alter the testing code.

1. None

2. Data Structures

3.

4. Register Chan TM 22061762A successful.

5. Register CHOW MP 22167034A successful.

6. Register LAM CS 22118617A successful.

7. Register LEUNG WA 22018089A successful.

8. Register LI CC 22134887A successful.

9. Course full. Put LIU MK 22052452A in waiting queue.

10. Course full. Put NG KY 22018110A in waiting queue.

11. Course full. Put SHEK CL 22161668A in waiting queue.

12. Course full. Put TSE David 22158990A in waiting queue.

13. Course full. Put WONG KM 22153656A in waiting queue.

14.

15. Remove CHOW MP 22167034A successful.

16. Register LIU MK 22052452A successful.

17.

18. Course code: SEHH2239

19. Course title: Data Structures

20. Course size: 5/5

21. Registered students:

22. 22018089A Name: LEUNG WA, ID: 22018089A

23. 22052452A Name: LIU MK, ID: 22052452A

24. 22061762A Name: Chan TM, ID: 22061762A

25. 22118617A Name: LAM CS, ID: 22118617A

26. 22134887A Name: LI CC, ID: 22134887A

27. Students in queue:

28. Queue size: 4/8

29. Name: NG KY, ID: 22018110A

30. Name: SHEK CL, ID: 22161668A

31. Name: TSE David, ID: 22158990A

32. Name: WONG KM, ID: 22153656A

- END of Assignment 2 -