Name: CS261 Data Structures Assignment 1 to 6 solutions
SKU: 43442
Price: 160.00 USD
Availability: InStock

Description

5/5 - (1 vote)

CS261 Assignment 1 Python Fundamentals Review

Summary

For this assignment, you will write a few short Python functions. The primary objectives are
to ensure that:
● You are familiar with basic Python syntax constructs
● Your programming environment is set up correctly
● You are familiar with submitting assignments through Gradescope, and
troubleshooting your solutions based on Gradescope output

● You know how to import and use classes that have been pre-written for you
For this course, we assume you are comfortable with:
● Iterating over a list of elements using for and while loops
● Accessing elements in a list or array using their indices
● Passing functions as parameters to other functions
● Using classes pre-written for you (imported into your code to create objects)
● Writing your own classes (including extending existing classes)
● Writing unit tests for your code
● Debugging your solutions

None of the functions in this assignment, or CS261 in general, will require Python
knowledge beyond what was covered in CS161 and CS162. If you completed the
CS161/CS162 classes in Python, you should be able to complete this assignment. In case
you need help, please post questions on Ed Discussion and feel free to contact the
instructor/ULAs in Teams during Office Hours.

General Instructions

1. The code for this assignment must be written in Python 3 and submitted to
Gradescope before the due date specified on Canvas and in the Course Schedule. You
may resubmit your code as many times as necessary (this is encouraged).
Gradescope allows you to choose which submission will be graded.

2. In Gradescope, your code will run through several tests. Any failed tests will provide
a brief explanation of testing conditions to help you with troubleshooting. Your goal is
to pass all tests.

3. We encourage you to create your own test cases, even though this work doesn’t
have to be submitted and won’t be graded. Gradescope tests are limited in scope and
may not cover all edge cases. Your submission must work on all valid inputs. We
reserve the right to test your submission with additional tests beyond Gradescope.
4. Your code must have an appropriate level of comments. At minimum, each
method must have a descriptive docstring. Additionally, write comments throughout
your code to make it easy to follow and understand any non-obvious code.

5. You will be provided with a starter “skeleton” code, on which you will build your
implementation. Methods defined in the skeleton code must retain their names and
input/output parameters. Variables defined in the skeleton code must also retain
their names. We will only test your solution by making calls to methods defined in
the skeleton code, and by checking values of variables defined in the skeleton code.
You can add more helper methods and variables, as needed. You also are allowed to
add optional default parameters to method definitions.

6. The skeleton code and code examples provided in this document are part of
assignment requirements. Please read all of them very carefully. They have been
carefully selected to demonstrate requirements for each method. Refer to them for
detailed descriptions of expected method behavior, input/output parameters, and
handling of edge cases.

7. For each method, you are required to use an iterative solution. Recursion is
not permitted.
8. Unless indicated otherwise, we will test your implementation with different types of
objects, not just integers. We guarantee that all such objects will have correct
implementation of methods __eq__(), __lt__(), __gt__(), __ge__(), __le__(),
and __str__().

Specific Instructions

There are 10 separate problems in this assignment. For each problem, you will write a
Python function according to the provided specifications. The skeleton code and some basic
test cases for each problem are provided in the file assignment1.py
Most problems will take as input (and sometimes return as output) an object of the
StaticArray class. The StaticArray class has been pre-written for you, and is located in the
file static_array.py

StaticArray is a very simple class that simulates the behavior of a fixed size array. It has
only four methods, and contains code to support bracketed indexing ([]):
1) init() – Creates a new static array that will store a fixed number of elements. Once
the StaticArray is created, its size cannot be changed.
2) set() – Changes the value of any element using its index.
3) get() – Reads the value of any element using its index.
4) length() – Queries the number of elements in the array.

Please review the code and comments in the StaticArray class to better understand the
available methods, their use, and input/output parameters. Note that since StaticArray is
intentionally a very simple class, it does not possess the many capabilities typically
associated with Python lists. You need to write your solutions using only the available
StaticArray functionality, as described above.

RESTRICTIONS: You are NOT allowed to use ANY built-in Python data structures and/or
their methods in any of your solutions. This includes built-in Python lists, dictionaries, or
anything else. Variables for holding a single value, or a tuple holding two/three values, are
allowed. It is also OK to use built-in Python generator functions like range().
You are NOT allowed to directly access any variables of the StaticArray class (e.g.
self._size or self._data). Access to StaticArray variables must be done by using the
StaticArray class methods.

Read the Coding Guides and Tips module for a detailed description of these topics.
You may not use any imports beyond the ones included in the assignment source code.
Table of Contents Page 5 of 19
min_max(arr: StaticArray) -> tuple:
Write a function that receives a one-dimensional array of integers and returns a Python
tuple with two values – the minimum and maximum values of the input array.
The content of the input array must not be changed. You may assume that the input array
will contain only integers, and will have at least one element. You do not need to check for
these conditions.

For full credit, the function must be implemented with O(N) complexity.
Example #1:
arr = StaticArray(5)
for i, value in enumerate([7, 8, 6, -5, 4]):
arr[i] = value
print(arr)
result = min_max(arr)
if result:
print(f”Min: {result[0]: 3}, Max: {result[1]}”)
else:
print(“min_max() not yet implemented”)
Output:
STAT_ARR Size: 5 [7, 8, 6, -5, 4]
Min: -5, Max: 8
Example #2:
arr = StaticArray(1)
arr[0] = 100
print(arr)
result = min_max(arr)
if result:
print(f”Min: {result[0]}, Max: {result[1]}”)
else:
print(“min_max() not yet implemented”)
Output:
STAT_ARR Size: 1 [100]
Min: 100, Max: 100

Example #3:
print(‘\n# min_max example 3’)
test_cases = (
[3, 3, 3],
[-10, -30, -5, 0, -10],
[25, 50, 0, 10],
)
for case in test_cases:
arr = StaticArray(len(case))
for i, value in enumerate(case):
arr[i] = value
print(arr)
result = min_max(arr)
if result:
print(f”Min: {result[0]: 3}, Max: {result[1]}”)
else:
print(“min_max() not yet implemented”)
Output:
STAT_ARR Size: 3 [3, 3, 3]
Min: 3, Max: 3
STAT_ARR Size: 5 [-10, -30, -5, 0, -10]
Min: -30, Max: 0
STAT_ARR Size: 4 [25, 50, 0, 10]
Min: 0, Max: 50
Table of Contents Page 7 of 19
fizz_buzz(arr: StaticArray) -> StaticArray:

Write a function that receives a StaticArray of integers and returns a new StaticArray object
with the content of the original array, modified as follows:
1) If the number in the original array is divisible by 3, the corresponding element in the
new array will be the string ‘fizz’.
2) If the number in the original array is divisible by 5, the corresponding element in the
new array will be the string ‘buzz’.

3) If the number in the original array is both a multiple of 3 and a multiple of 5, the
corresponding element in the new array will be the string ‘fizzbuzz’.
4) In all other cases, the element in the new array will have the same value as in the
original array.
The content of the input array must not be changed. You may assume that the input array
will contain only integers, and will have at least one element. You do not need to check for
these conditions.

For full credit, the function must be implemented with O(N) complexity.
Example #1:
source = [_ for _ in range(-5, 20, 4)]
arr = StaticArray(len(source))
for i, value in enumerate(source):
arr[i] = value
print(fizz_buzz(arr))
print(arr)
Output:
STAT_ARR Size: 7 [‘buzz’, -1, ‘fizz’, 7, 11, ‘fizzbuzz’, 19]
STAT_ARR Size: 7 [-5, -1, 3, 7, 11, 15, 19]

reverse(arr: StaticArray) -> None:
Write a function that receives a StaticArray and reverses the order of the elements in the
array. The reversal must be done ‘in place’, meaning that the original input array will be
modified, and you may not create another array (nor need to). You may assume that the
input array will contain at least one element. You do not need to check for this condition.

For full credit, the function must be implemented with O(N) complexity.
Example #1:
source = [_ for _ in range(-20, 20, 7)]
arr = StaticArray(len(source))
for i, value in enumerate(source):
arr.set(i, value)
print(arr)
reverse(arr)
print(arr)
reverse(arr)
print(arr)
Output:
STAT_ARR Size: 6 [-20, -13, -6, 1, 8, 15]
STAT_ARR Size: 6 [15, 8, 1, -6, -13, -20]
STAT_ARR Size: 6 [-20, -13, -6, 1, 8, 15]
Table of Contents Page 9 of 19
rotate(arr: StaticArray, steps: int) -> StaticArray:

Write a function that receives two parameters – a StaticArray and an integer value (called
steps). The function will create and return a new StaticArray, which contains all of the
elements from the original array, but their position has shifted right or left steps number of
times. The original array must not be modified.

If steps is a positive integer, the elements will be rotated to the right. Otherwise, they will
rotate to the left. Please see the code examples below for additional details. You may
assume that the input array will contain at least one element. You do not need to check for
this condition.

Please note that the value of the steps parameter can be very large (between -10
9 and
10

9). Your implementation must rotate an array of at least 1,000,000 elements in a
reasonable amount of time (under a minute).
For full credit, the function must be implemented with O(N) complexity.
Example #1:
source = [_ for _ in range(-20, 20, 7)]
arr = StaticArray(len(source))
for i, value in enumerate(source):
arr.set(i, value)
print(arr)
for steps in [1, 2, 0, -1, -2, 28, -100, 2**28, -2**31]:
space = “ ” if steps >= 0 else “”
print(f”{rotate(arr, steps)} {space}{steps}”)
print(arr)
Output:
STAT_ARR Size: 6 [-20, -13, -6, 1, 8, 15]
STAT_ARR Size: 6 [15, -20, -13, -6, 1, 8] 1
STAT_ARR Size: 6 [8, 15, -20, -13, -6, 1] 2
STAT_ARR Size: 6 [-20, -13, -6, 1, 8, 15] 0
STAT_ARR Size: 6 [-13, -6, 1, 8, 15, -20] -1
STAT_ARR Size: 6 [-6, 1, 8, 15, -20, -13] -2
STAT_ARR Size: 6 [-6, 1, 8, 15, -20, -13] 28
STAT_ARR Size: 6 [8, 15, -20, -13, -6, 1] -100
STAT_ARR Size: 6 [-6, 1, 8, 15, -20, -13] 268435456
STAT_ARR Size: 6 [-6, 1, 8, 15, -20, -13] -2147483648
STAT_ARR Size: 6 [-20, -13, -6, 1, 8, 15]

Example #2:
array_size = 1_000_000
source = [random.randint(-10**9, 10**9) for _ in range(array_size)]
arr = StaticArray(len(source))
for i, value in enumerate(source):
arr[i] = value
print(f’Started rotating large array of {array_size} elements’)
rotate(arr, 3**14)
rotate(arr, -3**15)
print(f’Finished rotating large array of {array_size} elements’)
Output:
Started rotating large array of 1000000 elements
Finished rotating large array of 1000000 elements
Table of Contents Page 11 of 19
sa_range(start: int, end: int) -> StaticArray:

Write a function that receives the two integers start and end, and returns a StaticArray that
contains all the consecutive integers between start and end (inclusive).
For full credit, the function must be implemented with O(N) complexity.
Example #1:
cases = [
(1, 3), (-1, 2), (0, 0), (0, -3),
(-95, -89), (-89, -95)
]
for start, end in cases:
print(f”Start: {start: 4}, End: {end: 4}, {sa_range(start, end)}”)
Output:
Start: 1, End: 3, STAT_ARR Size: 3 [1, 2, 3]
Start: -1, End: 2, STAT_ARR Size: 4 [-1, 0, 1, 2]
Start: 0, End: 0, STAT_ARR Size: 1 [0]
Start: 0, End: -3, STAT_ARR Size: 4 [0, -1, -2, -3]
Start: -95, End: -89, STAT_ARR Size: 7 [-95, -94, -93, -92, -91, -90, -89]
Start: -89, End: -95, STAT_ARR Size: 7 [-89, -90, -91, -92, -93, -94, -95]

is_sorted(arr: StaticArray) -> int:
Write a function that receives a StaticArray and returns an integer that describes whether
the array is sorted. The method must return:
● 1 if the array is sorted in strictly ascending order.
● -1 if the list is sorted in strictly descending order.
● 0 otherwise.

Arrays consisting of a single element are considered sorted in strictly ascending order.
You may assume that the input array will contain at least one element, and that values
stored in the array are all of the same type (either all numbers, or strings, or custom
objects, but never a mix of these). You do not need to write checks for these conditions.
The original array must not be modified.

For full credit, the function must be implemented with O(N) complexity, with no additional
data structures (including Static Arrays) being created.
Example #1:
test_cases = (
[-100, -8, 0, 2, 3, 10, 20, 100],
[‘A’, ‘B’, ‘Z’, ‘a’, ‘z’],
[‘Z’, ‘T’, ‘K’, ‘A’, ‘5’],
[1, 3, -10, 20, -30, 0],
[-10, 0, 0, 10, 20, 30],
[100, 90, 0, -90, -200],
[‘apple’]
)
for case in test_cases:
arr = StaticArray(len(case))
for i, value in enumerate(case):
arr[i] = value
result = is_sorted(arr)
space = “ ” if result and result >= 0 else “ ”
print(f”Result:{space}{result}, {arr}”)
Output:
Result: 1, STAT_ARR Size: 8 [-100, -8, 0, 2, 3, 10, 20, 100]
Result: 1, STAT_ARR Size: 5 [‘A’, ‘B’, ‘Z’, ‘a’, ‘z’]
Result: -1, STAT_ARR Size: 5 [‘Z’, ‘T’, ‘K’, ‘A’, ‘5’]
Result: 0, STAT_ARR Size: 6 [1, 3, -10, 20, -30, 0]
Result: 0, STAT_ARR Size: 6 [-10, 0, 0, 10, 20, 30]
Result: -1, STAT_ARR Size: 5 [100, 90, 0, -90, -200]
Result: 1, STAT_ARR Size: 1 [‘apple’]
Table of Contents Page 13 of 19
find_mode(arr: StaticArray) -> tuple:

Write a function that receives a StaticArray that is sorted in order, either non-descending or
non-ascending. The function will return, in this order, the mode (most-occurring value) of
the array, and its frequency (how many times it appears).
If there is more than one value that has the highest frequency, select the one that occurs
first in the array.

remove_duplicates(arr: StaticArray) -> StaticArray:
Write a function that receives a StaticArray that is already in sorted order, either
non-descending or non-ascending. The function will return a new StaticArray with all
duplicate values removed. The original array must not be modified.
You may assume that the input array will contain at least one element, and that values
stored in the array are all of the same type (either all numbers, or strings, or custom
objects, but never a mix of these), and that elements of the input array are already in
sorted order. You do not need to write checks for these conditions.

For full credit, the function must be implemented with O(N) complexity.
Example #1:
test_cases = (
[1], [1, 2], [1, 1, 2], [1, 20, 30, 40, 500, 500, 500],
[5, 5, 5, 4, 4, 3, 2, 1, 1], [1, 1, 1, 1, 2, 2, 2, 2]
)
for case in test_cases:
arr = StaticArray(len(case))
for i, value in enumerate(case):
arr[i] = value
print(arr)
print(remove_duplicates(arr))
print(arr)
Output:
STAT_ARR Size: 1 [1]
STAT_ARR Size: 1 [1]
STAT_ARR Size: 2 [1, 2]
STAT_ARR Size: 2 [1, 2]
STAT_ARR Size: 3 [1, 1, 2]
STAT_ARR Size: 2 [1, 2]
STAT_ARR Size: 7 [1, 20, 30, 40, 500, 500, 500]
STAT_ARR Size: 5 [1, 20, 30, 40, 500]
STAT_ARR Size: 9 [5, 5, 5, 4, 4, 3, 2, 1, 1]
STAT_ARR Size: 5 [5, 4, 3, 2, 1]
STAT_ARR Size: 8 [1, 1, 1, 1, 2, 2, 2, 2]
STAT_ARR Size: 2 [1, 2]
STAT_ARR Size: 8 [1, 1, 1, 1, 2, 2, 2, 2]
Table of Contents Page 15 of 19
count_sort(arr: StaticArray) -> StaticArray:

Write a function that receives a StaticArray and returns a new StaticArray with the same
content sorted in non-ascending order, using the count sort algorithm. The original array
must not be modified.

What is count sort? The name of the algorithm may seem confusing, if not deceptive – it’s
really not a sort as you might commonly view one. While the end result is a sorted
version of the original array, the means by which we arrive there may be a bit different.
For example, a sorted array can be generated if you know what values are present, and how
many times they occur. Note that other functions in this assignment will help you determine
how many different values could be in the array, as well as the range of possible values
present.

