CS代考程序代写 data structure python algorithm Introduction to Data Structures and Algorithms (IDSA, CCIT4016)

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 ===
”) myL = AList()
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(“
— 2. Finished AppendL(): A,C > ABC,D,B —“)
myL.displayL()
print(f” removeLastL(), elt is {myL.removeLastL()}”)
print(“
— 3. Finished removeLastL —“)
myL.displayL()
print(f”
— 4. isEmptyL(), value: { print(f”
— 5. searchL(‘ABC’), pos value: { print(f”
— 6. searchL(‘XYZ’), pos value: {
print(“
=== Program ends ===
”)
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>:
removeLastL(), elt is B
— 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

Leave a Reply

Your email address will not be published. Required fields are marked *