Introduction to Data Structures and Algorithms (IDSA, CCIT4016)
HKU SPACE Community College, 2024-2025, Semester 2
Assignment 1 (A1)
(15%)
(Total Marks: 30)
o Finish this work, based on concepts and techniques learnt in our course.
o Students should finish reviewing the related course notes and materials, before doing this assignment.
o Individual work: FINISH THIS WORK ALONE. Student cannot work with others.
* Plagiarism / Collusion / Shared work with others are not allowed. Zero mark will be given, with
possible disciplinary action.
o Students are responsible for ensuring that their files are submitted successfully and properly to SOUL. It
is recommended to download submitted files for self-check before the deadline. Improper file
submissions, such as damaged or wrongly sent files, will not be processed or notified by any means.
o Late Submission is Not Accepted. Zero Mark will be Given. Students should well-plan their time and
schedule. Finish and submit the assignment well before the deadline.
o Questions related to program codes are based on Python programming language, unless specified.
o Follow given instructions and guidelines.
Section A, A1A (10 marks)
Multiple Choice (MC) and Matching Questions, Online (SOUL-Quiz Feature)
o Identify and select the option of choice that "best" completes the statement, matches the item, or
answers the question.
o Number of Attempts Allowed: 2
o Grading method: Highest Grade
o Make sure you have successfully completed, "Finished" and submitted before deadline.
* Attempts must be submitted before time expires, or they are NOT counted. (Zero mark given)
o 5 MC questions and 5 Matching questions. Each question carries the same mark.
Section B, A1B (20 marks): Programming Tasks
* IMPORTANT:
o Source code *.py file must start with comments, including the information of individual student
(student name, student id) as example below, unless specified. E.g. below
o Modify the given Main testing file M*.py file (if any) to display the information of individual student
(student name, student id) as example below, unless specified. E.g. below
=== A1B1, Rectangle Program, by <CHAN Siu Ming> <20004016> ===
...
...
# A1B1.py, for IDSA A1
# FINISHED by: <CHAN Siu Ming>, <20004016>
class Rectangle: # define the class of Rectangle
2 / 5
General requirements (unless further specified):
o Students should handle special cases, for examples: empty list, one-element list, etc.
o Proper brief comments are required, at least at the top of each source code file.
o Proper indentations are required in writing program codes.
o All related files (including *.py) should be working in the same folder.
o Python list is mainly used to hold data elements as an array in our course and this assessment.
DO NOT use methods of Python’s list (such as list.append() or list.insert() etc.),
inheritance in OOP, or other non-taught approaches in our course, unless specified.
Given Materials:
o This assignment document.
o Python files A1B1.py and A1B2.py: to be modified and completed by student.
o Also modify top comments for your STUDENT INFO.
o DO NOT modify the given portions unless specified, including the given methods if any.
o Python files MA1B1.py and MA1B2.py: the main files for basic running and testing.
o DO NOT modify these given main test files, except the STUDENT INFO part.
A1B1 (10 marks)
Develop a Fixed-Size Array-List, with the given Python file A1B1.py.
o In this part, students are required to implement a Fixed-Size version of Array-List:
o No need to enlarge the list if it is full.
o GIVEN an uncompleted Fixed-Size Array-List in A1B1.py (based on the one in our lecture notes,
AList.py), with implemented methods below:
GIVEN Operations (Class AList) Description
__init__(): Initiate/create a new Array-List (constructor / initializer)
* This code sample is in Python-style
sizeL():int Get and return the size of the List (total number of elements)
getL(pos):elt Get and return the element in position pos without removal
- If failed, return null/None; e.g. pos is out of range
insertL(elt,pos): Insert a new element elt into position pos
- If list is full, console display "<FULL>- Failed INSERT"
Do nothing if this task cannot be done, including if pos is out of range
or other exceptional cases
removeL(pos):elt Remove and return the element elt in position pos
- If failed, return null/None; e.g. pos is out of range
displayL(): Display all elements of the list in order
* Remark: pos (position of element in list) starts from 1 in our course (not 0 as index in Python list)
3 / 5
o Complete the Fixed-Size Array-List with the following Extra Operations (methods of the class):
o At least one line of simple comment for each extra operation required
Operations (Class AList) Description
appendL(elt): Insert/Append a new element elt into the end of the current list
o If list is full, console display "<FULL>- Failed APPEND"
o Do nothing if this task cannot be done, including if pos is out of
range or other exceptional cases
searchLastL(elt):int Search & return the position of the last occurrence of an input
searching element elt. (* Position starts from 1)
o Return -1 if this task cannot be done, including the searching
element does not exist in the list.
isEmptyL():bool Check if the list is empty or not
Return boolean True if the list is empty, otherwise False
isFullL():bool Check if the list is already full or not, for our fixed-size list
Return True if the list is full, otherwise return False
clearL(): Clear the whole list (remove/delete all elements)
Sample console display output of executing the main testing program MA1B1.py
=== A1B1, Fixed-Sized ArrayList, by <Student NAME> <Student ID> ===
--- 0. new AL <CHECK> isFullL()?:False, isEmptyL()?:True
>>> AList Display(Head/Left), size/last<0>, capacity<4>:
--- 1. insertL <KABC>-D?
<FULL>- Failed INSERT
>>> AList Display(Head/Left), size/last<4>, capacity<4>:
> K > A > B > C
--- 2. appendL: <KAC,K>-P?
<FULL>- Failed APPEND
>>> AList Display(Head/Left), size/last<4>, capacity<4>:
> K > A > C > K
------ <CHECK> searchLastL('D'), pos:-1
------ <CHECK> searchLastL('A'), pos:2
--- 3. getL(myL.searchLastL(myL.removeL(1))), elt:K
>>> AList Display(Head/Left), size/last<3>, capacity<4>:
> A > C > K
------ <CHECK> searchLastL('C'), pos:2
------ <CHECK> searchLastL('P'), pos:-1
=== Program ends ===
4 / 5
A1B2 (10 marks)
Develop a Doubly-Linked-List, with the given Python file A1B2.py.
o Each node in Doubly-Linked-List has two links: one for the next node as in singly-linked list, the other
for the previous node. The head node has no previous link and the tail node has no next link. This is
implemented as a Python class DLNode and given in our Python file.
o Some operations could be done efficiently with this Doubly-Linked-List, which require tracing
backward (the previous node of the current node).
o Given an uncompleted Doubly-Linked-List in A1B2.py (based on the one in our lecture notes,
LList.py), with implemented methods below:
Given Operations (Class DLList) Description
__init__(): Create and initiate a new Doubly-Linked-List (constructor)
appendDL(elt): Append/Insert element elt as a new tail
displayDL(): Traverse & display node values, starting from head in forward order
displayBwDL(): Traverse & display node values, starting from tail in backward order
o Complete the Doubly-Linked-List with the following Extra Operations (methods of the class):
o At least one line of simple comment for each extra operation required
Operations (Class DLList) Description
getNextFwDL(refElt):elt Get & return (without remove) the next element of a reference
element refElt, starting from head in forward order
o Return None if no element can be returned
getPrevBwDL(refElt):elt Get & return (without remove) previous element of reference
element refElt, starting from tail in backward order
o Return None if no element can be returned
removeNextFwDL(refElt):elt Remove & return the next element elt of a reference element
refElt, starting from head in forward order
o Return None if no element can be removed and returned
- A B C - headN tailN
5 / 5
Sample console display output of executing the main testing program MA1B2.py
=== === A1B2, DLList program, by <Student NAME> <Student ID>===
--- 1. List with Insert items <8,3,1,2,7,4,9> ---
>>> DOUBLY-Linked-List Display: >
... head <8>, tail <9>:
> 8 > 3 > 1 > 2 > 7 > 4 > 9
<<< DOUBLY-Linked-List Display, Backwards: <<
FROM ... tail <9>, head <8>
< 9 < 4 < 7 < 2 < 1 < 3 < 8
------ <CHECK> getPrevBwDL('2'), elt:1
------ <CHECK> getNextFwDL('9'), elt:None
------ <CHECK> getNextFwDL('7'), elt:4
--- 2. removeNextFwDL('4'), elt:9
>>> DOUBLY-Linked-List Display: >
... head <8>, tail <4>:
> 8 > 3 > 1 > 2 > 7 > 4
<<< DOUBLY-Linked-List Display, Backwards: <<
FROM ... tail <4>, head <8>
< 4 < 7 < 2 < 1 < 3 < 8
------ <CHECK> getPrevBwDL('8'), elt:None
------ <CHECK> getNextFwDL('1'), elt:2
=== Program ends ===
SUBMISSION:
o Check and follow requirements and instructions, including to follow the required naming of files.
o Run, Debug, Test and Evaluate your program based on the requirements.
o Submit ALL related .py files to SOUL:
o A1B1.py, MA1B1.py
o A1B2.py, MA1B2.py
o Do NOT compress/zip or rename the files. Submission work not following requirements may be
penalized or not be assessed.
~ END ~
請加QQ：99515681 郵箱：
[email protected] WX：codinghelp