Getting Started: As mentioned, we want to create a sorted array by counting the number
of times each value appears in the unsorted array. A possible first step would be to find the
range of numbers in the array, and use that range to create a new ‘count array’ that
tabulates the number of times each element is present in the original array. The ‘count
array’ will then provide you with the information you need to generate a sorted array.
You may assume that the input array will contain at least one element, and that all elements
will be integers in the range [-10
9
, 10
9].

It is guaranteed that the difference between the
maximum and minimum values in the input will be less than 1,000. You do not need to write
checks for these conditions.
Implement a solution that can sort at least 5,000,000 elements in a reasonable amount of
time (under a minute). Note that using a traditional sorting algorithm (even a fast sorting
algorithm like merge sort or shell sort) will not pass the largest test case of 5M elements.
For full credit, the function must be implemented with O(n+k) time complexity, where n is
the number of elements and k is the range of values.

Example #1:
test_cases = (
[1, 2, 4, 3, 5], [5, 4, 3, 2, 1], [0, -5, -3, -4, -2, -1, 0],
[-3, -2, -1, 0, 1, 2, 3], [1, 2, 3, 4, 3, 2, 1, 5, 5, 2, 3, 1],
[10100, 10721, 10320, 10998], [-100320, -100450, -100999, -100001],
)
for case in test_cases:
arr = StaticArray(len(case))
for i, value in enumerate(case):
arr[i] = value
before = arr if len(case) < 50 else ‘Started sorting large array’
print(f”Before: {before}”)
result = count_sort(arr)
after = result if len(case) < 50 else ‘Finished sorting large array’
print(f”After: {after}”)

Output:
Before: STAT_ARR Size: 5 [1, 2, 4, 3, 5]
After : STAT_ARR Size: 5 [5, 4, 3, 2, 1]
Before: STAT_ARR Size: 5 [5, 4, 3, 2, 1]
After : STAT_ARR Size: 5 [5, 4, 3, 2, 1]
Before: STAT_ARR Size: 7 [0, -5, -3, -4, -2, -1, 0]
After : STAT_ARR Size: 7 [0, 0, -1, -2, -3, -4, -5]
Before: STAT_ARR Size: 7 [-3, -2, -1, 0, 1, 2, 3]
After : STAT_ARR Size: 7 [3, 2, 1, 0, -1, -2, -3]
Before: STAT_ARR Size: 12 [1, 2, 3, 4, 3, 2, 1, 5, 5, 2, 3, 1]
After : STAT_ARR Size: 12 [5, 5, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1]
Before: STAT_ARR Size: 4 [10100, 10721, 10320, 10998]
After : STAT_ARR Size: 4 [10998, 10721, 10320, 10100]
Before: STAT_ARR Size: 4 [-100320, -100450, -100999, -100001]
After : STAT_ARR Size: 4 [-100001, -100320, -100450, -100999]
Example #2:
array_size = 5_000_000
min_val = random.randint(-10**9, 10**9 – 998)
max_val = min_val + 998
case = [random.randint(min_val, max_val) for _ in range(array_size)]
arr = StaticArray(len(case))
for i, value in enumerate(case):
arr[i] = value
print(f’Started sorting large array of {array_size} elements’)
result = count_sort(arr)
print(f’Finished sorting large array of {array_size} elements’)

Output:
Started sorting large array of 5000000 elements
Finished sorting large array of 5000000 elements
Table of Contents Page 17 of 19
sorted_squares(arr: StaticArray) -> StaticArray:

Write a function that receives a StaticArray where the elements are in sorted order, and
returns a new StaticArray with squares of the values from the original array, sorted in
non-descending order. The original array must not be modified.
You may assume that the input array will have at least one element, will contain only
integers in the range [-10
9
, 10
9], and that elements of the input array are already in
non-descending order.

You do not need to write checks for these conditions.
Implement a FAST solution that can process at least 5,000,000 elements in a reasonable
amount of time (under a minute).
Note that using a traditional sorting algorithm (even a fast sorting algorithm like merge sort
or shell sort) will not pass the largest test case of 5M elements. Also, a solution using
count_sort() as a helper method will also not work here, due to the wide range of values in
the input array.

For full credit, the function must be implemented with O(N) complexity.
Example #1:
test_cases = (
[1, 2, 3, 4, 5],
[-5, -4, -3, -2, -1, 0],
[-3, -2, -2, 0, 1, 2, 3],
)
for case in test_cases:
arr = StaticArray(len(case))
for i, value in enumerate(sorted(case)):
arr[i] = value
print(arr)
result = sorted_squares(arr)
print(result)
Output:
STAT_ARR Size: 5 [1, 2, 3, 4, 5]
STAT_ARR Size: 5 [1, 4, 9, 16, 25]
STAT_ARR Size: 6 [-5, -4, -3, -2, -1, 0]
STAT_ARR Size: 6 [0, 1, 4, 9, 16, 25]
STAT_ARR Size: 7 [-3, -2, -2, 0, 1, 2, 3]
STAT_ARR Size: 7 [0, 1, 4, 4, 4, 9, 9]

Example #2:
array_size = 5_000_000
case = [random.randint(-10**9, 10**9) for _ in range(array_size)]
arr = StaticArray(len(case))
for i, value in enumerate(sorted(case)):
arr[i] = value
print(f’Started sorting large array of {array_size} elements’)
result = sorted_squares(arr)
print(f’Finished sorting large array of {array_size} elements’)
Output:
Started sorting large array of 5000000 elements
Finished sorting large array of 5000000 elements

CS261 Assignment 2 Dynamic Array Implementation (plus a brand new Bag)

General Instructions ………………………………………………………….

3 Part 1 – Dynamic Array Implementation Summary and Specific Instructions ……………………………………….. 5 resize() …………………………………………………………………………. 6 append() ……………………………………………………………………….. 7 insert_at_index() ………………………………………………………………8 remove_at_index() …………………………………………………………. 10 slice() …………………………………………………………………………. 13 merge() ………………………………………………………………………. 14 map() …………………………………………………………………………. 15 filter() …………………………………………………………………………. 16 reduce() ………………………………………………………………………. 17 find_mode() ………………………………………………………………….. 18 Part 2 – Bag ADT Implementation Summary and Specific Instructions ……………………………………… 20 add() ………………………………………………………………………….. 21 remove() ……………………………………………………………………… 21 count() …………………………………………………………………………22 clear() ………………………………………………………………………….22 equal() ………………………………………………………………………… 23 __iter__() …………………………………………………………………….. 24 __next__() …………………………………………………………………… 24

General Instructions

1. Programs in this assignment must be written in Python 3 and submitted to Gradescope before the due date specified on Canvas and in the Course Schedule. You may resubmit your code as many times as necessary. Gradescope allows you to choose which submission will be graded. 2. In Gradescope, your code will be run through several tests. Any failed tests will provide a brief explanation of testing conditions to help you with troubleshooting. Your goal is to pass all tests.

3. We encourage you to create your own test cases, even though this work won’t have to be submitted and won’t be graded. Gradescope tests are limited in scope and may not cover all edge cases. Your submission must work on all valid inputs. We reserve the right to test your submission with more tests than Gradescope. 4. Your code must have an appropriate level of comments.

At a minimum, each method should have a descriptive docstring. Additionally, write comments throughout your code to make it easy to follow and understand any non-obvious code. 5. You will be provided with a starter “skeleton” code, on which you will build your implementation. Methods defined in the skeleton code must retain their names and input/output parameters. Variables defined in the skeleton code must also retain their names. We will only test your solution by making calls to methods defined in the skeleton code, and by checking values of variables defined in the skeleton code. You can add more methods and variables, as needed.

However, certain classes and methods cannot be changed in any way. Please see the comments in the skeleton code for guidance. The content of any methods pre-written for you as part of the skeleton code must not be changed. Half points will be deducted from DynamicArray’s find_mode() for the incorrect time complexity. All points will be deducted from Bag methods for the incorrect time complexity. Note that the __iter__() method in the Bag implementation will require you to add variables in that method, and this is permitted. 6. The skeleton code and code examples provided in this document are part of the assignment requirements.

They have been carefully selected to demonstrate requirements for each method. Refer to them for a detailed description of expected method behavior, input/output parameters, and handling of edge cases. Code examples may include assignment requirements not explicitly stated elsewhere. Table of Contents Page 3 of 24 7. For each method, you are required to use an iterative solution. Recursion is not permitted. We will specify the maximum input size that your solution must handle. 8. You may not use any imports beyond the ones included in the assignment source code.

Part 1 – Summary and Specific Instructions

1. Implement a DynamicArray class by completing the skeleton code provided in the file dynamic_array.py. The DynamicArray class will use a StaticArray object as its underlying data storage container, and will provide many methods similar to the functionality of Python lists. Once completed, your implementation will include the following methods: resize() append() insert_at_index() remove_at_index() slice() merge() map() filter() reduce() * Several class methods, like is_empty(), length(), get_at_index(), and set_at_index() have been pre-written for you. * The dynamic_array.py file also contains the find_mode() function, but this is a separate function outside the class that you will need to implement.

2. We will test your implementations with different types of objects, not just integers. We guarantee that all such objects will have correct implementation of methods __eq__(), __lt__(), __gt__(), __ge__(), __le__(), and __str__(). 3. The number of objects stored in the array at any given time will be between 0 and 1,000,000 inclusive. An array must allow for the storage of duplicate objects. 4. Variables in the DynamicArray class are marked as private, so they may only be accessed and/or changed directly inside the class. Use the provided getter or setter methods when you need this functionality outside of the DynamicArray class.

5. RESTRICTIONS: You are NOT allowed to use ANY built-in Python data structures and/or their methods in any of your solutions. This includes built-in Python lists, dictionaries, or anything else. You must solve this portion of the assignment by importing and using objects of the StaticArray class (prewritten for you), and using class methods to write your solution. You are also not allowed to directly access any variables of the StaticArray class (e.g. self._size or self._data). Access to StaticArray variables must only be done by using the StaticArray class methods.

Don’t forget to include your StaticArray class from Assignment 1 in your project. Read the Coding Guides and Tips module for a detailed description of these topics. Table of Contents Page 5 of 24 resize(self, new_capacity: int) -> None: This method changes the capacity of the underlying storage for the elements in the dynamic array. It does not change the values or the order of any elements currently stored in the array. It is intended to be an “internal” method of the DynamicArray class, called by other class methods such as append(), remove_at_index(), or insert_at_index(), to manage the capacity of the underlying data structure. The method should only accept positive integers for new_capacity. Additionally, new_capacity cannot be smaller than the number of elements currently stored in the dynamic array (which is tracked by the self._size variable).

If new_capacity is not a positive integer, or if new_capacity is less than self._size, this method should not do any work and immediately exit. Example #1: da = DynamicArray() da.print_da_variables() da.resize(8) da.print_da_variables() da.resize(2) da.print_da_variables() da.resize(0) da.print_da_variables() Output: Length: 0, Capacity: 4, STAT_ARR Size: 4 [None, None, None, None] Length: 0, Capacity: 8, STAT_ARR Size: 8 [None, None, None, None, None, None, None, None] Length: 0, Capacity: 2, STAT_ARR Size: 2 [None, None] Length: 0, Capacity: 2, STAT_ARR Size: 2 [None, None] NOTE: Example 2 below will not work properly unless the append() method is implemented. Example #2: da = DynamicArray([1, 2, 3, 4, 5, 6, 7, 8]) print(da) da.resize(20) print(da) da.resize(4) print(da) Output: DYN_ARR Size/Cap: 8/8 [1, 2, 3, 4, 5, 6, 7, 8] DYN_ARR Size/Cap: 8/20 [1, 2, 3, 4, 5, 6, 7, 8] DYN_ARR Size/Cap: 8/20 [1, 2, 3, 4, 5, 6, 7, 8]

append(self, value: object) -> None: This method adds a new value at the end of the dynamic array. If the internal storage associated with the dynamic array is already full, you will need to DOUBLE its capacity before adding a new value (hint: you can use your already written resize() function for this). Example #1: da = DynamicArray() da.print_da_variables() da.append(1) da.print_da_variables() print(da) Output: Length: 0, Capacity: 4, STAT_ARR Size: 4 [None, None, None, None] Length: 1, Capacity: 4, STAT_ARR Size: 4 [1, None, None, None] DYN_ARR Size/Cap: 1/4 [1] Example #2: da = DynamicArray() for i in range(9): da.append(i + 101) print(da) Output: DYN_ARR Size/Cap: 1/4 [101] DYN_ARR Size/Cap: 2/4 [101, 102] DYN_ARR Size/Cap: 3/4 [101, 102, 103] DYN_ARR Size/Cap: 4/4 [101, 102, 103, 104] DYN_ARR Size/Cap: 5/8 [101, 102, 103, 104, 105] DYN_ARR Size/Cap: 6/8 [101, 102, 103, 104, 105, 106] DYN_ARR Size/Cap: 7/8 [101, 102, 103, 104, 105, 106, 107] DYN_ARR Size/Cap: 8/8 [101, 102, 103, 104, 105, 106, 107, 108] DYN_ARR Size/Cap: 9/16 [101, 102, 103, 104, 105, 106, 107, 108, 109] Example #3: da = DynamicArray() for i in range(600): da.append(i) print(da.length()) print(da.get_capacity()) Output: 600 1024 Table of Contents Page 7 of 24 insert_at_index(self, index: int, value: object) ->

None: This method adds a new value at the specified index in the dynamic array. Index 0 refers to the beginning of the array. If the provided index is invalid, the method raises a custom “DynamicArrayException”. Code for the exception is provided in the skeleton file. If the array contains N elements, valid indices for this method are [0, N] inclusive. If the internal storage associated with the dynamic array is already full, you will need to DOUBLE its capacity before adding a new value. Example #1: da = DynamicArray([100]) print(da) da.insert_at_index(0, 200) da.insert_at_index(0, 300) da.insert_at_index(0, 400) print(da) da.insert_at_index(3, 500) print(da) da.insert_at_index(1, 600) print(da) Output: DYN_ARR Size/Cap: 1/4 [100] DYN_ARR Size/Cap: 4/4 [400, 300, 200, 100] DYN_ARR Size/Cap: 5/8 [400, 300, 200, 500, 100] DYN_ARR Size/Cap: 6/8 [400, 600, 300, 200, 500, 100] Example #2: da = DynamicArray() try: da.insert_at_index(-1, 100) except Exception as e: print(“Exception raised:”, type(e)) da.insert_at_index(0, 200) try: da.insert_at_index(2, 300) except Exception as e: print(“Exception raised:”, type(e)) print(da) Output: Exception raised: <class ‘__main__.DynamicArrayException’> Exception raised: <class ‘__main__.DynamicArrayException’> DYN_ARR Size/Cap: 1/4 [200] Example #3:

da = DynamicArray() for i in range(1, 10): index, value = i – 4, i * 10 try: da.insert_at_index(index, value) except Exception as e: print(“Cannot insert value”, value, “at index”, index) print(da) Output: Cannot insert value 10 at index -3 Cannot insert value 20 at index -2 Cannot insert value 30 at index -1 DYN_ARR Size/Cap: 6/8 [40, 50, 60, 70, 80, 90] Table of Contents Page 9 of 24 remove_at_index(self, index: int) -> None: This method removes the element at the specified index in the dynamic array. Index 0 refers to the beginning of the array. If the provided index is invalid, the method raises a custom “DynamicArrayException”. Code for the exception is provided in the skeleton file. If the array contains N elements, valid indices for this method are [0, N – 1] inclusive. When the number of elements stored in the array (before removal) is STRICTLY LESS than ¼ of its current capacity, the capacity must be reduced to TWICE the number of current elements.

This check and capacity adjustment must occur BEFORE removal of the element. If the current capacity (before reduction) is 10 elements or less, reduction should not occur at all. If the current capacity (before reduction) is greater than 10 elements, the reduced capacity cannot become less than 10 elements. Please see the examples below, especially example #3, for clarification. Example #1: da = DynamicArray([10, 20, 30, 40, 50, 60, 70, 80]) print(da) da.remove_at_index(0) print(da) da.remove_at_index(6) print(da) da.remove_at_index(2) print(da) Output: DYN_ARR Size/Cap: 8/8 [10, 20, 30, 40, 50, 60, 70, 80] DYN_ARR Size/Cap: 7/8 [20, 30, 40, 50, 60, 70, 80] DYN_ARR Size/Cap: 6/8 [20, 30, 40, 50, 60, 70] DYN_ARR Size/Cap: 5/8 [20, 30, 50, 60, 70] Example #2: da = DynamicArray([1024]) print(da) for i in range(17): da.insert_at_index(i, i) print(da.length(), da.get_capacity()) for i in range(16, -1, -1): da.remove_at_index(0) print(da) Output: DYN_ARR Size/Cap: 1/4 [1024] 18 32 DYN_ARR Size/Cap: 1/10 [1024] Page 10 of 24

