ECS 032B FQ 2022 Programming Assignment 1
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Programming Assignment 1
ECS 032B FQ 2022
Setup:
Python3 . 6 + to develop and run your code .
Provided files:
PA1 /
__init__.py
pythonreview . py
arrays.py
linkedlist.py
adts.py
utils.py
This file is very important . Make sure to read and understand the code inside .
Hint: You may not need to override some of the provided functions .
test.py
Run this file to test your code .
tests/
test_ pythonreview . py
test_arrays.py
test_linkedlist.py
test_adts.py
Submission instructions:
Submit all provided files through Gradescope as a zip file .
Do not remove/ rename files nor change any naming conventions .
You should receive your grade for correctness automatically .
Rubric:
Correctness = 18 points
TAs will double - check your assignment to ensure that you are adhering the specifications . They may overrule your score if you break the listed restrictions .
Documentation = 2 points
Provide comments in code and good documentation on Gradescope . A TA will grade this based on correctness .
Extra Cre dit
+ 0.2 points for every day you turn in all parts (Python files + Documentation) early . You must submit all parts; the latest day will be counted .
( Maximum : 2 points)
Section 1: Python Review (pythonreview.py)
No additional modules to be imported for this section .
You may use itertools (see:
https://docs.python.org/3/library/itertools.html#itertools.combinations ) You may use any built - in Python functionalities .
def findWithSum(arr :list, val :int, n=2 :int) -> dict :
Given a list of integers arr and integer val, find n integers in arr that add up to the val. Return a dictionary with keys as indices of the n elements and the values as the value of the elements.
Assume that each input would have exactly one solution. If no solutions exist, then return an empty dictionary.
For Section 2-4:
No additional modules may be imported .
Do not modify the arguments or the naming of the already defined functions . You may not use built - in Python data structures .
Cannot use any of the following:
Section 2: Dynamic Array (arrays.py)
In this section, you will implement a dynamic array using the StaticArray class This cla ss extends the given StaticArray class (a child class of Collections) .
Enforce shifting property:
There should not be empty slots (i . e . None) between occupied slots .
This property is not enforced in StaticArray, hence some modifications must be made . Assume that None cannot be an element in Collections
Follow this resizing rule:
Double the size if more than 80% is occupied . Only double upon adding new items . Halve the size if less than 20% is occupied . Only halve upon removing items .
class DynamicArray(StaticArray):
def __init__(self, size:int, isSet = False :bool) :
Constructor for collection with size empty slots.
To determine whether this collection will enforce the set property, use isSet argument. def __getitem__(self, index:int) -> Any:
Return the value at the index of the collection.
def __setitem__(self, index :int, value:Any) -> None:
Set the index of the collection to the value.
def __delitem__(self, index:int) -> None:
Remove the element at index of the collection.
def append(self, value:Any) -> None:
Add value to collection at the next open slot.
def extend(self, arr:Collections) -> None:
Append the values of arr to the collection.
def remove(self, value:Any) -> None:
Remove the first instance of the value from collection.
def argwhere(self, value:Any) -> StaticArray:
Find the value in your collection.
Returns a StaticArray with elements containing the indices where the value exists. def __eq__(self, arr:Collections) -> bool :
Check whether arr is equivalent to this collection
Two collections are equal only if they share all the same values, in the correct order. Their sizes do not matter.
def __len__(self) -> int :
Return the number of total slots.
def get_size(self) -> int :
Return the number of elements in this collection.
def __iter__(self) -> Any :
Yield the next value (Used for iterable functions)
def reallocate(self, size:int) -> None:
Reallocate your collection to a new collection with size.
This is where you transfer over your existing content.
This function should call resize.
def resize(self, size:int) -> None:
Do not modify this function.
Resizes your data to size.
This function is destructive! Remember to back-up your previous data somewhere else.
Section 3: Linked Lists (linkedlist.py)
In this section, you will be implementing a linked list using the Node class .
You will mostly follow the same instructions as Section 2, but with a linked list implementation .
As this class extends Collections, you will have to implement all those functions .
Whenever you return a value from the linked list, return it as a Node. Do not return the data of the node .
The purpose of returning the node instead of the data itself is mostly just for testing and making sure that you are adhering to the requirements . In practice, you should just return the data .
When you store values in the linked list, you will accept as the original data type and internally wrap it and store it as Node
class LinkedList(Collections):
def __init__(self, isSet = False :bool, isDoubly = False:bool, isCircular =
False:bool) :
Constructor for linked list.
To determine whether this collection will enforce the set property, use isSet argument. To determine whether this linked list is a doubly or not, use the isDoubly argument. To determine whether this linked list is a circular or not, use the isCircular argument.
Section 4: Stacks and Queue ADTs (adts.py)
In this section, you will be implementing stacks and queues .
Use your DynamicCollection and LinkedList implementations .
class StackOrQueue () :
def __init__(self, isQueue = False :bool, isLinked = False :bool,) :
This function will initialize this collection.
Implement this collection is a singly linked list if isLinked = True. Otherwise, use a dynamic array.
To determine whether this collection is a queue or stack, use the isQueue argument. def peek(self) -> Any:
Return the first value in the collection but do not remove the value.
def push(self, value: Any) -> None:
Add the value into the collection.
Treat this as enqueue if isQueue is used.
def pop(self) -> Any:
Remove and return the first value from the collection.
If collection is empty, return None.
Treat this as dequeue if isQueue is used.
2022-09-24