Introduction to Data Structures and Algorithms (IDSA, CCIT4016)
HKU SPACE Community College, 2020-2021
Assignment 1
(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: Student MUST 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.
* Student may reference and reuse the given codes in our course materials, unless specified.
* Do not use methods of Python’s list (such as list.append() etc.), inheritance in OOP, or other non-taught approaches in our course, unless specified.
* Follow given instructions and guidelines, including those given by individual class teacher.
1.
Part 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 Make sure you have successfully completed, “Finished” and submitted your work.
* Attempts must be submitted before time expires, or they are NOT counted.
o Questions related to program codes are based on Python programming language, unless specified. o 10 MC questions and 10 Matching questions. Each question carries the same mark.
2.
Part B, A1B (10 marks)
Write a Python program, with the given Python files.
o Enhancing Array-List: Enhance and implement a List ADT (with Array-based approach), by modifying our given Python file AoneB.py (based on the one in our lecture notes, AList.py)
o Extra Operations (methods of the class) to be implemented by Students: At least one line of simple comment for each extra operation required
Operation (AList)
Description
isEmptyL():bool
Check if the list is empty or not
appendL(elt):
Insert a new element elt into the end of the current list.
removeLastL():elt
Remove & return the last element elt of the list o Return None in case of empty list
searchL(elt):int
Search & return the position of the first occurrence of an input searching element elt. * Position starts from 1.
o Return -1 if not exist.
1/4
Given Materials:
o Python file to be modified and completed by student. Also modify top comments for your (DO NOT modify this given portions, including given methods if any)
o Python file AoneBT.py for basic running and testing.
DO NOT modify this given test file, except the STUDENT INFO part.
File AoneB.py, to be modified and completed by student.
AoneB.py,
STUDENT INFO.
# AoneB.py, for IDSA Assign 1
class AList: # defining a class of Dynamic-Array-List
# …
####################### STUDNET’s WORK ######################
# simple comment HERE
def isEmptyL(self):
pass # TO BE DONE
# AND MORE
#######################################
File AoneBT.py for basic running and testing
# AoneCT.py, for basic running and testing.
# * DO NOT modify this given test file, except the STUDENT INFO part. # Main Testing Program
from AoneB import AList
def main():
print(“=== A1B, Enhanced ArrayList, by
print(f”— 1. New AL created, isEmptyL() result: {myL.isEmptyL()}”)
myL.insertL(‘A’, 1); myL.insertL(‘C’, 2);
myL.appendL(‘ABC’); myL.appendL(‘D’); myL.appendL(‘B’);
print(“\n— 2. Finished AppendL(): A,C > ABC,D,B —“)
myL.displayL()
print(f”
print(“\n— 3. Finished removeLastL —“)
myL.displayL()
print(f”\n— 4. isEmptyL(), value: { print(f”\n— 5. searchL(‘ABC’), pos value: { print(f”\n— 6. searchL(‘XYZ’), pos value: {
print(“\n=== Program ends ===\n”)
main()
}”)
}”)
}”)
myL.isEmptyL()
Sample console display output of executing the main testing program AoneBT.py
myL.searchL(‘ABC’)
myL.searchL(‘XYZ’)
True
> A > C > ABC > D > B
> A > C > ABC > D
False
-1
=== A1B, Enhanced ArrayList, by === — 1. New AL created, isEmptyL() result:
— 2. Finished appendL(): A,C > ABC,D,B —
>>> AList Display, with size/last<5>, capacity<10>:
— 3. Finished removeLastL() —
>>> AList Display, with size/last<4>, capacity<10>:
— 4. isEmptyL(), value:
— 5. searchL(‘ABC’), pos value: 3 — 6. searchL(‘XYZ’), pos value: === Program ends ===
2/4
3.
Part C, A1C (10 marks)
Write a Python program, with the given Python files.
o Doubly-Linked List (DLL): Implement a Doubly-Linked List
o Students have learnt conventional (Singly-) Linked-List in our course. In this part,
students should implement a simple-version of Doubly-Linked List:
Each node in this 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.
Some operations could be done for efficiently with this Doubly-Linked List, which
require tracing backward (the previous node of the current node).
o Students should reuse and modify the given codes of (Singly-) Linked-List in our course.
File AoneC.py, to be modified and completed by student.
o Include a given class of nodes with a value and two links (to previous and next nodes):
11 33 55 77
# AoneC.py, for IDSA Assign 1
class DLNode: # modelling a node with doubly-linked
def __init__(self, inValue=None, inPrev=None, inNext=None): # constructor self.value = inValue # the node data value, default None
self.prevN = inPrev # the previous node, default None
self.nextN = inNext # the next node, default None
class DLList: # defining a class of Doubly-Linked List def __init__(self): # constructor
self.headN = None # the head Node self.tailN = None # the tail Node
# MORE TO BE MODIFIED AND FINISHED
o Extra Operations (methods of the class) to be implemented by Students: At least one line of simple comment for each extra operation required
Operation (DLList)
__init__():
insertAsTail(elt):
displayDL():
Description
Create and initiate a new DLL (constructor, GIVEN)
Insert element elt as a new tail (GIVEN)
Traverse & display node values, in forward order (GIVEN)
insertBefore(refElt, elt):
Insert element elt, before a reference refElt o Do not insert if refElt not existing
insertAfter(refElt, elt):
Insert element elt, after a reference refElt o Do not insert if refElt not existing
displayDLBackw():
Traverse & display node values, in backward order
3/4
Given Materials:
o Python file , to be modified and completed by student. Also modify top comments for your (DO NOT modify this given portions, including given methods if any)
o Python file AoneCT.py for basic running and testing.
DO NOT modify this given test file, except the STUDENT INFO part.
Sample console display output of executing the main testing program AoneCT.py
AoneC.py
STUDENT INFO.
… AN EMPTY LIST
>11 >22 >33 >55 >77 >99
>11 >22 >33 >55 >66 >77
>11 >22 >33 >44 >55 >66
>11 >22 >33 >44 >55 >66 <99 <88 <77 <66 <55 <44
>99
>77 >99
>77 >88 >99 <33 <22 <11
4.
Submission and Assessment
o Mark sure students follow instructions, including to follow the required naming of files.
o Submit ALL files to SOUL ( , AoneBT.py, AoneC.py, AoneCT.py).
o Do NOT compress/zip or the files. Submission work not following requirements would
be penalized.
o Assessment is mainly based on whether the program functions as expected and it is coded
according to the requirements. It also includes: 1) proper and completed submission, 2) works finished based on the given instructions and requirements.
* Remarks:
o More testing may be performed during assessment based on the requirements, apart from the given testing files.
o Certain possible deviations could be applied to individual cases.
AoneB.py
rename
=== A1C, DLList program, by
— 1. New DLL created —
>>> DOUBLY-Linked-List Display:
— 2. Insert some items — >>> DOUBLY-Linked-List Display:
… head <11>, tail <99>:
— 3. insertAfter(55,66) — >>> DOUBLY-Linked-List Display:
… head <11>, tail <99>:
— 4. insertBefore(55,44) — >>> DOUBLY-Linked-List Display:
… head <11>, tail <99>:
— 5. insertAfter(77,88) — >>> DOUBLY-Linked-List Display:
… head <11>, tail <99>:
>>> DOUBLY-Linked-List Display, FROM … tail <99>, head <11>
=== Program ends ===
===
>
>
>
>
>
Backwards: >
~ END ~
4/4