Example #3: da = DynamicArray() print(da.length(), da.get_capacity()) [da.append(1) for i in range(100)] # step 1 – add 100 elements print(da.length(), da.get_capacity()) [da.remove_at_index(0) for i in range(68)] # step 2 – remove 68 elements print(da.length(), da.get_capacity()) da.remove_at_index(0) # step 3 – remove 1 element print(da.length(), da.get_capacity()) da.remove_at_index(0) # step 4 – remove 1 element print(da.length(), da.get_capacity()) [da.remove_at_index(0) for i in range(14)] # step 5 – remove 14 elements print(da.length(), da.get_capacity()) da.remove_at_index(0) # step 6 – remove 1 element print(da.length(), da.get_capacity()) da.remove_at_index(0) # step 7 – remove 1 element print(da.length(), da.get_capacity()) for i in range(14): print(“Before remove_at_index(): “, da.length(), da.get_capacity(), end=””) da.remove_at_index(0) print(” After remove_at_index(): “, da.length(), da.get_capacity()) Output: 0 4 100 128 32 128 31 128 30 62 16 62 15 62 14 30 Before remove_at_index(): 14 30 After remove_at_index(): 13 30 Before remove_at_index(): 13 30 After remove_at_index(): 12 30

Before remove_at_index(): 12 30 After remove_at_index(): 11 30 Before remove_at_index(): 11 30 After remove_at_index(): 10 30 Before remove_at_index(): 10 30 After remove_at_index(): 9 30 Before remove_at_index(): 9 30 After remove_at_index(): 8 30 Before remove_at_index(): 8 30 After remove_at_index(): 7 30 Before remove_at_index(): 7 30 After remove_at_index(): 6 14 Before remove_at_index(): 6 14 After remove_at_index(): 5 14 Before remove_at_index(): 5 14 After remove_at_index(): 4 14 Before remove_at_index(): 4 14 After remove_at_index(): 3 14 Before remove_at_index(): 3 14 After remove_at_index(): 2 10 Before remove_at_index(): 2 10 After remove_at_index(): 1 10 Before remove_at_index(): 1 10 After remove_at_index(): 0 10 Table of Contents Page 11 of 24 Example #4: da = DynamicArray([1, 2, 3, 4, 5]) print(da) for _ in range(5): da.remove_at_index(0) print(da) Output: DYN_ARR Size/Cap: 5/8 [1, 2, 3, 4, 5] DYN_ARR Size/Cap: 4/8 [2, 3, 4, 5] DYN_ARR Size/Cap: 3/8 [3, 4, 5] DYN_ARR Size/Cap: 2/8 [4, 5] DYN_ARR Size/Cap: 1/8 [5] DYN_ARR Size/Cap: 0/8 [] Page 12 of 24

slice(self, start_index: int, size: int) -> object: This method returns a new DynamicArray object that contains the requested number of elements from the original array, starting with the element located at the requested start index. If the array contains N elements, a valid start_index is in range [0, N – 1] inclusive. A valid size is a non-negative integer. If the provided start index or size is invalid, or if there are not enough elements between the start index and the end of the array to make the slice of the requested size, this method raises a custom “DynamicArrayException”.

Code for the exception is provided in the skeleton file. Example #1: da = DynamicArray([1, 2, 3, 4, 5, 6, 7, 8, 9]) da_slice = da.slice(1, 3) print(da, da_slice, sep=”\n”) da_slice.remove_at_index(0) print(da, da_slice, sep=”\n”) Output: DYN_ARR Size/Cap: 9/16 [1, 2, 3, 4, 5, 6, 7, 8, 9] DYN_ARR Size/Cap: 3/4 [2, 3, 4] DYN_ARR Size/Cap: 9/16 [1, 2, 3, 4, 5, 6, 7, 8, 9] DYN_ARR Size/Cap: 2/4 [3, 4] Example #2: da = DynamicArray([10, 11, 12, 13, 14, 15, 16]) print(“SOURCE:”, da) slices = [(0, 7), (-1, 7), (0, 8), (2, 3), (5, 0), (5, 3), (6, 1), (6, -1)] for i, cnt in slices: print(“Slice”, i, “/”, cnt, end=””) try: print(” — OK: “, da.slice(i, cnt)) except: print(” — exception occurred.”) Output: SOURCE: DYN_ARR Size/Cap: 7/8 [10, 11, 12, 13, 14, 15, 16] Slice 0 / 7 — OK: DYN_ARR Size/Cap: 7/8 [10, 11, 12, 13, 14, 15, 16] Slice -1 / 7 — exception occurred. Slice 0 / 8 — exception occurred. Slice 2 / 3 — OK: DYN_ARR Size/Cap: 3/4 [12, 13, 14] Slice 5 / 0 — OK: DYN_ARR Size/Cap: 0/4 [] Slice 5 / 3 — exception occurred. Slice 6 / 1 — OK: DYN_ARR Size/Cap: 1/4 [16] Slice 6 / -1 — exception occurred.

Table of Contents Page 13 of 24 merge(self, second_da: object) -> None: This method takes another DynamicArray object as a parameter, and appends all elements from this array onto the current one, in the same order in which they are stored in the input array. Example #1: da = DynamicArray([1, 2, 3, 4, 5]) da2 = DynamicArray([10, 11, 12, 13]) print(da) da.merge(da2) print(da) Output: DYN_ARR Size/Cap: 5/8 [1, 2, 3, 4, 5] DYN_ARR Size/Cap: 9/16 [1, 2, 3, 4, 5, 10, 11, 12, 13] Example #2: da = DynamicArray([1, 2, 3]) da2 = DynamicArray() da3 = DynamicArray() da.merge(da2) print(da) da2.merge(da3) print(da2) da3.merge(da) print(da3) Output: DYN_ARR Size/Cap: 3/4 [1, 2, 3] DYN_ARR Size/Cap: 0/4 [] DYN_ARR Size/Cap: 3/4 [1, 2, 3]

map(self, map_func) ->object: This method creates a new dynamic array where the value of each element is derived by applying a given map_func to the corresponding value from the original array. This method works similarly to the Python map() function. For a review on how Python’s map() works, here is some suggested reading: ● https://docs.python.org/3/library/functions.html#map ● https://www.geeksforgeeks.org/python-map-function/ Example #1: da = DynamicArray([1, 5, 10, 15, 20, 25]) print(da) print(da.map(lambda x: (x ** 2))) Output: DYN_ARR Size/Cap: 6/8 [1, 5, 10, 15, 20, 25] DYN_ARR Size/Cap: 6/8 [1, 25, 100, 225, 400, 625] Example #2: def double(value): return value * 2 def square(value): return value ** 2 def cube(value): return value ** 3 def plus_one(value): return value + 1 da = DynamicArray([plus_one, double, square, cube]) for value in [1, 10, 20]: print(da.map(lambda x: x(value))) Output: DYN_ARR Size/Cap: 4/4 [2, 2, 1, 1] DYN_ARR Size/Cap: 4/4 [11, 20, 100, 1000] DYN_ARR Size/Cap: 4/4 [21, 40, 400, 8000] Table of Contents Page 15 of 24 filter(self, filter_func) ->object: This method creates a new dynamic array populated only with those elements from the original array for which filter_func returns True.

This method works similarly to the Python filter() function. For a review on how Python’s filter() works, here is some suggested reading: ● https://docs.python.org/3/library/functions.html#filter ● https://www.geeksforgeeks.org/filter-in-python/ Example #1: def filter_a(e): return e > 10 da = DynamicArray([1, 5, 10, 15, 20, 25]) print(da) result = da.filter(filter_a) print(result) print(da.filter(lambda x: (10 <= x <= 20))) Output: DYN_ARR Size/Cap: 6/8 [1, 5, 10, 15, 20, 25] DYN_ARR Size/Cap: 3/4 [15, 20, 25] DYN_ARR Size/Cap: 3/4 [10, 15, 20] Example #2: def is_long_word(word, length): return len(word) > length da = DynamicArray(“This is a sentence with some long words”.split()) print(da) for length in [3, 4, 7]: print(da.filter(lambda word: is_long_word(word, length))) Output: DYN_ARR Size/Cap: 8/8 [This, is, a, sentence, with, some, long, words] DYN_ARR Size/Cap: 6/8 [This, sentence, with, some, long, words] DYN_ARR Size/Cap: 2/4 [sentence, words] DYN_ARR Size/Cap: 1/4 [sentence]

reduce(self, reduce_func, initializer=None) ->object: This method sequentially applies the reduce_func to all elements of the dynamic array and returns the resulting value. It takes an optional initializer parameter. If this parameter is not provided, the first value in the array is used as the initializer. If the dynamic array is empty, the method returns the value of the initializer (or None, if one was not provided). This method works similarly to the Python reduce() function. For a review on how Python’s reduce() works, here is some suggested reading: ● https://www.geeksforgeeks.org/reduce-in-python/ Example #1: values = [100, 5, 10, 15, 20, 25] da = DynamicArray(values) print(da) print(da.reduce(lambda x, y: (x // 5 + y ** 2))) print(da.reduce(lambda x, y: (x + y ** 2), -1)) Output: DYN_ARR Size/Cap: 6/8 [100, 5, 10, 15, 20, 25] 714 11374 Explanation: 45 = (100 // 5) + 5 2 109 = (45 // 5) + 10 2 246 = (109 // 5) + 15 2 449 = (246 // 5) + 20 2 714 = (449 // 5) + 25 2 # -1 is the initializer 11374 = -1 + 100 2+ 5 2 + 10 2 + 15 2 + 20 2 + 25 2 Example #2: da = DynamicArray([100]) print(da.reduce(lambda x, y: x + y ** 2)) print(da.reduce(lambda x, y: x + y ** 2, -1)) da.remove_at_index(0) print(da.reduce(lambda x, y: x + y ** 2)) print(da.reduce(lambda x, y: x + y ** 2, -1)) Output: 100 9999 None -1 Table of Contents Page 17 of 24 find_mode(arr:

DynamicArray) -> (DynamicArray, int): Write a standalone function outside of the DynamicArray class that receives a dynamic array already in sorted order, either non-descending or non-ascending. The function will return a tuple containing (in this order) a dynamic array comprising the mode (most-occurring) value/s of the array, and an integer that represents the highest frequency (how many times they appear). If there is more than one value that has the highest frequency, all values at that frequency should be included in the array being returned in the order in which they appear in the input array. If there is only one mode, only that value should be included.

You may assume that the input array will contain at least one element, and that values stored in the array are all of the same type (either all numbers, or strings, or custom objects, but never a mix of these). You do not need to write checks for these conditions. For full credit, the function must be implemented with O(N) complexity with no additional data structures (beyond the array you return) being created. Example #1: test_cases = ( [1, 1, 2, 3, 3, 4], [1, 2, 3, 4, 5], [“Apple”, “Banana”, “Banana”, “Carrot”, “Carrot”, “Date”, “Date”, “Date”, “Eggplant”, “Eggplant”, “Eggplant”, “Fig”, “Fig”, “Grape”] ) for case in test_cases: da = DynamicArray(case) mode, frequency = find_mode(da) print(f”{da}\nMode: {mode}, Frequency: {frequency}\n”) case = [4, 3, 3, 2, 2, 2, 1, 1, 1, 1] da = DynamicArray() for x in range(len(case)): da.append(case[x]) mode, frequency = find_mode(da) print(f”{da}\nMode: {mode}, Frequency: {frequency}\n”) Output: DYN_ARR Size/Cap: 6/8 [1, 1, 2, 3, 3, 4] Mode: DYN_ARR Size/Cap: 2/4 [1, 3], Frequency: 2 DYN_ARR Size/Cap: 5/8 [1, 2, 3, 4, 5] Mode: DYN_ARR Size/Cap: 5/8 [1, 2, 3, 4, 5], Frequency: 1 Page 18 of 24 CS261 Data Structures Assignment 2: Dynamic Array Implementation DYN_ARR Size/Cap: 14/16 [Apple, Banana, Banana, Carrot, Carrot, Date, Date, Date, Eggplant, Eggplant, Eggplant, Fig, Fig, Grape] Mode: DYN_ARR Size/Cap: 2/4 [Date, Eggplant], Frequency: 3 DYN_ARR Size/Cap: 1/4 [4] Mode: DYN_ARR Size/Cap: 1/4 [4], Frequency: 1 DYN_ARR Size/Cap: 2/4 [4, 3] Mode: DYN_ARR Size/Cap: 2/4 [4, 3], Frequency: 1 DYN_ARR Size/Cap: 3/4 [4, 3, 3] Mode: DYN_ARR Size/Cap: 1/4 [3], Frequency: 2 DYN_ARR Size/Cap: 4/4 [4, 3, 3, 2] Mode: DYN_ARR Size/Cap: 1/4 [3], Frequency: 2 DYN_ARR Size/Cap: 5/8 [4, 3, 3, 2, 2] Mode: DYN_ARR Size/Cap: 2/4 [3, 2], Frequency: 2 DYN_ARR Size/Cap: 6/8 [4, 3, 3, 2, 2, 2] Mode: DYN_ARR Size/Cap: 1/4 [2], Frequency: 3 DYN_ARR Size/Cap: 7/8 [4, 3, 3, 2, 2, 2, 1] Mode: DYN_ARR Size/Cap: 1/4 [2], Frequency: 3 DYN_ARR Size/Cap: 8/8 [4, 3, 3, 2, 2, 2, 1, 1] Mode: DYN_ARR Size/Cap: 1/4 [2], Frequency: 3 DYN_ARR Size/Cap: 9/16 [4, 3, 3, 2, 2, 2, 1, 1, 1] Mode: DYN_ARR Size/Cap: 2/4 [2, 1], Frequency: 3 DYN_ARR Size/Cap: 10/16 [4, 3, 3, 2, 2, 2, 1, 1, 1, 1] Mode: DYN_ARR Size/Cap: 1/4 [1], Frequency: 4 Table of Contents Page 19 of 24

Part 2 – Summary and Specific Instructions

1. Implement a Bag ADT class by completing the skeleton code provided in the file bag_da.py. You will use the DynamicArray class that you implemented in Part 1 of this assignment as the underlying data storage for your Bag ADT. 2. Once completed, your implementation will include the following methods: add() remove() count() clear() equal() __iter__() __next__() 3. We will test your implementation with different types of objects, not just integers. We guarantee that all such objects will have correct implementation of methods __eq__(), __lt__(), __gt__(), __ge__(), __le__(), and __str__(). 4. The number of objects stored in the Bag at any given time will be between 0 and 1,000,000 inclusive. The bag must allow for the storage of duplicate objects.

5. RESTRICTIONS: You are NOT allowed to use ANY built-in Python data structures and/or their methods in any of your solutions. This includes built-in Python lists, dictionaries, or anything else. You must solve this portion of the assignment by importing and using objects of the DynamicArray class (that you wrote in Part 1) and using class methods to write your solution. You are also not allowed to directly access any variables of the DynamicArray class (e.g. self._size, self._capacity, and self._data). Access to DynamicArray variables must only be done by using the DynamicArray class methods. Read the Coding Guides and Tips module for a detailed description of these topics.

add(self, value: object) -> None: This method adds a new element to the bag. It must be implemented with O(1) amortized runtime complexity. Example #1: bag = Bag() print(bag) values = [10, 20, 30, 10, 20, 30] for value in values: bag.add(value) print(bag) Output: BAG: 0 elements. [] BAG: 6 elements. [10, 20, 30, 10, 20, 30] remove(self, value: object) -> bool: This method removes any one element from the bag that matches the provided value object. It returns True if some object was actually removed from the bag. Otherwise, it returns False. This method must be implemented with O(N) runtime complexity. Example #1: bag = Bag([1, 2, 3, 1, 2, 3, 1, 2, 3]) print(bag) print(bag.remove(7), bag) print(bag.remove(3), bag) print(bag.remove(3), bag) print(bag.remove(3), bag) print(bag.remove(3), bag) Output: BAG: 9 elements. [1, 2, 3, 1, 2, 3, 1, 2, 3] False BAG: 9 elements. [1, 2, 3, 1, 2, 3, 1, 2, 3] True BAG: 8 elements. [1, 2, 1, 2, 3, 1, 2, 3] True BAG: 7 elements. [1, 2, 1, 2, 1, 2, 3] True BAG: 6 elements. [1, 2, 1, 2, 1, 2] False BAG: 6 elements. [1, 2, 1, 2, 1, 2] Table of Contents Page 21 of 24 count(self, value: object) -> int: This method returns the number of elements in the bag that match the provided value object. It must be implemented with O(N) runtime complexity.

