SEHH2239 Data Structures
SEHH2239 – Assignment 2
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.
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 __.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.
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.
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!
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.
(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).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 -