闪电代写 -代写CS作业_CS代写_Finance代写_Economic代写_Statistics代写_代码代做_IT代写_加急帮助

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 fifirst occurrence of an input searching element elt. * Position starts from 1. o Return -1 if not exist.

Given Materials:

o Python file AoneB.py, to be modified and completed by student. Also modify top comments for your STUDENT INFO. (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, 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 <Student NAME> <Student ID> ===\n")

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("\n--- 2. Finished AppendL(): A,C > ABC,D,B ---")

myL.displayL()

print(f"<CHECK> removeLastL(), elt is {myL.removeLastL()}")

print("\n--- 3. Finished removeLastL ---")

myL.displayL()

print(f"\n--- 4. isEmptyL(), value: {myL.isEmptyL()}")

print(f"\n--- 5. searchL('ABC'), pos value: {myL.searchL('ABC')}")

print(f"\n--- 6. searchL('XYZ'), pos value: {myL.searchL('XYZ')}")

print("\n=== Program ends ===\n")

main()

Sample console display output of executing the main testing program AoneBT.py

=== A1B, Enhanced ArrayList, by <Student NAME> <Student ID> ===

--- 1. New AL created, isEmptyL() result: True

--- 2. Finished appendL(): A,C > ABC,D,B ---

>>> AList Display, with size/last<5>, capacity<10>:

> A > C > ABC > D > B

<CHECK> removeLastL(), elt is B

--- 3. Finished removeLastL() ---

>>> AList Display, with size/last<4>, capacity<10>:

> A > C > ABC > D

--- 4. isEmptyL(), value: False

--- 5. searchL('ABC'), pos value: 3

--- 6. searchL('XYZ'), pos value: -1

=== Program ends ===

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):

# 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)	Description
__init__():	Create and initiate a new DLL (constructor, GIVEN)
insertAsTail(elt):	Insert element elt as a new tail (GIVEN)
displayDL():	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

Given Materials:

o Python file AoneC.py, to be modified and completed by student. Also modify top comments for your STUDENT INFO. (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

=== A1C, DLList program, by <Student NAME> <Student ID> ===

--- 1. New DLL created ---