Example #1: bag = Bag([1, 2, 3, 1, 2, 2]) print(bag, bag.count(1), bag.count(2), bag.count(3), bag.count(4)) Output: BAG: 6 elements. [1, 2, 3, 1, 2, 2] 2 3 1 0 clear(self) -> None: This method clears the contents of the bag. It must be implemented with O(1) runtime complexity. Example #1: bag = Bag([1, 2, 3, 1, 2, 3]) print(bag) bag.clear() print(bag) Output: BAG: 6 elements. [1, 2, 3, 1, 2, 3] BAG: 0 elements. [] Page 22 of 24 CS261 Data Structures Assignment 2: Dynamic Array Implementation equal(self, second_bag: “Bag”) -> bool: This method compares the contents of a bag with the contents of a second bag provided as a parameter. The method returns True if the bags are equal (contain the same number of elements, and also contain the same elements without regard to the order of elements). Otherwise, it returns False. An empty bag is only considered equal to another empty bag. This method must not change the contents of either bag. You are allowed to directly access all instance variables of second_bag, but you may not create any additional data structures, nor sort either bag. The runtime complexity of this implementation should be no greater than O(N 2).

The maximum test case size for this method will be limited to bags of 1,000 items each. Example #1: bag1 = Bag([10, 20, 30, 40, 50, 60]) bag2 = Bag([60, 50, 40, 30, 20, 10]) bag3 = Bag([10, 20, 30, 40, 50]) bag_empty = Bag() print(bag1, bag2, bag3, bag_empty, sep=”\n”) print(bag1.equal(bag2), bag2.equal(bag1)) print(bag1.equal(bag3), bag3.equal(bag1)) print(bag2.equal(bag3), bag3.equal(bag2)) print(bag1.equal(bag_empty), bag_empty.equal(bag1)) print(bag_empty.equal(bag_empty)) print(bag1, bag2, bag3, bag_empty, sep=”\n”) bag1 = Bag([100, 200, 300, 200]) bag2 = Bag([100, 200, 30, 100]) print(bag1.equal(bag2)) Output: BAG: 6 elements. [10, 20, 30, 40, 50, 60] BAG: 6 elements. [60, 50, 40, 30, 20, 10] BAG: 5 elements. [10, 20, 30, 40, 50] BAG: 0 elements. [] True True False False False False False False True BAG: 6 elements. [10, 20, 30, 40, 50, 60] BAG: 6 elements. [60, 50, 40, 30, 20, 10] BAG: 5 elements. [10, 20, 30, 40, 50] BAG: 0 elements. [] False Table of Contents Page 23 of 24 __iter__(): This method enables the Bag to iterate across itself.

Implement this method in a similar way to the example in the Exploration: Encapsulation and Iterators. You ARE permitted (and will need to) initialize a variable to track the iterator’s progress through the Bag’s contents. You can use either of the two models demonstrated in the Exploration – you can build the iterator functionality inside the Bag, or you can create a separate iterator class. Example #1: bag = Bag([5, 4, -8, 7, 10]) print(bag) for item in bag: print(item) Output: BAG: 5 elements. [5, 4, -8, 7, 10] 5 4 -8 7 10 __next__(): This method will return the next item in the Bag, based on the current location of the iterator. Implement this method in a similar way to the example in the Exploration: Encapsulation and Iterators. Example #2: bag = Bag([“orange”, “apple”, “pizza”, “ice cream”]) print(bag) for item in bag: print(item) Output: BAG: 4 elements. [orange, apple, pizza, ice cream] orange apple pizza ice cream Page 24 of 24

CS261 Assignment 3: Linked List / ADT Implementation

Part 1 – Summary and Specific Instructions

1. Implement a Singly Linked List data structure by completing the skeleton code provided in the file sll.py. Once completed, your implementation will include the following methods: insert_front(), insert_back() insert_at_index(), remove_at_index() remove() count() find() slice() 2. We will test your implementation with different types of objects, not just integers. We guarantee that all such objects will have correct implementations of methods __eq__(), __lt__(), __gt__(), __ge__(), __le__(), and __str__().

3. The number of objects stored in the list at any given time will be between 0 and 900 inclusive. 4. Make sure that you include the provided SLNode class in your project. You do NOT upload this class to Gradescope. 5. The variable in the LinkedList class (_head) is marked as private, so it may only be accessed/changed directly inside the class. Variables in the SLNode class (provided in its own file, as it will also be used in Parts 4 and 5) are not marked as private.

You are allowed to access/change their values directly wherever the SLNode class is used, and are not required to write getter or setter methods for them. 6. RESTRICTIONS: You are not allowed to use ANY built-in Python data structures or their methods. 7. This implementation must be done with the use of a front sentinel node.

insert_front(self, value: object) -> None: This method adds a new node at the beginning of the list (right after the front sentinel). It must be implemented with O(1) runtime complexity. Example #1: test_case = [“A”, “B”, “C”] lst = LinkedList() for case in test_case: lst.insert_front(case) print(lst) Output: SLL [A] SLL [B -> A] SLL [C -> B -> A] insert_back(self, value: object) -> None: This method adds a new node at the end of the list. It must be implemented with O(N) runtime complexity. Example #1: test_case = [“C”, “B”, “A”] lst = LinkedList() for case in test_case: lst.insert_back(case) print(lst) Output: SLL [C] SLL [C -> B] SLL [C -> B -> A]

Implementation insert_at_index(self, index: int, value: object) -> None: This method inserts a new value at the specified index position in the linked list. Index 0 refers to the beginning of the list (right after the front sentinel). If the provided index is invalid, the method raises a custom “SLLException”. Code for the exception is provided in the skeleton file. If the linked list contains N nodes (the sentinel node is not included in this count), valid indices for this method are [0, N] inclusive. It must be implemented with O(N) runtime complexity.

Example #1: lst = LinkedList() test_cases = [(0, “A”), (0, “B”), (1, “C”), (3, “D”), (-1, “E”), (5, “F”)] for index, value in test_cases: print(“Inserted”, value, “at index”, index, “: “, end=””) try: lst.insert_at_index(index, value) print(lst) except Exception as e: print(type(e)) Output: Inserted A at index 0 : SLL [A] Inserted B at index 0 : SLL [B -> A] Inserted C at index 1 : SLL [B -> C -> A] Inserted D at index 3 : SLL [B -> C -> A -> D] Inserted E at index -1 : <class ‘__main__.SLLException’> Inserted F at index 5 : <class ‘__main__.SLLException’>

Implementation remove_at_index(self, index: int) -> None: This method removes the node at the specified index position from the linked list. Index 0 refers to the beginning of the list (right after the front sentinel). If the provided index is invalid, the method raises a custom “SLLException”. Code for the exception is provided in the skeleton file. If the list contains N elements (the sentinel node is not included in this count), valid indices for this method are [0, N – 1] inclusive.

It must be implemented with O(N) runtime complexity. Example #1: lst = LinkedList([1, 2, 3, 4, 5, 6]) print(f”Initial LinkedList : {lst}”) for index in [0, 2, 0, 2, 2, -2]: print(“Removed at index:”, index, “: “, end=””) try: lst.remove_at_index(index) print(lst) except Exception as e: print(type(e)) print(lst) Output: Initial LinkedList : SLL [1 -> 2 -> 3 -> 4 -> 5 -> 6] Removed at index 0 : SLL [2 -> 3 -> 4 -> 5 -> 6] Removed at index 2 : SLL [2 -> 3 -> 5 -> 6] Removed at index 0 : SLL [3 -> 5 -> 6] Removed at index 2 : SLL [3 -> 5] Removed at index 2 : <class ‘__main__.SLLException’> Removed at index -2 : <class ‘__main__.SLLException’>

Implementation remove(self, value: object) -> bool: This method traverses the list from the beginning to the end, and removes the first node that matches the provided “value” object. The method returns True if a node was removed from the list. Otherwise, it returns False. It must be implemented with O(N) runtime complexity. Example #1: lst = LinkedList([1, 2, 3, 1, 2, 3, 1, 2, 3]) print(f”Initial LinkedList, Length: {lst.length()}\n {lst}”) for value in [7, 3, 3, 3, 3]: print(f”remove({value}): {lst.remove(value}, Length: {lst.length()}” f”\n {lst}”) Output: Initial LinkedList, Length: 9 SLL [1 -> 2 -> 3 -> 1 -> 2 -> 3 -> 1 -> 2 -> 3] remove(7): False, Length: 9 SLL [1 -> 2 -> 3 -> 1 -> 2 -> 3 -> 1 -> 2 -> 3] remove(3): True, Length: 8 SLL [1 -> 2 -> 1 -> 2 -> 3 -> 1 -> 2 -> 3] remove(3): True, Length: 7 SLL [1 -> 2 -> 1 -> 2 -> 1 -> 2 -> 3] remove(3): True, Length: 6 SLL [1 -> 2 -> 1 -> 2 -> 1 -> 2] remove(3): False, Length: 6 SLL [1 -> 2 -> 1 -> 2 -> 1 -> 2]

Example #2: lst = LinkedList([1, 2, 3, 1, 2, 3, 1, 2, 3]) print(f”Initial LinkedList, Length: {lst.length()}\n {lst}”) for value in [1, 2, 3, 1, 2, 3, 3, 2, 1]: print(f”remove({value}): {lst.remove(value), Length: {lst.length()}” f”\n {lst}”) Output: Initial LinkedList, Length: 9 SLL [1 -> 2 -> 3 -> 1 -> 2 -> 3 -> 1 -> 2 -> 3] remove(1): True, Length: 8 SLL [2 -> 3 -> 1 -> 2 -> 3 -> 1 -> 2 -> 3] remove(2): True, Length: 7 SLL [3 -> 1 -> 2 -> 3 -> 1 -> 2 -> 3] remove(3): True, Length: 6 SLL [1 -> 2 -> 3 -> 1 -> 2 -> 3] remove(1): True, Length: 5 SLL [2 -> 3 -> 1 -> 2 -> 3] remove(2): True, Length: 4 SLL [3 -> 1 -> 2 -> 3] remove(3): True, Length: 3 SLL [1 -> 2 -> 3] remove(3): True, Length: 2 SLL [1 -> 2] remove(2): True, Length: 1 SLL [1] remove(1): True, Length: 0 SLL []

Implementation count(self, value: object) -> int: This method counts the number of elements in the list that match the provided “value” object. The method then returns this number. It must be implemented with O(N) runtime complexity. Example #1: lst = LinkedList([1, 2, 3, 1, 2, 2]) print(lst, lst.count(1), lst.count(2), lst.count(3), lst.count(4)) Output: SLL [1 -> 2 -> 3 -> 1 -> 2 -> 2] 2 3 1 0 find(self, value: object) -> bool: This method returns a Boolean value based on whether or not the provided “value” object exists in the list. It must be implemented with O(N) runtime complexity.

Example #1: lst = LinkedList([“Waldo”, “Clark Kent”, “Homer”, “Santa Claus”]) print(lst) print(lst.find(“Waldo”)) print(lst.find(“Superman”)) print(lst.find(“Santa Claus”)) Output: SLL [Waldo -> Clark Kent -> Homer -> Santa Claus] True False True Page 10 of 26 CS261 Data Structures Assignment 3: Linked List / ADT Implementation slice(self, start_index: int, size: int) -> object: This method returns a new LinkedList object that contains the requested number of nodes from the original list, starting with the node located at the requested start index.

If the original list contains N nodes, a valid start_index is in range [0, N – 1] inclusive. The original list cannot be modified. The runtime complexity of your implementation must be O(N). You are allowed to directly access the variable (_head) of LinkedList objects you create. If the provided start index is invalid, or if there are not enough nodes between the start index and the end of the list to make a slice of the requested size, this method raises a custom “SLLException”. Code for the exception is provided in the skeleton file. Example #1: lst = LinkedList([1, 2, 3, 4, 5, 6, 7, 8, 9]) ll_slice = lst.slice(1, 3) print(“Source:”, lst) print(“Start: 1 Size: 3 :”, ll_slice) ll_slice.remove_at_index(0) print(“Removed at index 0 :”, ll_slice) Output: Source: SLL [1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9] Start: 1 Size: 3 : SLL [2 -> 3 -> 4] Removed at index 0 : SLL [3 -> 4]

Example #2: lst = LinkedList([10, 11, 12, 13, 14, 15, 16]) print(“Source:”, lst) slices = [(0, 7), (-1, 7), (0, 8), (2, 3), (5, 0), (5, 3), (6, 1)] for index, size in slices: print(“Start:”, index, “Size:”, size, end=””) try: print(” :”, lst.slice(index, size)) except: print(” : exception occurred.”) Output: Source: SLL [10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16] Start: 0 Size: 7 : SLL [10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16] Start: -1 Size: 7 : exception occurred. Start: 0 Size: 8 : exception occurred. Start: 2 Size: 3 : SLL [12 -> 13 -> 14] Start: 5 Size: 0 : SLL [] Start: 5 Size: 3 : exception occurred. Start: 6 Size: 1 : SLL [16]

Part 2 – Summary and Specific Instructions

1. Implement a Stack ADT class by completing the provided skeleton code in the file stack_da.py. You will use the Dynamic Array data structure that you implemented in Assignment 2 as the underlying storage for your Stack ADT.

2. Your Stack ADT implementation will include the following standard Stack methods: push() pop() top() 3. We will test your implementation with different types of objects, not just integers. We guarantee that all such objects will have correct implementations of methods __eq__(), __lt__(), __gt__(), __ge__(), __le__(), and __str__(). 4. The number of objects stored in the Stack at any given time will be between 0 and 1,000,000 inclusive.

The stack must allow for the storage of duplicate objects. 5. RESTRICTIONS: You are not allowed to use ANY built-in Python data structures and/or their methods. You must solve this portion of the assignment by importing the DynamicArray class that you wrote in Assignment 2, and using class methods to write your solution. You are also not allowed to directly access any variables of the DynamicArray class (self._da._size, self._da._capacity, and self._da._data). All work must be done by only using class methods.

push(self, value: object) -> None: This method adds a new element to the top of the stack. It must be implemented with O(1) amortized runtime complexity. Example #1: s = Stack() print(s) for value in [1, 2, 3, 4, 5]: s.push(value) print(s) Output: STACK: 0 elements. [] STACK: 5 elements. [1, 2, 3, 4, 5] pop(self) -> object: This method removes the top element from the stack and returns its value. It must be implemented with O(1) amortized runtime complexity. If the stack is empty, the method raises a custom “StackException”. Code for the exception is provided in the skeleton file. Example #1: s = Stack() try: print(s.pop()) except Exception as e: print(“Exception:”, type(e)) for value in [1, 2, 3, 4, 5]: s.push(value) for i in range(6): try: print(s.pop()) except Exception as e: print(“Exception:”, type(e)) Output: Exception: <class ‘__main__.StackException’> 5 4 3 2 1 Exception: <class ‘__main__.StackException’>

top(self) -> object: This method returns the value of the top element of the stack without removing it. It must be implemented with O(1) runtime complexity. If the stack is empty, the method raises a custom “StackException”. Code for the exception is provided in the skeleton file. Example #1: s = Stack() try: s.top() except Exception as e: print(“No elements in stack”, type(e)) s.push(10) s.push(20) print(s) print(s.top()) print(s.top()) print(s) Output: No elements in stack <class ‘__main__.StackException’> STACK: 2 elements. [10, 20] 20 20 STACK: 2 elements. [10, 20]

Part 3 – Summary and Specific Instructions

1. Implement a Queue ADT class that utilizes a circular buffer (as described in the Exploration) by completing the provided skeleton code in the file queue_sa.py. You will use the Static Array data structure from previous assignments as the underlying storage for your Queue ADT. 2. Once completed, your implementation will include the following methods: enqueue() dequeue() front() The following private helper method in the skeleton code is used by __str__() to handle the “wraparound” in the circular buffer.

You may find it helpful for your methods: _increment() There is also a suggested (optional and private) helper method in the skeleton code that you may wish to implement, to assist with resizing: _double_queue() 3. We will test your implementation with different types of objects, not just integers. We guarantee that all such objects will have correct implementations of methods __eq__(), __lt__(), __gt__(), __ge__(), __le__(), and __str__(). 4. The number of objects stored in the queue at any given time will be between 0 and 1,000,000 inclusive.

The queue must allow for the storage of duplicate elements. 5. RESTRICTIONS: You are not allowed to use ANY built-in Python data structures and/or their methods. You must solve this portion of the assignment by importing the StaticArray class provided in Assignment 1, and using class methods to write your solution. You are also not allowed to directly access any variables of the StaticArray class (self._sa._size and self._sa._data). All work must be done by only using class methods.

enqueue(self, value: object) -> None: This method adds a new value to the end of the queue. It must be implemented with O(1) amortized runtime complexity. Example #1: q = Queue() print(q) for value in [1, 2, 3, 4, 5]: q.enqueue(value) print(q) Output: QUEUE: 0 elements. [] QUEUE: 5 elements. [1, 2, 3, 4, 5]

