Description
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.
Table of Contents Page 3 of 19
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.
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.
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__().
Page 4 of 19
CS261 Data Structures Assignment 1: Python Fundamentals Review
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
Page 6 of 19
CS261 Data Structures Assignment 1: Python Fundamentals Review
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]
Page 8 of 19
CS261 Data Structures Assignment 1: Python Fundamentals Review
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]
Page 10 of 19
CS261 Data Structures Assignment 1: Python Fundamentals Review
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]
Page 12 of 19
CS261 Data Structures Assignment 1: Python Fundamentals Review
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.
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 (including Static Arrays) being created.
Example #1:
test_cases = (
[1, 20, 30, 40, 500, 500, 500],
[2, 2, 2, 2, 1, 1, 1, 1],
[“zebra”, “sloth”, “otter”, “otter”, “moose”, “koala”],
[“Albania”, “Belgium”, “Chile”, “Denmark”, “Egypt”, “Fiji”]
)
for case in test_cases:
arr = StaticArray(len(case))
for i, value in enumerate(case):
arr[i] = value
result = find_mode(arr)
if result:
print(f”{arr}\nMode: {mode}, Frequency: {frequency}\n”)
else:
print(“find_mode() not yet implemented”)
Output:
STAT_ARR Size: 7 [1, 20, 30, 40, 500, 500, 500]
Mode: 500, Frequency: 3
STAT_ARR Size: 8 [2, 2, 2, 2, 1, 1, 1, 1]
Mode: 2, Frequency: 4
STAT_ARR Size: 6 [‘zebra’, ‘sloth’, ‘otter’, ‘otter’, ‘moose’, ‘koala’]
Mode: otter, Frequency: 2
STAT_ARR Size: 6 [‘Albania’, ‘Belgium’, ‘Chile’, ‘Denmark’, ‘Egypt’, ‘Fiji’]
Mode: Albania, Frequency: 1
Page 14 of 19
CS261 Data Structures Assignment 1: Python Fundamentals Review
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}”)
Page 16 of 19
CS261 Data Structures Assignment 1: Python Fundamentals Review
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]
Page 18 of 19
CS261 Data Structures Assignment 1: Python Fundamentals Review
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
Table of Contents Page 19 of 19