dequeue(self) -> object: This method removes and returns the value at the beginning of the queue. It must be implemented with O(1) runtime complexity. If the queue is empty, the method raises a custom “QueueException”. Code for the exception is provided in the skeleton file. Example #1: q = Queue() for value in [1, 2, 3, 4, 5]: q.enqueue(value) print(q) for i in range(q.size() + 1): try: print(q.dequeue()) except Exception as e: print(“No elements in queue”, type(e)) for value in [6, 7, 8, 111, 222, 3333, 4444]: q.enqueue(value) print(q) q.print_underlying_sa() Output: QUEUE: 5 elements. [1, 2, 3, 4, 5] 1 2 3 4 5 No elements in queue <class ‘__main__.QueueException’> QUEUE: 7 element(s). [6, 7, 8, 111, 222, 3333, 4444] STAT_ARR Size: 8 [111, 222, 3333, 4444, 5, 6, 7, 8]

front(self) -> object: This method returns the value of the front element of the queue without removing it. It must be implemented with O(1) runtime complexity. If the queue is empty, the method raises a custom “QueueException”. Code for the exception is provided in the skeleton file. NOTE: The circular buffer tests utilize the action_and_print() function to perform various operations and display the results.

You are encouraged to review this function’s code in the starter file to get a feel for how it works. For an explanation of circular buffers, please read Exploration: Queues. Example #1: q = Queue() print(q) for value in [‘A’, ‘B’, ‘C’, ‘D’]: try: print(q.front()) except Exception as e: print(“No elements in queue”, type(e)) q.enqueue(value) print(q) Output: QUEUE: 0 elements. [] No elements in queue <class ‘__main__.QueueException’> A A A QUEUE: 4 elements. [A, B, C, D] Testing for Circular Buffer print(“\n Circular buffer tests: #\n”) q = Queue() print(“# Enqueue: 2, 4, 6, 8”) test_case = [2, 4, 6, 8] for value in test_case: q.enqueue(value) print(q) q.print_underyling_sa() print()

Output: # Enqueue: 2, 4, 6, 8 QUEUE: 4 element(s). [2, 4, 6, 8] STAT_ARR Size: 4 [2, 4, 6, 8] action_and_print(“# Dequeue a value”, q.dequeue, [], q) Output: # Dequeue a value QUEUE: 3 element(s). [4, 6, 8] STAT_ARR Size: 4 [2, 4, 6, 8] action_and_print(“# Enqueue: 10”, q.enqueue, [10], q) Output: # Enqueue: 10 QUEUE: 4 element(s). [4, 6, 8, 10] STAT_ARR Size: 4 [10, 4, 6, 8] action_and_print(“# Enqueue: 12”, q.enqueue, [12], q) Output: # Enqueue: 12 QUEUE: 5 element(s). [4, 6, 8, 10, 12] STAT_ARR Size: 8 [4, 6, 8, 10, 12, None, None, None] print(“# Dequeue until empty”) while not q.is_empty(): q.dequeue print(q) q.print_underlying_sa() print() Output: # Dequeue until empty QUEUE: 0 element(s).

[] STAT_ARR Size: 8 [4, 6, 8, 10, 12, None, None, None]

action_and_print(“# Enqueue: 14, 16, 18”, q.enqueue, [14, 16, 18], q) Output: # Enqueue: 14, 16, 18 QUEUE: 3 element(s). [14, 16, 18] STAT_ARR Size: 8 [4, 6, 8, 10, 12, 14, 16, 18] action_and_print(“# Enqueue: 20”, q.enqueue, [20], q) Output: # Enqueue: 20 QUEUE: 4 element(s). [14, 16, 18, 20] STAT_ARR Size: 8 [20, 6, 8, 10, 12, 14, 16, 18] action_and_print(“# Enqueue: 22, 24, 26, 28”, q.enqueue, [22, 24, 26, 28], q) Output: # Enqueue: 22, 24, 26, 28 QUEUE: 8 element(s). [14, 16, 18, 20, 22, 24, 26, 28] STAT_ARR Size: 8 [20, 22, 24, 26, 28, 14, 16, 18] action_and_print(“# Enqueue: 30”, q.enqueue, [30], q) Output: # Enqueue: 30 QUEUE: 9 element(s). [14, 16, 18, 20, 22, 24, 26, 28, 30] STAT_ARR Size: 16 [14, 16, 18, 20, 22, 24, 26, 28, 30, None, None, None, None, None, None, None]

Part 4 – Summary and Specific Instructions

1. Implement a Stack ADT class by completing the provided skeleton code in the file stack_sll.py. You will use a chain of Singly-Linked Nodes (the provided SLNode) as the underlying storage for your Stack ADT. Be sure to review the Exploration on Stacks for an example.

4. The number of objects stored in the Stack at any given time will be between 0 and 1,000,000 inclusive. The stack must allow for the storage of duplicate objects. 5. RESTRICTIONS: You are not allowed to use ANY built-in Python data structures and/or their methods.

You must solve this portion of the assignment by using the SLNode class provided with this assignment.

push(self, value: object) -> None: This method adds a new element to the top of the stack. It must be implemented with O(1) runtime complexity. Example #1: s = Stack() print(s) for value in [1, 2, 3, 4, 5]: s.push(value) print(s) Output: STACK [] STACK [5 -> 4 -> 3 -> 2 -> 1] pop(self) -> object: This method removes the top element from the stack and returns its value. It must be implemented with O(1) runtime complexity.

If the stack is empty, the method raises a custom “StackException”. Code for the exception is provided in the skeleton file. Example #1: s = Stack() try: print(s.pop()) except Exception as e: print(“Exception:”, type(e)) for value in [1, 2, 3, 4, 5]: s.push(value) for i in range(6): try: print(s.pop()) except Exception as e: print(“Exception:”, type(e)) Output: Exception: <class ‘__main__.StackException’> 5 4 3 2 1 Exception: <class ‘__main__.StackException’>

Part 5 – Summary and Specific Instructions

1. Implement a Queue ADT class by completing the provided skeleton code in the file queue_sll.py. You will use a chain of Singly-Linked Nodes (the provided SLNode) as the underlying storage for your Queue ADT. Be sure to review the Exploration on Queues for an example.

2. Once completed, your implementation will include the following methods: enqueue() dequeue() front() 3. We will test your implementation with different types of objects, not just integers. We guarantee that all such objects will have correct implementations of methods __eq__(), __lt__(), __gt__(), __ge__(), __le__(), and __str__(). 4. The number of objects stored in the queue at any given time will be between 0 and 1,000,000 inclusive.

enqueue(self, value: object) -> None: This method adds a new value to the end of the queue. It must be implemented with O(1) runtime complexity. Example #1: q = Queue() print(q) for value in [1, 2, 3, 4, 5]: q.enqueue(value)m print(q) Output: QUEUE [] QUEUE [1 -> 2 -> 3 -> 4 -> 5] dequeue(self) -> object: This method removes and returns the value from the beginning of the queue. It must be implemented with O(1) runtime complexity.

If the queue is empty, the method raises a custom “QueueException”. Code for the exception is provided in the skeleton file. Example #1: q = Queue() for value in [1, 2, 3, 4, 5]: q.enqueue(value) print(q) for i in range(6): try: print(q.dequeue()) except Exception as e: print(“No elements in queue”, type(e)) Output: QUEUE [1 -> 2 -> 3 -> 4 -> 5] 1 2 3 4 5 No elements in queue <class ‘__main__.QueueException’>

front(self) -> object: This method returns the value of the front element of the queue without removing it. It must be implemented with O(1) runtime complexity. If the queue is empty, the method raises a custom “QueueException”. Code for the exception is provided in the skeleton file. Example #1: q = Queue() print(q) for value in [‘A’, ‘B’, ‘C’, ‘D’]: try: print(q.front()) except Exception as e: print(“No elements in queue”, type(e)) q.enqueue(value) print(q) Output: QUEUE [] No elements in queue <class ‘__main__.QueueException’> A A A QUEUE [A -> B -> C -> D]

CS261 Assignment 4 BST/AVL Tree Implementation

Part 1 – Summary and Specific Instructions

1. Implement the BST class by completing the provided skeleton code in the file
bst.py. Once completed, your implementation will include the following methods:
add(), remove()
contains(), inorder_traversal()
find_min(), find_max()
is_empty(), make_empty()

2. The BST class is constructed using instances of the provided BSTNode class.
3. We will test your implementation with different types of objects, not just integers.
We guarantee that all such objects will have correct implementation of methods
__eq__(), __lt__(), __gt__(), __ge__(), __le__(), and __str__().

4. The number of objects stored in the tree will be between 0 and 900 inclusive.
5. When removing a node with two subtrees, replace it with the leftmost child
of the right subtree (i.e. the inorder successor). You do not need to recursively
continue this process. If the deleted node only has one subtree (either right or left),
replace the deleted node with the root node of that subtree.

6. The variables in BSTNode are not private. You are allowed to access and change
their values directly. You do not need to write any getter or setter methods for them.

7. RESTRICTIONS: You are NOT allowed to use ANY built-in Python data structures
and/or their methods. In case you need ‘helper’ data structures in your solution, the
skeleton code includes prewritten implementations of Queue and Stack classes,
which are in separate files and imported in bst.py and avl.py. You are allowed to
create and use objects from those classes in your implementation.
You are NOT allowed to directly access any variables of the Queue or Stack classes.
All work must be done only by using class methods.

8. Ensure that your methods meet the specified runtime requirements.

add(self, value: object) -> None:
This method adds a new value to the tree. Duplicate values are allowed. If a node with
that value is already in the tree, the new value should be added to the right
subtree of that node. It must be implemented with O(N) runtime complexity.
Example #1:
test_cases = (
(1, 2, 3),
(3, 2, 1),
(1, 3, 2),
(3, 1, 2),
)
for case in test_cases:
tree = BST(case)
print(tree)
Output:
BST pre-order { 1, 2, 3 }
BST pre-order { 3, 2, 1 }
BST pre-order { 1, 3, 2 }
BST pre-order { 3, 1, 2 }

Example #2:
test_cases = (
(10, 20, 30, 40, 50),
(10, 20, 30, 50, 40),
(30, 20, 10, 5, 1),
(30, 20, 10, 1, 5),
(5, 4, 6, 3, 7, 2, 8),
(range(0, 30, 3)),
(range(0, 31, 3)),
(range(0, 34, 3)),
(range(10, -10, -2)),
(‘A’, ‘B’, ‘C’, ‘D’, ‘E’),
(1, 1, 1, 1),
)
for case in test_cases:
tree = BST(case)
print(‘INPUT :’, case)
print(‘RESULT :’, tree)

Output:
INPUT : (10, 20, 30, 40, 50)
RESULT : BST pre-order { 10, 20, 30, 40, 50 }
INPUT : (10, 20, 30, 50, 40)
RESULT : BST pre-order { 10, 20, 30, 50, 40 }
INPUT : (30, 20, 10, 5, 1)
RESULT : BST pre-order { 30, 20, 10, 5, 1 }
INPUT : (30, 20, 10, 1, 5)
RESULT : BST pre-order { 30, 20, 10, 1, 5 }
INPUT : (5, 4, 6, 3, 7, 2, 8)
RESULT : BST pre-order { 5, 4, 3, 2, 6, 7, 8 }
INPUT : range(0, 30, 3)
RESULT : BST pre-order { 0, 3, 6, 9, 12, 15, 18, 21, 24, 27 }
INPUT : range(0, 31, 3)
RESULT : BST pre-order { 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30 }
INPUT : range(0, 34, 3)
RESULT : BST pre-order { 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33 }
INPUT : range(10, -10, -2)
RESULT : BST pre-order { 10, 8, 6, 4, 2, 0, -2, -4, -6, -8 }
INPUT : (‘A’, ‘B’, ‘C’, ‘D’, ‘E’)
RESULT : BST pre-order { A, B, C, D, E }
INPUT : (1, 1, 1, 1)
RESULT : BST pre-order { 1, 1, 1, 1 }

n
Example #3:
for _ in range(100):
case = list(set(random.randrange(1, 20000) for _ in range(900)))
tree = BST()
for value in case:
bst.add(value)
if not tree.is_valid_bst():
Raise Exception(“PROBLEM WITH ADD OPERATION”)
print(‘add() stress test finished’)
Output:
add() stress test finished

remove(self, value: object) -> bool:
This method removes a value from the tree. The method returns True if the value is
removed. Otherwise, it returns False. It must be implemented with O(N) runtime
complexity.
NOTE: See ‘Specific Instructions’ for an explanation of which node replaces the deleted
node.
Example #1:
test_cases = (
((1, 2, 3), 1),
((1, 2, 3), 2),
((1, 2, 3), 3),
((50, 40, 60, 30, 70, 20, 80, 45), 0),
((50, 40, 60, 30, 70, 20, 80, 45), 45),
((50, 40, 60, 30, 70, 20, 80, 45), 40),
((50, 40, 60, 30, 70, 20, 80, 45), 30),
)
for case, del_value in test_cases:
tree = BST(case)
print(‘INPUT :’, tree, “DELETE:”, del_value)
tree.remove(del_value)
print(‘RESULT :’, tree)

Output:
INPUT : BST pre-order { 1, 2, 3 } DEL: 1
RESULT : BST pre-order { 2, 3 }
INPUT : BST pre-order { 1, 2, 3 } DEL: 2
RESULT : BST pre-order { 1, 3 }
INPUT : BST pre-order { 1, 2, 3 } DEL: 3
RESULT : BST pre-order { 1, 2 }
INPUT : BST pre-order { 50, 40, 30, 20, 45, 60, 70, 80 } DEL: 0
RESULT : BST pre-order { 50, 40, 30, 20, 45, 60, 70, 80 }
INPUT : BST pre-order { 50, 40, 30, 20, 45, 60, 70, 80 } DEL: 45
RESULT : BST pre-order { 50, 40, 30, 20, 60, 70, 80 }
INPUT : BST pre-order { 50, 40, 30, 20, 45, 60, 70, 80 } DEL: 40
RESULT : BST pre-order { 50, 45, 30, 20, 60, 70, 80 }
INPUT : BST pre-order { 50, 40, 30, 20, 45, 60, 70, 80 } DEL: 30
RESULT : BST pre-order { 50, 40, 20, 45, 60, 70, 80 }

Example #2:
test_cases = (
((50, 40, 60, 30, 70, 20, 80, 45), 20),
((50, 40, 60, 30, 70, 20, 80, 15), 40),
((50, 40, 60, 30, 70, 20, 80, 35), 20),
((50, 40, 60, 30, 70, 20, 80, 25), 40),
)
for case, del_value in test_cases:
tree= BST(tree)
print(‘INPUT :’, tree, “DELETE:”, del_value)
tree.remove(del_value)
print(‘RESULT :’, tree)

Output:
INPUT : BST pre-order { 50, 40, 30, 20, 45, 60, 70, 80 } DEL: 20
RESULT : BST pre-order { 50, 40, 30, 45, 60, 70, 80 }
INPUT : BST pre-order { 50, 40, 30, 20, 15, 60, 70, 80 } DEL: 40
RESULT : BST pre-order { 50, 30, 20, 15, 60, 70, 80 }
INPUT : BST pre-order { 50, 40, 30, 20, 35, 60, 70, 80 } DEL: 20
RESULT : BST pre-order { 50, 40, 30, 35, 60, 70, 80 }
INPUT : BST pre-order { 50, 40, 30, 20, 25, 60, 70, 80 } DEL: 40
RESULT : BST pre-order { 50, 30, 20, 25, 60, 70, 80 }

Example #3:
case = range(-9, 16, 2)
tree = BST(case)
for del_value in case:
print(‘INPUT :’, tree, del_value)
tree.remove(del_value)
print(‘RESULT :’, tree)

Output:
INPUT : BST pre-order { -9, -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15 } -9
RESULT : BST pre-order { -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15 }
INPUT : BST pre-order { -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15 } -7
RESULT : BST pre-order { -5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15 }
INPUT : BST pre-order { -5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15 } -5
RESULT : BST pre-order { -3, -1, 1, 3, 5, 7, 9, 11, 13, 15 }
INPUT : BST pre-order { -3, -1, 1, 3, 5, 7, 9, 11, 13, 15 } -3
RESULT : BST pre-order { -1, 1, 3, 5, 7, 9, 11, 13, 15 }
INPUT : BST pre-order { -1, 1, 3, 5, 7, 9, 11, 13, 15 } -1
RESULT : BST pre-order { 1, 3, 5, 7, 9, 11, 13, 15 }
INPUT : BST pre-order { 1, 3, 5, 7, 9, 11, 13, 15 } 1
RESULT : BST pre-order { 3, 5, 7, 9, 11, 13, 15 }
INPUT : BST pre-order { 3, 5, 7, 9, 11, 13, 15 } 3
RESULT : BST pre-order { 5, 7, 9, 11, 13, 15 }
INPUT : BST pre-order { 5, 7, 9, 11, 13, 15 } 5
RESULT : BST pre-order { 7, 9, 11, 13, 15 }
INPUT : BST pre-order { 7, 9, 11, 13, 15 } 7
RESULT : BST pre-order { 9, 11, 13, 15 }
INPUT : BST pre-order { 9, 11, 13, 15 } 9
RESULT : BST pre-order { 11, 13, 15 }
INPUT : BST pre-order { 11, 13, 15 } 11
RESULT : BST pre-order { 13, 15 }
INPUT : BST pre-order { 13, 15 } 13
RESULT : BST pre-order { 15 }
INPUT : BST pre-order { 15 } 15
RESULT : BST pre-order { }

Example #4:
case = range(0, 34, 3)
tree = BST(case)
for _ in case[:-2]:
root_value = tree.get_root().value
print(‘INPUT :’, tree, root_value)
tree.remove(root_value)
if not tree.is_valid_bst():
raise Exception(“PROBLEM WITH REMOVE OPERATION”)
print(‘RESULT :’, tree)

Output:
INPUT : BST pre-order { 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33 } 0
RESULT : BST pre-order { 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33 }
INPUT : BST pre-order { 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33 } 3
RESULT : BST pre-order { 6, 9, 12, 15, 18, 21, 24, 27, 30, 33 }
INPUT : BST pre-order { 6, 9, 12, 15, 18, 21, 24, 27, 30, 33 } 6
RESULT : BST pre-order { 9, 12, 15, 18, 21, 24, 27, 30, 33 }
INPUT : BST pre-order { 9, 12, 15, 18, 21, 24, 27, 30, 33 } 9
RESULT : BST pre-order { 12, 15, 18, 21, 24, 27, 30, 33 }
INPUT : BST pre-order { 12, 15, 18, 21, 24, 27, 30, 33 } 12
RESULT : BST pre-order { 15, 18, 21, 24, 27, 30, 33 }
INPUT : BST pre-order { 15, 18, 21, 24, 27, 30, 33 } 15
RESULT : BST pre-order { 18, 21, 24, 27, 30, 33 }
INPUT : BST pre-order { 18, 21, 24, 27, 30, 33 } 18
RESULT : BST pre-order { 21, 24, 27, 30, 33 }
INPUT : BST pre-order { 21, 24, 27, 30, 33 } 21
RESULT : BST pre-order { 24, 27, 30, 33 }
INPUT : BST pre-order { 24, 27, 30, 33 } 24
RESULT : BST pre-order { 27, 30, 33 }
INPUT : BST pre-order { 27, 30, 33 } 27
RESULT : BST pre-order { 30, 33 }

contains(self, value: object) -> bool:
This method returns True if the value is in the tree. Otherwise, it returns False. If the tree is
empty, the method should return False. It must be implemented with O(N) runtime
complexity.
Example #1:
tree = BST([10, 5, 15])
print(tree.contains(15))
print(tree.contains(-10))
print(tree.contains(15))
Output:
True
False
True
Example #2:
tree = BST()
print(tree.contains(0))
Output:
False

inorder_traversal(self) -> Queue:
This method will perform an inorder traversal of the tree, and return a Queue object that
contains the values of the visited nodes, in the order they were visited. If the tree is empty,
the method returns an empty Queue. It must be implemented with O(N) runtime
complexity.

Example #1:
tree = BST([10, 20, 5, 15, 17, 7, 12])
print(tree.inorder_traversal())
Output:
QUEUE { 5, 7, 10, 12, 15, 17, 20 }
Example #2:
tree = BST([8, 10, -4, 5, -1])
print(tree.inorder_traversal())
Output:
QUEUE { -4, -1, 5, 8, 10 }

find_min(self) -> object:
This method returns the lowest value in the tree. If the tree is empty, the method should
return None. It must be implemented with O(N) runtime complexity.
Example #1:
tree = BST([10, 20, 5, 15, 17, 7, 12])
print(tree.find_min())
Output:
5
Example #2:
tree = BST([8, 10, -4, 5, -1])
print(tree.find_min())
Output:
-4
find_max(self) -> object:

This method returns the highest value in the tree. If the tree is empty, the method should
return None. It must be implemented with O(N) runtime complexity.
Example #1:
tree = BST([10, 20, 5, 15, 17, 7, 12])
print(tree.find_max())
Output:
20
Example #2:
tree = BST([8, 10, -4, 5, -1])
print(tree.find_max())
Output:
10

is_empty(self) -> bool:
This method returns True if the tree is empty. Otherwise, it returns False. It must be
implemented with O(1) runtime complexity.
Example #1:
tree = BST([10, 20, 5, 15, 17, 7, 12])
print(tree.is_empty())
Output:
False
Example #2:
tree = BST()
print(tree.is_empty())
Output:
True
make_empty(self) -> None:
This method removes all of the nodes from the tree. It must be implemented with O(1)
runtime complexity.

Example #1:
tree = BST([10, 20, 5, 15, 17, 7, 12])
tree.make_empty())
print(tree)
Output:
AVL pre-order { }
Example #2:
tree = BST()
tree.make_empty())
print(tree)
Output:
AVL pre-order { }

Part 2 – Summary and Specific Instructions

1. Implement the AVL class (a subclass of BST) by completing the provided skeleton
code in the file avl.py.
Once completed, your implementation will include overridden versions of the
following methods:
add(), remove()
And it will inherit the following methods from BST:
contains(), inorder_traversal(), find_min(), find_max()
is_empty(), make_empty()

2. When reviewing the provided skeleton code, please note that the AVLNode class (a
subclass of BSTNode) has two important added attributes: parent (to store a pointer
to the parent of the current node) and height (to store the height of the subtree
rooted at the current node). Your implementation must correctly maintain all three
node pointers (left, right, and parent), as well as the height attribute of each
node. Your tree must use the AVLNode class.

3. We will test your implementation with different types of objects, not just integers.
We guarantee that all such objects will have correct implementation of methods
__eq__(), __lt__(), __gt__(), __ge__(), __le__(), and __str__().

6. The variables in AVLNode are not private. You are allowed to access and change
their values directly. You do not need to write any getter or setter methods for them.
The AVL skeleton code includes some suggested helper methods.

7. RESTRICTIONS: You are not allowed to use ANY built-in Python data structures
and/or their methods. In case you need ‘helper’ data structures in your solution, the
skeleton code includes prewritten implementations of Queue and Stack classes,
which are in separate files and imported in bst.py and avl.py.

You are allowed to
create and use objects from those classes in your implementation.
You are not allowed to directly access any variables of the Queue or Stack classes. All
work must be done only by using class methods.

8. Ensure that your methods meet the specified runtime requirements.
add(self, value: object) -> None:
This method adds a new value to the tree while maintaining its AVL property. Duplicate
values are not allowed. If the value is already in the tree, the method should not change
the tree. It must be implemented with O(log N) runtime complexity.

Example #1:
test_cases = (
(1, 2, 3), #RR
(3, 2, 1), #LL
(1, 3, 2), #RL
(3, 1, 2), #LR
)
for case in test_cases:
tree = AVL(case)
print(tree)
Output:
AVL pre-order { 2, 1, 3 }
AVL pre-order { 2, 1, 3 }
AVL pre-order { 2, 1, 3 }
AVL pre-order { 2, 1, 3 }

Example #2:
test_cases = (
(10, 20, 30, 40, 50), # RR, RR
(10, 20, 30, 50, 40), # RR, RL
(30, 20, 10, 5, 1), # LL, LL
(30, 20, 10, 1, 5), # LL, LR
(5, 4, 6, 3, 7, 2, 8), # LL, RR
(range(0, 30, 3)),
(range(0, 31, 3)),
(range(0, 34, 3)),
(range(10, -10, -2)),
(‘A’, ‘B’, ‘C’, ‘D’, ‘E’),
(1, 1, 1, 1),
)

for case in test_cases:
tree = AVL(case)
print(‘INPUT :’, case)
print(‘RESULT :’, tree)
Output:
INPUT : (10, 20, 30, 40, 50)
RESULT : AVL pre-order { 20, 10, 40, 30, 50 }
INPUT : (10, 20, 30, 50, 40)
RESULT : AVL pre-order { 20, 10, 40, 30, 50 }
INPUT : (30, 20, 10, 5, 1)
RESULT : AVL pre-order { 20, 5, 1, 10, 30 }
INPUT : (30, 20, 10, 1, 5)
RESULT : AVL pre-order { 20, 5, 1, 10, 30 }
INPUT : (5, 4, 6, 3, 7, 2, 8)
RESULT : AVL pre-order { 5, 3, 2, 4, 7, 6, 8 }
INPUT : range(0, 30, 3)
RESULT : AVL pre-order { 9, 3, 0, 6, 21, 15, 12, 18, 24, 27 }
INPUT : range(0, 31, 3)
RESULT : AVL pre-order { 9, 3, 0, 6, 21, 15, 12, 18, 27, 24, 30 }
INPUT : range(0, 34, 3)
RESULT : AVL pre-order { 21, 9, 3, 0, 6, 15, 12, 18, 27, 24, 30, 33 }
INPUT : range(10, -10, -2)
RESULT : AVL pre-order { 4, -4, -6, -8, 0, -2, 2, 8, 6, 10 }
INPUT : (‘A’, ‘B’, ‘C’, ‘D’, ‘E’)
RESULT : AVL pre-order { B, A, D, C, E }
INPUT : (1, 1, 1, 1)
RESULT : AVL pre-order { 1 }

Example #3:
for _ in range(100):
case = list(set(random.randrange(1, 20000) for _ in range(900)))
tree = AVL()
for value in case:
tree.add(value)
if not tree.is_valid_avl():
raise Exception(“PROBLEM WITH ADD OPERATION”)
print(‘add() stress test finished’)
Output:
add() stress test finished

remove(self, value: object) -> bool:
This method removes the value from the AVL tree. The method returns True if the value is
removed. Otherwise, it returns False. It must be implemented with O(log N) runtime
complexity.

NOTE: See ‘Specific Instructions’ for an explanation of which node replaces the deleted
node.
Example #1:
test_cases = (
((1, 2, 3), 1), # no AVL rotation
((1, 2, 3), 2), # no AVL rotation
((1, 2, 3), 3), # no AVL rotation
((50, 40, 60, 30, 70, 20, 80, 45), 0),
((50, 40, 60, 30, 70, 20, 80, 45), 45), # no AVL rotation
((50, 40, 60, 30, 70, 20, 80, 45), 40), # no AVL rotation
((50, 40, 60, 30, 70, 20, 80, 45), 30), # no AVL rotation
)
for case, del_value in test_cases:
tree = AVL(case)
print(‘INPUT :’, tree, “DELETE:”, del_value)
tree.remove(del_value)
print(‘RESULT :’, tree)
Output:
INPUT : AVL pre-order { 2, 1, 3 } DEL: 1
RESULT : AVL pre-order { 2, 3 }
INPUT : AVL pre-order { 2, 1, 3 } DEL: 2
RESULT : AVL pre-order { 3, 1 }
INPUT : AVL pre-order { 2, 1, 3 } DEL: 3
RESULT : AVL pre-order { 2, 1 }
INPUT : AVL pre-order { 50, 30, 20, 40, 45, 70, 60, 80 } DEL: 0
RESULT : AVL pre-order { 50, 30, 20, 40, 45, 70, 60, 80 }
INPUT : AVL pre-order { 50, 30, 20, 40, 45, 70, 60, 80 } DEL: 45
RESULT : AVL pre-order { 50, 30, 20, 40, 70, 60, 80 }
INPUT : AVL pre-order { 50, 30, 20, 40, 45, 70, 60, 80 } DEL: 40
RESULT : AVL pre-order { 50, 30, 20, 45, 70, 60, 80 }
INPUT : AVL pre-order { 50, 30, 20, 40, 45, 70, 60, 80 } DEL: 30
RESULT : AVL pre-order { 50, 40, 20, 45, 70, 60, 80 }

Example #2:
test_cases = (
((50, 40, 60, 30, 70, 20, 80, 45), 20), # RR
((50, 40, 60, 30, 70, 20, 80, 15), 40), # LL
((50, 40, 60, 30, 70, 20, 80, 35), 20), # RL
((50, 40, 60, 30, 70, 20, 80, 25), 40), # LR
)
for case, del_value in test_cases:
tree = AVL(case)
print(‘INPUT :’, tree, “DELETE:”, del_value)
tree.remove(del_value)
print(‘RESULT :’, tree)
Output:
INPUT : AVL pre-order { 50, 30, 20, 40, 45, 70, 60, 80 } DEL: 20
RESULT : AVL pre-order { 50, 40, 30, 45, 70, 60, 80 }
INPUT : AVL pre-order { 50, 30, 20, 15, 40, 70, 60, 80 } DEL: 40
RESULT : AVL pre-order { 50, 20, 15, 30, 70, 60, 80 }
INPUT : AVL pre-order { 50, 30, 20, 40, 35, 70, 60, 80 } DEL: 20
RESULT : AVL pre-order { 50, 35, 30, 40, 70, 60, 80 }
INPUT : AVL pre-order { 50, 30, 20, 25, 40, 70, 60, 80 } DEL: 40
RESULT : AVL pre-order { 50, 25, 20, 30, 70, 60, 80 }

Example #3:
case = range(-9, 16, 2)
tree = AVL(case)
for del_value in case:
print(‘INPUT :’, tree, del_value)
tree.remove(del_value)
print(‘RESULT :’, tree)

Output:
INPUT : AVL pre-order { 5, -3, -7, -9, -5, 1, -1, 3, 9, 7, 13, 11, 15 } -9
RESULT : AVL pre-order { 5, -3, -7, -5, 1, -1, 3, 9, 7, 13, 11, 15 }
INPUT : AVL pre-order { 5, -3, -7, -5, 1, -1, 3, 9, 7, 13, 11, 15 } -7
RESULT : AVL pre-order { 5, -3, -5, 1, -1, 3, 9, 7, 13, 11, 15 }
INPUT : AVL pre-order { 5, -3, -5, 1, -1, 3, 9, 7, 13, 11, 15 } -5
RESULT : AVL pre-order { 5, 1, -3, -1, 3, 9, 7, 13, 11, 15 }
INPUT : AVL pre-order { 5, 1, -3, -1, 3, 9, 7, 13, 11, 15 } -3
RESULT : AVL pre-order { 5, 1, -1, 3, 9, 7, 13, 11, 15 }
INPUT : AVL pre-order { 5, 1, -1, 3, 9, 7, 13, 11, 15 } -1
RESULT : AVL pre-order { 5, 1, 3, 9, 7, 13, 11, 15 }
INPUT : AVL pre-order { 5, 1, 3, 9, 7, 13, 11, 15 } 1
RESULT : AVL pre-order { 9, 5, 3, 7, 13, 11, 15 }
INPUT : AVL pre-order { 9, 5, 3, 7, 13, 11, 15 } 3
RESULT : AVL pre-order { 9, 5, 7, 13, 11, 15 }
INPUT : AVL pre-order { 9, 5, 7, 13, 11, 15 } 5
RESULT : AVL pre-order { 9, 7, 13, 11, 15 }
INPUT : AVL pre-order { 9, 7, 13, 11, 15 } 7
RESULT : AVL pre-order { 13, 9, 11, 15 }
INPUT : AVL pre-order { 13, 9, 11, 15 } 9
RESULT : AVL pre-order { 13, 11, 15 }
INPUT : AVL pre-order { 13, 11, 15 } 11
RESULT : AVL pre-order { 13, 15 }
INPUT : AVL pre-order { 13, 15 } 13
RESULT : AVL pre-order { 15 }
INPUT : AVL pre-order { 15 } 15
RESULT : AVL pre-order { }

Example #4:
case = range(0, 34, 3)
tree = AVL(case)
for _ in case[:-2]:
root_value = tree.get_root().value
print(‘INPUT :’, tree, root_value)
tree.remove(root_value)
print(‘RESULT :’, tree)

Output:
INPUT : AVL pre-order { 21, 9, 3, 0, 6, 15, 12, 18, 27, 24, 30, 33 } 21
RESULT : AVL pre-order { 24, 9, 3, 0, 6, 15, 12, 18, 30, 27, 33 }
INPUT : AVL pre-order { 24, 9, 3, 0, 6, 15, 12, 18, 30, 27, 33 } 24
RESULT : AVL pre-order { 27, 9, 3, 0, 6, 15, 12, 18, 30, 33 }
INPUT : AVL pre-order { 27, 9, 3, 0, 6, 15, 12, 18, 30, 33 } 27
RESULT : AVL pre-order { 9, 3, 0, 6, 30, 15, 12, 18, 33 }
INPUT : AVL pre-order { 9, 3, 0, 6, 30, 15, 12, 18, 33 } 9
RESULT : AVL pre-order { 12, 3, 0, 6, 30, 15, 18, 33 }
INPUT : AVL pre-order { 12, 3, 0, 6, 30, 15, 18, 33 } 12
RESULT : AVL pre-order { 15, 3, 0, 6, 30, 18, 33 }
INPUT : AVL pre-order { 15, 3, 0, 6, 30, 18, 33 } 15
RESULT : AVL pre-order { 18, 3, 0, 6, 30, 33 }
INPUT : AVL pre-order { 18, 3, 0, 6, 30, 33 } 18
RESULT : AVL pre-order { 30, 3, 0, 6, 33 }
INPUT : AVL pre-order { 30, 3, 0, 6, 33 } 30
RESULT : AVL pre-order { 3, 0, 33, 6 }
INPUT : AVL pre-order { 3, 0, 33, 6 } 3
RESULT : AVL pre-order { 6, 0, 33 }
INPUT : AVL pre-order { 6, 0, 33 } 6
RESULT : AVL pre-order { 33, 0 }

Example #5:
for _ in range(100):
case = list(set(random.randrange(1, 20000) for _ in range(900)))
tree = AVL(case)
for value in case[::2]:
tree.remove(value)
if not tree.is_valid_avl():
raise Exception(“PROBLEM WITH REMOVE OPERATION”)
print(‘Stress test finished’)
Output:
remove() stress test finished

CS261 Assignment 5 MinHeap Implementation

General Instructions …………………………………………………. 3

Min Heap Implementation
Summary and Specific Instructions ………………………………….. 4
add() ………………………………………………………………………. 5
is_empty() ……………………………………………………………….. 6
get_min() ………………………………………………………………… 7
remove_min() …………………………………………………………… 7
build_heap() …………………………………………………………….. 8
size() ……………………………………………………………………… 9
clear() …………………………………………………………………….. 9
heapsort() ………………………………………………………………. 10

General Instructions

1. The program in this assignment must be written in Python 3 and submitted to
Gradescope before the due date specified on Canvas and in the Course Schedule. You
may resubmit your code as many times as necessary. Gradescope allows you to
choose which submission will be graded.
2. In Gradescope, your code will run through several tests. Any failed tests will provide
a brief explanation of testing conditions to help you with troubleshooting. Your goal is
to pass all tests.

3. We encourage you to create your own test cases, even though this work won’t need
to be submitted and won’t be graded. Gradescope tests are limited in scope and may
not cover all edge cases. Your submission must work on all valid inputs. We reserve
the right to test your submission with more tests than Gradescope.

4. Your code must have an appropriate level of comments. At a minimum, each method
needs to have a descriptive docstring. Additionally, add comments throughout the
code to make it easy to follow and understand any non-obvious code.
5. You will be provided with a starter “skeleton” code, on which you will build your
implementation. Methods defined in skeleton code must retain their names and
input/output parameters. Variables defined in skeleton code must also retain their
names. We will only test your solution by making calls to methods defined in the
skeleton code and by checking values of variables defined in the skeleton code.

You can add more helper methods and variables, as needed. The MinHeap
skeleton code file includes a suggested helper method. You are also allowed to
add optional default parameters to method definitions.

6. The skeleton code and code examples provided in this document are part of the
assignment requirements. They have been carefully selected to demonstrate
requirements for each method. Refer to them for detailed descriptions of expected
method behavior, input/output parameters, and handling of edge cases. Code
examples may include assignment requirements not explicitly stated elsewhere.

7. For each method, you are required to use an iterative solution. Recursion is
not permitted.
8. We will test your implementation with different types of objects, not just integers.
We guarantee that all such objects will have correct implementation of methods
__eq__(), __lt__(), __gt__(), __ge__(), __le__(), and __str__().

Summary and Specific Instructions

1. Implement the MinHeap class by completing the provided skeleton code in the file
min_heap.py. Once completed, your implementation will include the following
methods:
add()
is_empty()
get_min()
remove_min()
build_heap()
size()
clear()
heapsort()

2. The MinHeap must be implemented with a DynamicArray as per the skeleton code.
You are to use your existing DynamicArray for the implementation.
3. You may wish to augment your existing DynamicArray to assist you in this
assignment. For instance, a method similar to pop() in Python’s list, that removes
the last item in your DynamicArray, may be helpful. Alternatively, you may
implement this functionality inline in your heap implementation, if you prefer.

4. The number of objects stored in the MinHeap will be between 0 and 1,000,000
inclusive.
5. RESTRICTIONS: You are NOT allowed to use ANY built-in Python data structures
and/or their methods.
You are NOT allowed to directly access any variables of the DynamicArray class. All
work must be done only by using class methods.

6. You do not need to write any getter or setter methods for the MinHeap class.
7. Be sure to review your methods to make sure that they meet the runtime complexity
requirements.
8. You may not use any imports beyond the ones included in the assignment source
code provided.

add(self, node: object) -> None:
This method adds a new object to the MinHeap while maintaining heap property.
The runtime complexity of this implementation must be O(log N).
Example #1:
h = MinHeap()
print(h, h.is_empty())
for value in range(300, 200, -15):
h.add(value)
print(h)
Output:
HEAP [] True
HEAP [300]
HEAP [285, 300]
HEAP [270, 300, 285]
HEAP [255, 270, 285, 300]
HEAP [240, 255, 285, 300, 270]
HEAP [225, 255, 240, 300, 270, 285]
HEAP [210, 255, 225, 300, 270, 285, 240]

Example #2:
h = MinHeap([‘fish’, ‘bird’])
print(h)
for value in [‘monkey’, ‘zebra’, ‘elephant’, ‘horse’, ‘bear’]:
h.add(value)
print(h)
Output:
HEAP [‘bird’, ‘fish’]
HEAP [‘bird’, ‘fish’, ‘monkey’]
HEAP [‘bird’, ‘fish’, ‘monkey’, ‘zebra’]
HEAP [‘bird’, ‘elephant’, ‘monkey’, ‘zebra’, ‘fish’]
HEAP [‘bird’, ‘elephant’, ‘horse’, ‘zebra’, ‘fish’, ‘monkey’]
HEAP [‘bear’, ‘elephant’, ‘bird’, ‘zebra’, ‘fish’, ‘monkey’, ‘horse’]

is_empty(self) -> bool:
This method returns True if the heap is empty; otherwise, it returns False.
The runtime complexity of this implementation must be O(1).
Example #1:
h = MinHeap([2, 4, 12, 56, 8, 34, 67])
print(h.is_empty())
Output:
False
Example #2:
h = MinHeap()
print(h.is_empty())
Output:
True

get_min(self) -> object:
This method returns an object with the minimum key, without removing it from the heap. If
the heap is empty, the method raises a MinHeapException.
The runtime complexity of this implementation must be O(1).
Example #1:
h = MinHeap([‘fish’, ‘bird’])
print(h)
print(h.get_min(), h.get_min())
Output:
HEAP [‘bird’, ‘fish’]
bird bird
remove_min(self) -> object:

This method returns an object with the minimum key, and removes it from the heap. If the
heap is empty, the method raises a MinHeapException.
For the downward percolation of the replacement node: if both children of the node have
the same value (and are both smaller than the node), swap with the left child.
The runtime complexity of this implementation must be O(log N).

Example #1:
h = MinHeap([1, 10, 2, 9, 3, 8, 4, 7, 5, 6])
while not h.is_empty() and h.is_empty() is not None:
print(h, end=’ ‘)
print(h.remove_min())
Output:
HEAP [1, 3, 2, 5, 6, 8, 4, 10, 7, 9] 1
HEAP [2, 3, 4, 5, 6, 8, 9, 10, 7] 2
HEAP [3, 5, 4, 7, 6, 8, 9, 10] 3
HEAP [4, 5, 8, 7, 6, 10, 9] 4
HEAP [5, 6, 8, 7, 9, 10] 5
HEAP [6, 7, 8, 10, 9] 6
HEAP [7, 9, 8, 10] 7
HEAP [8, 9, 10] 8
HEAP [9, 10] 9
HEAP [10] 10

build_heap(self, da: DynamicArray) -> None:
This method receives a DynamicArray with objects in any order, and builds a proper
MinHeap from them. The current content of the MinHeap is overwritten.
The runtime complexity of this implementation must be O(N). If the runtime complexity is
O(N log N), you will not receive any points for this portion of the assignment, even if your
method passes Gradescope.

Example #1:
da = DynamicArray([100, 20, 6, 200, 90, 150, 300])
h = MinHeap([‘zebra’, ‘apple’])
print(h)
h.build_heap(da)
print(h)
print(“Inserting 500 into input DA:”)
da[0] = 500
print(da)
print(“Your MinHeap:”)
print(h)
if h.get_min() == 500:
print(“Error: input array and heap’s underlying DA reference same object
in memory”)

Output:
HEAP [‘apple’, ‘zebra’]
HEAP [6, 20, 100, 200, 90, 150, 300]
Inserting 500 into input DA:
DYN_ARR Size/Cap: 7/8 [500, 20, 6, 200, 90, 150, 300]
Your MinHeap:
HEAP [6, 20, 100, 200, 90, 150, 300]

size(self) -> int:
This method returns the number of items currently stored in the heap.
The runtime complexity of this implementation must be O(1).
Example #1:
h = MinHeap([100, 20, 6, 200, 90, 150, 300])
print(h.size())
Output:
7
Example #2:
h = MinHeap([])
print(h.size())
Output:
0
clear(self) -> None:
This method clears the contents of the heap.
The runtime complexity of this implementation must be O(1).

Example #1:
h = MinHeap([‘monkey’, ‘zebra’, ‘elephant’, ‘horse’, ‘bear’])
print(h)
print(h.clear())
print(h)
Output:
HEAP [‘bear’, ‘elephant’, ‘monkey’, ‘zebra’, ‘horse’]
None
HEAP []

heapsort(arr: DynamicArray) -> None:
Write a function that receives a DynamicArray and sorts its content in non-ascending order,
using the Heapsort algorithm. You must sort the array in place, without creating any data
structures. This function does not return anything.

The runtime complexity of this implementation must be O(N log N). If the sort uses an
algorithm other than Heapsort, you will not receive any points for this portion of the
assignment, even if your function passes Gradescope.
Example #1:
da = DynamicArray([100, 20, 6, 200, 90, 150, 300])
print(f”Before: {da}”)
heapsort(da)
print(f”After: {da}”)

Output:
Before: DYN_ARR Size/Cap: 7/8 [100, 20, 6, 200, 90, 150, 300]
After: DYN_ARR Size/Cap: 7/8 [300, 200, 150, 100, 90, 20, 6]
Example #2:
da = DynamicArray([‘monkey’, ‘zebra’, ‘elephant’, ‘horse’, ‘bear’])
print(f”Before: {da}”)
heapsort(da)
print(f”After: {da}”)

Output:
Before: DYN_ARR Size/Cap: 5/8 [monkey, zebra, elephant, horse, bear]
After: DYN_ARR Size/Cap: 5/8 [zebra, monkey, horse, elephant, bear]

CS261 Assignment 6 HashMap Implementation

Part 1 – Summary and Specific Instructions

1. Implement the HashMap class by completing the provided skeleton code in the file
hash_map_sc.py. Once completed, your implementation will include the following
methods:
put()
get()
remove()
contains_key()
clear()
empty_buckets()
resize_table()
table_load()
get_keys()
find_mode()

2. Use a dynamic array to store your hash table and implement chaining for collision
resolution using a singly linked list. Chains of key/value pairs must be stored in
linked list nodes. The diagram below illustrates the overall architecture of the
HashMap class:

3. Two pre-written classes are provided for you in the skeleton code – DynamicArray
and LinkedList (in a6_include.py). You must use objects of these classes in your
HashMap class implementation. Use a DynamicArray object to store your hash table,
and LinkedList objects to store chains of key/value pairs.

4. The provided DynamicArray and LinkedList classes may provide different functionality
than those described in the lectures, or implemented in prior homework
assignments. Review the docstrings in the skeleton code to understand the available
methods, their use, and input/output parameters.

5. The number of objects stored in the hash map will be between 0 and 1,000,000
inclusive.
6. Two pre-written hash functions are provided in the skeleton code. Make sure you test
your code with both functions. We will use these two functions in our testing of your
implementation.

7. RESTRICTIONS: You are NOT allowed to use ANY built-in Python data structures
and/or their methods.
You are NOT allowed to directly access any variables of the DynamicArray or
LinkedList classes. All work must be done only by using class methods.

8. Variables in the SLNode class are not private. You ARE allowed to access and change
their values directly. You do not need to write any getter or setter methods.
9. You may not use any imports beyond the ones included in the assignment source
code provided.

put(self, key: str, value: object) -> None:
This method updates the key/value pair in the hash map. If the given key already exists in
the hash map, its associated value must be replaced with the new value. If the given key is
not in the hash map, a new key/value pair must be added.

For this hash map implementation, the table must be resized to double its current
capacity when this method is called and the current load factor of the table is
greater than or equal to 1.0.
Example #1:
m = HashMap(53, hash_function_1)
for i in range(150):
m.put(‘str’ + str(i), i * 100)
if i % 25 == 24:
print(m.empty_buckets(), round(m.table_load(), 2), m.get_size(),
m.get_capacity())
Output:
39 0.47 25 53
39 0.94 50 53
82 0.7 75 107
79 0.93 100 107
184 0.56 125 223
181 0.67 150 223
Example #2:
m = HashMap(41, hash_function_2)
for i in range(50):
m.put(‘str’ + str(i // 3), i * 100)
if i % 10 == 9:
print(m.empty_buckets(), round(m.table_load(), 2), m.get_size(),
m.get_capacity())
Output:
37 0.1 4 41
34 0.17 7 41
31 0.24 10 41
28 0.34 14 41
26 0.41 17 41

empty_buckets(self) -> int:
This method returns the number of empty buckets in the hash table.
Example #1:
m = HashMap(101, hash_function_1)
print(m.empty_buckets(), m.get_size(), m.get_capacity())
m.put(‘key1’, 10)
print(m.empty_buckets(), m.get_size(), m.get_capacity())
m.put(‘key2’, 20)
print(m.empty_buckets(), m.get_size(), m.get_capacity())
m.put(‘key1’, 30)
print(m.empty_buckets(), m.get_size(), m.get_capacity())
m.put(‘key4’, 40)
print(m.empty_buckets(), m.get_size(), m.get_capacity())

Output:
101 0 101
100 1 101
99 2 101
99 2 101
98 3 101
Example #2:
m = HashMap(53, hash_function_1)
for i in range(150):
m.put(‘key’ + str(i), i * 100)
if i % 30 == 0:
print(m.empty_buckets(), m.get_size(), m.get_capacity())
Output:
52 1 53
39 31 53
83 61 107
80 91 107
184 121 223

table_load(self) -> float:
This method returns the current hash table load factor.
Example #1:
m = HashMap(101, hash_function_1)
print(round(m.table_load(), 2))
m.put(‘key1’, 10)
print(round(m.table_load(), 2))
m.put(‘key2’, 20)
print(round(m.table_load(), 2))
m.put(‘key1’, 30)
print(round(m.table_load(), 2))
Output:
0.0
0.01
0.02
0.02

Example #2:
m = HashMap(53, hash_function_1)
for i in range(50):
m.put(‘key’ + str(i), i * 100)
if i % 10 == 0:
print(round(m.table_load(), 2), m.get_size(), m.get_capacity())
Output:
0.02 1 53
0.21 11 53
0.4 21 53
0.58 31 53
0.77 41 53

clear(self) -> None:
This method clears the contents of the hash map. It does not change the underlying hash
table capacity.
Example #1:
m = HashMap(101, hash_function_1)
print(m.get_size(), m.get_capacity())
m.put(‘key1’, 10)
m.put(‘key2’, 20)
m.put(‘key1’, 30)
print(m.get_size(), m.get_capacity())
m.clear()
print(m.get_size(), m.get_capacity())
Output:
0 101
2 101
0 101

Example #2:
m = HashMap(53, hash_function_1)
print(m.get_size(), m.get_capacity())
m.put(‘key1’, 10)
print(m.get_size(), m.get_capacity())
m.put(‘key2’, 20)
print(m.get_size(), m.get_capacity())
m.resize_table(100)
print(m.get_size(), m.get_capacity())
m.clear()
print(m.get_size(), m.get_capacity())
Output:
0 53
1 53
2 53
2 101
0 101

resize_table(self, new_capacity: int) -> None:
This method changes the capacity of the internal hash table. All existing key/value pairs
must remain in the new hash map, and all hash table links must be rehashed. (Consider
calling another HashMap method for this part).

First check that new_capacity is not less than 1; if so, the method does nothing.
If new_capacity is 1 or more, make sure it is a prime number. If not, change it to the next
highest prime number. You may use the methods _is_prime() and _next_prime() from the
skeleton code.

Example #1:
m = HashMap(23, hash_function_1)
m.put(‘key1’, 10)
print(m.get_size(), m.get_capacity(), m.get(‘key1’), m.contains_key(‘key1’))
m.resize_table(30)
print(m.get_size(), m.get_capacity(), m.get(‘key1’), m.contains_key(‘key1’))

Output:
1 23 10 True
1 31 10 True
Example #2:
m = HashMap(79, hash_function_2)
keys = [i for i in range(1, 1000, 13)]
for key in keys:
m.put(str(key), key * 42)
print(m.get_size(), m.get_capacity())
for capacity in range(111, 1000, 117):
m.resize_table(capacity)
m.put(‘some key’, ‘some value’)
result = m.contains_key(‘some key’)
m.remove(‘some key’)
for key in keys:
result &= m.contains_key(str(key))
result &= not m.contains_key(str(key + 1))
print(capacity, result, m.get_size(), m.get_capacity(),
round(m.table_load(), 2))

Output:
77 79
111 True 77 113 0.68
228 True 77 229 0.34
345 True 77 347 0.22
462 True 77 463 0.17
579 True 77 587 0.13
696 True 77 701 0.11
813 True 77 821 0.09
930 True 77 937 0.08

get(self, key: str) -> object:
This method returns the value associated with the given key. If the key is not in the hash
map, the method returns None.
Example #1:
m = HashMap(31, hash_function_1)
print(m.get(‘key’))
m.put(‘key1’, 10)
print(m.get(‘key1’))
Output:
None
10
Example #2:
m = HashMap(151, hash_function_2)
for i in range(200, 300, 7):
m.put(str(i), i * 10)
print(m.get_size(), m.get_capacity())
for i in range(200, 300, 21):
print(i, m.get(str(i)), m.get(str(i)) == i * 10)
print(i + 1, m.get(str(i + 1)), m.get(str(i + 1)) == (i + 1) * 10)

Output:
15 151
200 2000 True
201 None False
221 2210 True
222 None False
242 2420 True
243 None False
263 2630 True
264 None False
284 2840 True
285 None False

contains_key(self, key: str) -> bool:
This method returns True if the given key is in the hash map, otherwise it returns False. An
empty hash map does not contain any keys.

Example #1:
m = HashMap(53, hash_function_1)
print(m.contains_key(‘key1’))
m.put(‘key1’, 10)
m.put(‘key2’, 20)
m.put(‘key3’, 30)
print(m.contains_key(‘key1’))
print(m.contains_key(‘key4’))
print(m.contains_key(‘key2’))
print(m.contains_key(‘key3’))
m.remove(‘key3’)
print(m.contains_key(‘key3’))
Output:
False
True
False
True
True
False

Example #2:
m = HashMap(79, hash_function_2)
keys = [i for i in range(1, 1000, 20)]
for key in keys:
m.put(str(key), key * 42)
print(m.get_size(), m.get_capacity())
result = True
for key in keys:
# all inserted keys must be present
result &= m.contains_key(str(key))
# NOT inserted keys must be absent
result &= not m.contains_key(str(key + 1))
print(result)
Output:
50 79
True

remove(self, key: str) -> None:
This method removes the given key and its associated value from the hash map. If the key
is not in the hash map, the method does nothing (no exception needs to be raised).
Example #1:
m = HashMap(53, hash_function_1)
print(m.get(‘key1’))
m.put(‘key1’, 10)
print(m.get(‘key1’))
m.remove(‘key1’)
print(m.get(‘key1’))
m.remove(‘key4′)
Output:
None
10
None
get_keys_and_values(self) -> DynamicArray:

This method returns a dynamic array where each index contains a tuple of a key/value pair
stored in the hash map. The order of the keys in the dynamic array does not matter.
Example #1:
m = HashMap(11, hash_function_2)
for i in range(1, 6):
m.put(str(i), str(i * 10))
print(m.get_keys_and_values())
m.put(’20’, ‘200’)
m.remove(‘1’)
m.resize_table(2)
print(m.get_keys_and_values())

Output:
[(‘1′, ’10’), (‘2′, ’20’), (‘3′, ’30’), (‘4′, ’40’), (‘5′, ’50’)]
[(‘2′, ’20’), (‘3′, ’30’), (’20’, ‘200’), (‘4′, ’40’), (‘5′, ’50’)]

find_mode(arr: DynamicArray) -> (DynamicArray, int):
Write a standalone function outside of the HashMap class that receives a dynamic array
(that is not guaranteed to be sorted). This function will return a tuple containing, in this
order, a dynamic array comprising the mode (most occurring) value/s of the array, and an
integer that represents the highest frequency (how many times the mode value(s) appear).
If there is more than one value with the highest frequency, all values at that frequency
should be included in the array being returned (the order does not matter). If there is only
one mode, the dynamic array will only contain that value.

You may assume that the input array will contain at least one element, and that all values
stored in the array will be strings. You do not need to write checks for these conditions.
For full credit, the function must be implemented with O(N) time complexity. For best
results, we recommend using the separate chaining hash map provided for you in the
function’s skeleton code.

Example #1:
da = DynamicArray([“apple”, “apple”, “grape”, “melon”, “peach”])
mode, frequency = find_mode(da)
print(f”Input: {da}\nMode : {mode}, Frequency: {frequency}”)
Output:
Input: [‘apple’, ‘apple’, ‘grape’, ‘melon’, ‘peach’]
Mode : [‘apple’], Frequency: 2

Example #2:
test_cases = (
[“Arch”, “Manjaro”, “Manjaro”, “Mint”, “Mint”, “Mint”, “Ubuntu”,
“Ubuntu”, “Ubuntu”],
[“one”, “two”, “three”, “four”, “five”],
[“2”, “4”, “2”, “6”, “8”, “4”, “1”, “3”, “4”, “5”, “7”, “3”, “3”, “2”]
)
for case in test_cases:
da = DynamicArray(case)
mode, frequency = find_mode(da)
print(f”{da}\nMode : {mode}, Frequency: {frequency}\n”)

Output:
Input: [‘Arch’, ‘Manjaro’, ‘Manjaro’, ‘Mint’, ‘Mint’, ‘Mint’, ‘Ubuntu’,
‘Ubuntu’, ‘Ubuntu’]
Mode : [‘Mint’, ‘Ubuntu’], Frequency: 3
Input: [‘one’, ‘two’, ‘three’, ‘four’, ‘five’]
Mode : [‘one’, ‘four’, ‘two’, ‘five’, ‘three’], Frequency: 1
Input: [‘2’, ‘4’, ‘2’, ‘6’, ‘8’, ‘4’, ‘1’, ‘3’, ‘4’, ‘5’, ‘7’, ‘3’, ‘3’, ‘2’]
Mode : [‘2’, ‘3’, ‘4’], Frequency: 3

Part 2 – Summary and Specific Instructions

1. Implement the HashMap class by completing the provided skeleton code in the file
hash_map_oa.py. Your implementation will include the following methods:
put()
get()
remove()
contains_key()
clear()
empty_buckets()
resize_table()
table_load()
get_keys()
__iter__(), __next__()

2. Use a dynamic array to store your hash table, and implement Open Addressing
with Quadratic Probing for collision resolution inside that dynamic array. Key/value
pairs must be stored in the array. Refer to the Explorations for an example of this
implementation.

3. Use the pre-written DynamicArray class in a6_include.py. You must use objects of
this class in your HashMap class implementation. Use a DynamicArray object to store
your Open Addressing hash table.

4. The provided DynamicArray class may provide different functionality than the one
described in the lectures or implemented in prior homework assignments. Review the
docstrings in the skeleton code to understand the available methods, their use, and
input/output parameters.

7. RESTRICTIONS: You are NOT allowed to use ANY built-in Python data structures
and/or their methods. You are NOT allowed to directly access any variables of the
DynamicArray class. All work must be done only by using class methods.

8. Variables in the HashEntry class are not private. You ARE allowed to access and
change their values directly. You do not need to write any getter or setter methods.
9. You may not use any imports beyond the ones included in the assignment source
code.

For this hash map implementation, the table must be resized to double its current
capacity when this method is called and the current load factor of the table is
greater than or equal to 0.5.

Example #1:
m = HashMap(53, hash_function_1)
for i in range(150):
m.put(‘str’ + str(i), i * 100)
if i % 25 == 24:
print(m.empty_buckets(), m.table_load(), m.get_size(),
m.get_capacity())
Output:
28 0.47 25 53
57 0.47 50 107
148 0.34 75 223
123 0.45 100 223
324 0.28 125 449
299 0.33 150 449
Example #2:
m = HashMap(41, hash_function_2)
for i in range(50):
m.put(‘str’ + str(i // 3), i * 100)
if i % 10 == 9:
print(m.empty_buckets(), m.table_load(), m.get_size(),
m.get_capacity())

Output:
37 0.1 4 41
34 0.17 7 41
31 0.24 10 41
27 0.34 14 41
24 0.41 17 41

table_load(self) -> float:
This method returns the current hash table load factor.
Example #1:
m = HashMap(101, hash_function_1)
print(m.table_load())
m.put(‘key1’, 10)
print(m.table_load())
m.put(‘key2’, 20)
print(m.table_load())
m.put(‘key1’, 30)
print(m.table_load())
Output:
0.0
0.01
0.02
0.02

Example #2:
m = HashMap(53, hash_function_1)
for i in range(50):
m.put(‘key’ + str(i), i * 100)
if i % 10 == 0:
print(m.table_load(), m.get_size(), m.get_capacity())
Output:
0.02 1 53
0.21 11 53
0.4 21 53
0.29 31 107
0.38 41 107

Output:
101 0 101
100 1 101
99 2 101
99 2 101
98 3 101

Example #2:
m = HashMap(53, hash_function_1)
for i in range(150):
m.put(‘key’ + str(i), i * 100)
if i % 30 == 0:
print(m.empty_buckets(), m.get_size(), m.get_capacity())
Output:
52 1 53
76 31 107
162 61 223
132 91 223
328 121 449

resize_table(self, new_capacity: int) -> None:
This method changes the capacity of the internal hash table. All existing key/value pairs
must remain in the new hash map, and all hash table links must be rehashed.
First check that new_capacity is not less than the current number of elements in the hash
map; if so, the method does nothing.

If new_capacity is valid, make sure it is a prime number; if not, change it to the next
highest prime number. You may use the methods _is_prime() and _next_prime() from the
skeleton code.

Output:
1 23 10 True
1 31 10 True
Example #2:
m = HashMap(79, hash_function_2)
keys = [i for i in range(1, 1000, 13)]
for key in keys:
m.put(str(key), key * 42)
print(m.get_size(), m.get_capacity())
for capacity in range(111, 1000, 117):
m.resize_table(capacity)
m.put(‘some key’, ‘some value’)
result = m.contains_key(‘some key’)
m.remove(‘some key’)
for key in keys:
result &= m.contains_key(str(key))
result &= not m.contains_key(str(key + 1))
print(capacity, result,m.get_size(), m.get_capacity(),
round(m.table_load(), 2))

Output:
77 163
111 True 77 227 0.34
228 True 77 229 0.34
345 True 77 347 0.22
462 True 77 463 0.17
579 True 77 587 0.13
696 True 77 701 0.11
813 True 77 821 0.09
930 True 77 937 0.08

Example #2:
m = HashMap(151, hash_function_2)
for i in range(200, 300, 7):
m.put(str(i), i * 10)
print(m.get_size(), m.get_capacity())
for i in range(200, 300, 21):
print(i, m.get(str(i)), m.get(str(i)) == i * 10)
print(i + 1, m.get(str(i + 1)), m.get(str(i + 1)) == (i + 1) * 10)
Output:
15 151
200 2000 True
201 None False
221 2210 True
222 None False
242 2420 True
243 None False
263 2630 True
264 None False
284 2840 True
285 None False

contains_key(self, key: str) -> bool:
This method returns True if the given key is in the hash map, otherwise it returns False. An
empty hash map does not contain any keys.

Output:
False
True
False
True
True
False

Output:
50 163
True

Example #1:
m = HashMap(53, hash_function_1)
print(m.get(‘key1’))
m.put(‘key1’, 10)
print(m.get(‘key1’))
m.remove(‘key1’)
print(m.get(‘key1’))
m.remove(‘key4’)
Output:
None
10
None

Example #2:
m = HashMap(53, hash_function_1)
print(m.get_size(), m.get_capacity())
m.put(‘key1’, 10)
print(m.get_size(), m.get_capacity())
m.put(‘key2′, 20)
print(m.get_size(), m.get_capacity())
m.resize_table(100)
print(m.get_size(), m.get_capacity())
m.clear()
print(m.get_size(), m.get_capacity())

Output:
0 53
1 53
2 53
2 101
0 101

get_keys_and_values(self) -> DynamicArray:
This method returns a dynamic array where each index contains a tuple of a key/value pair
stored in the hash map. The order of the keys in the dynamic array does not matter.
Example #1:
m = HashMap(11, hash_function_2)
for i in range(1, 6):
m.put(str(i), str(i * 10))
print(m.get_keys_and_values())
m.resize_table(2)
print(m.get_keys_and_values())
m.put(’20’, ‘200’)
m.remove(‘1’)
m.resize_table(12)
print(m.get_keys_and_values())

Output:
[(‘1′, ’10’), (‘2′, ’20’), (‘3′, ’30’), (‘4′, ’40’), (‘5′, ’50’)]
[(‘1′, ’10’), (‘2′, ’20’), (‘3′, ’30’), (‘4′, ’40’), (‘5′, ’50’)]
[(‘4′, ’40’), (‘5′, ’50’), (’20’, ‘200’), (‘2′, ’20’), (‘3′, ’30’)]

__iter__():
This method enables the hash map to iterate across itself. Implement this method in a
similar way to the example in the Exploration: Encapsulation and Iterators.
You ARE permitted (and will need to) initialize a variable to track the iterator’s progress
through the hash map’s contents.

You can use either of the two models demonstrated in the Exploration – you can build the
iterator functionality inside the HashMap class, or you can create a separate iterator class.
Example #1:
m = HashMap(10, hash_function_1)
for i in range(5):
m.put(str(i), str(i * 10))
print(m)
for item in m:
print(‘K:’, item.key, ‘V:’, item.value)
Output:
0: None
1: None
2: None
3: None
4: K: 0 V: 0 TS: False
5: K: 1 V: 10 TS: False
6: K: 2 V: 20 TS: False
7: K: 3 V: 30 TS: False
8: K: 4 V: 40 TS: False
9: None
10: None
K: 0 V: 0
K: 1 V: 10
K: 2 V: 20
K: 3 V: 30
K: 4 V: 40

__next__():
This method will return the next item in the hash map, based on the current location of the
iterator. Implement this method in a similar way to the example in the Exploration:
Encapsulation and Iterators. It will need to only iterate over active items.

Example #2:
m = HashMap(10, hash_function_2)
for i in range(5):
m.put(str(i), str(i * 24))
m.remove(‘0’)
m.remove(‘4’)
print(m)
for item in m:
print(‘K:’, item.key, ‘V:’, item.value)
Output:
0: None
1: None
2: None
3: None
4: K: 0 V: 0 TS: True
5: K: 1 V: 24 TS: False
6: K: 2 V: 48 TS: False
7: K: 3 V: 72 TS: False
8: K: 4 V: 96 TS: True
9: None
10: None
K: 1 V: 24
K: 2 V: 48
K: 3 V: 72

CS261 Data Structures Assignment 1 to 6 solutions

Description

CS261 Assignment 1 Python Fundamentals Review

Summary

General Instructions

Specific Instructions

CS261 Assignment 2 Dynamic Array Implementation (plus a brand new Bag)

Contents

General Instructions ………………………………………………………….

General Instructions

Part 1 – Summary and Specific Instructions

Part 2 – Summary and Specific Instructions

CS261 Assignment 3: Linked List / ADT Implementation

Part 1 – Summary and Specific Instructions

Part 2 – Summary and Specific Instructions

Part 3 – Summary and Specific Instructions

Part 4 – Summary and Specific Instructions

Part 5 – Summary and Specific Instructions

CS261 Assignment 4 BST/AVL Tree Implementation

Part 1 – Summary and Specific Instructions

Part 2 – Summary and Specific Instructions

CS261 Assignment 5 MinHeap Implementation

Contents

General Instructions

Summary and Specific Instructions

CS261 Assignment 6 HashMap Implementation

Part 1 – Summary and Specific Instructions

Part 2 – Summary and Specific Instructions

Related products

CS 261 CS : Assignment 1 C Programming Practice solved

CS 261 Assignment 3 ­­ Linked List Variations solved

CS261 Assignment 6 HashMap Implementation solution

CS 261 Assignment 3 Linked List Variations solved