CS 201 Data Structures 2 Homework 1 -Solved

This write-up has 3 parts. The first part provides an explanation of your implementation tasks. It refers 
to code that is provided in the appendices in the third part. The second part lists the tasks for you to do. 
It contains space for you to enter your solutions to some of the problems. The third part lists code which is 
referred to in the first part. 
You have to fill in the solutions in the second part, and complete the code files in the accompanying src/ 
folder as described in Part 1. Please work in this file, hw1.tex, and not in a copy. When submitting, please 
remove the first and third parts from this file. 
Part I 
Explanation 
In this assignment, we will implement an ArrayList to represent a List. We will use the List to implement 
an image and will write operations for the image. 
1 Image Operations 
We will work with RGB images and perform four operations on them–channel suppression, rotations, mask 
application, and resize. None of these operations is destructive. That is, the operations do not alter the 
original image, rather they return a new image containing the result of the operation. 
1.1 Channel Suppression 
An image is said to contain color values in different channels. In an RGB image, the channels are Red, Blue, 
and Green. Each channel contains the intensities for that color for every pixel in the image. The values from 
all three channels at a pixel yield the RGB value at the pixel. A channel suppression operation switches off 
a specific channel. That is, all intensities in that channel are turned to zero, or turned off. Figure 1 shows 
an original image and two modifications, one with the blue channel turned off, and the other with only the 
blue channel turned on, i.e. the red and green channels turned off. 
1.2 Rotation 
Given a square image, i.e. one whose width is equal to its height, this operation generates a new image that 
contains rotations of the original image. Figure 2 shows an example of applying the operation. The resulting 
image has twice the dimensions of the original image, i.e. twice the width and twice the height. It contains 
4 appropriately placed sub-images which, going anti-clockwise are the original image rotated anti-clockwise 
by increments of 90◦. 
1CS 201 Data Structures II Homework 1: Lists Spring 2023 
(a) An RGB image of a swimming 
pool. 
(b) The image with the blue chan
nel turned off. 
(c) The original image with only 
the blue channel turned on. 
Figure 1: Example of channel suppression. 
(a) A square image. 
(b) The image obtained as a result of ap
plying rotations to the original image. 
Figure 2: Example of rotation. 
1.3 Applying a Mask 
A mask specifies certain weights and applying the mask to an image entails replacing the value at each pixel 
in the image with a weighted sum or weighted average of the values of its neighbors. The weights and the 
neighbors to consider for the average are specified by the mask. 
A mask is an n × n array of integers representing weights. For our purposes, n must be odd. This 
means that the n × n array has a well defined center–the origin. The weights in the mask can be arbitrary 
integers–positive, negative, or zero. 
For each pixel in the input image, think of the mask as being placed on top of the image so its origin 
is on the pixel we wish to examine. The intensity value of each pixel under the mask is multiplied by the 
corresponding value in the mask that covers it. These products are added together. Always use the original 
values for each pixel for each mask calculation, not the new values that you compute as you process the 
image. 
For example, refer to Figure 3a, which shows the 3 × 3 mask, 

 
1 3 1 
3 5 3 
1 3 1 

 
and an image on which we want to perform the mask computation. Suppose we want to compute the result 
of the mask computation for pixel e. This result would be: 
a + 3b + c + 3d + 5e + 3f + g + 3h + i 
Some masks require a weighted average instead of a weighted sum. The weighted average in the case of 
Figure 3a for pixel e would be: 
a + 3b + c + 3d + 5e + 3f + g + 3h + i 
1 + 3 + 1 + 3 + 5 + 3 + 1 + 3 + 1 
Page 2 of 20CS 201 Data Structures II Homework 1: Lists Spring 2023 
(a) Overlay the 3×3 mask over the image so it is centered 
on pixel e to compute the new value for pixel e. 
(b) If the mask hangs over the edge of the image, use only 
those mask values that cover the image in the weighted 
sum. 
Figure 3: Applying a mask to an image. 
Instead of doing this calculation for each channel individually at a pixel, for the purpose of this calculation, 
replace the value of each channel at the pixel with the average channel value at the pixel. For example, if the 
pixel is given by (r, g, b) = (107, 9, 218), then apply the mask to the average value (107 + 9 + 218)//3 = 111 
(integer division) and copy the result to each channel of the corresponding pixel in the output image. This 
effectively converts the output image to grayscale. 
Note that sometimes when you center the mask over a pixel, the mask will hang over the edge of the 
image. In this case, compute the weighted sum of only those pixels that the mask covers. For the example 
shown in Figure 3b, the weighted sum for the pixel e is given by: 
3b + c + 5e + 3f + 3h + i 
and the weighted average is as follows. 
3b + c + 5e + 3f + 3h + i 
3 + 1 + 5 + 3 + 3 + 1 
Integer division is used when computing averages in order to ensure that pixel intensities are integers. 
1.3.1 Applications of Masks 
Applying different masks leads to different properties. For example, applying the following mask leads to 
blurring of the image. Figures 4a and 4b show the blurring effect of this mask. Note that color information 
is lost as mentioned above. 





 
2 4 5 4 2 
4 9 12 9 4 
5 12 15 12 5 
4 9 12 9 4 
2 4 5 4 2 





 
. 
Another application we use is an implementation of Canny Edge Detection using Sobel Operators. Once 
the image has been blurred as above, two more filters, or masks, (the Sobel operators) are applied in 
succession to the blurred image. These filters determine the change in intensity, which approximates the 
3 
(a) An image with sharp details and 
several lines. 
(b) Result of applying the blur mask 
to the original image. 
(c) Result of applying the Sobel fil
ters to the blurred image. 
Figure 4: Blurring and detection of edges in an image using masks. 
horizontal and vertical derivatives. 
Gx = 
 
−
1 0 1 
−2 0 2 
−1 0 1 

 
, Gy = 
 
−
1 −2 
−1 
0 0 0 
1 2 1 

 
. 
After these operations are applied one after the other to the blurred image, the values obtained are used to 
search for edges based on the magnitude and direction of the change in intensity. An example of the final 
result is shown in Figure 4c. 
1.4 Resize 
Given an image, this operation generates a new image that has twice the dimensions of the original image 
i.e, twice the width and twice the height. Figure 5 shows a 4x3 image which is resized to twice its size. The 
resized image has 4 times as many pixels and some of them take on the values from the original image as 
shown. For the pixels shown to be blank, color values are not known and have to be computed from the 
known values. Consider the labeled pixels in the resized image below. One way to fill in the missing color 
information is as follows. 
P = 
1
2
(A + B), T = 
1
2
(C + D), Q = 
1
2
(A + C), S = 
1
2
(B + D) 
Page 4 of 20CS 201 Data Structures II Homework 1: Lists Spring 2023 
Figure 5: Bilinear Interpolation 
There are various ways to compute R, all of which are ultimately equivalent. 
R = 
1
2
(P + T) = 
1
2
(S + Q) = 
1
4
(A + B + C + D) = 
1
4
(P + Q + S + T) = 
1
8
(A + B + C + D + P + Q + S + T) 
The boundary pixels pose a problem as some of the neighboring pixels required for the average do not exist. 
In such cases, only the existing neighbors are used for the average. 
Notice how all the above expressions are affine combinations. Furthermore, the colors for P, Q, S, and T 
are linearly interpolated from their horizontal or vertical neighbors. The color for R is a bilinear interpolation: 
it is a linear interpolation of P and T, or Q and S, which are themselves linear interpolations. 
Note: All divisions in the above expressions are integer divisions. 
2 Image 
We treat an image as a grid of pixels where each pixel is represented as an RGB value indicating the red, 
green, and blue intensities of the pixel. An image has dimensions, namely width and height, which determine 
the number of rows and columns in the image. Every pixel in the image is at a unique combination of row 
and column numbers which can therefore be used as a coordinate system in the image. An image with width 
w and height h is said to be of size w × h. Figure 6a shows the column and row numbers in a w × h image 
along with the resulting pixel coordinates. Note that the coordinate is just a means to locate a pixel in the 
image, it is not the value stored at the pixel. The value stored at a pixel is a triplet denoting the red, green, 
and blue intensities respectively. 
We will work with a flattened representation of an image. That is, we will store the pixel values in a 
1-dimensional list structure as opposed to a 2-dimensional structure (programming languages generally store 
multi-dimensional arrays in their flattened form) . The list stores pixel values as they appear in the image 
from left to right and top to bottom. Figure 6b shows a 5 × 5 image with some supposed RGB values. 
Note that each value would be a triplet of integers, each integer between 0 and 255 inclusive. Using our 
representation, the image in Figure 6b will be represented as the list: 
[a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y] 
Page 5 of 20CS 201 Data Structures II Homework 1: Lists Spring 2023 
Columns 
0 1 2 . . . (w − 1) 
0 
(0, 0) 
(0, 1) 
(0, 2) 
. . . 
(0, w − 1) 
1 
(1, 0) 
(1, 1) 
(1, 2) 
. . . 
(1, w − 1) 
2 
(2, 0) 
(2, 1) 
(2, 2) 
. . . 
(2, w − 1) 
.
.
. 
(h − 1) 
(h − 1, 0) 
(h − 1, 1) 
(h − 1, 2) 
. . . 
(h − 1, w − 1) 
(a) Row and column numbers of an image with width w and height h. Pixel 
coordinates are also shown. 
a 
b 
c 
d 
e 
f 
g 
h 
i 
j 
k 
l 
m 
n 
o 
p 
q 
r 
s 
t 
u 
v 
w 
x 
y 
(b) A 5 × 5 image with supposed 
pixel values. 
Figure 6: Image dimensions and pixel coordinates. 
3 Implementation Details and Tasks 
We will be working with a MyImage class as shown in Listing 1 on Page 9, also included in the accompanying 
file src/myimage.py. Its implementation is complete but requires a concrete implementation of MyList which 
is our implementation of the List interface. The implementation to be used is specified in the constructor of 
MyImage. 
An implementation of MyList is shown in Listing 2 on Page 12, also included in the accompanying file 
src/mylist.py. The implementation is mostly complete except for the segments marked as pass. These 
are to be implemented appropriately in the subclasses of MyList which are indicated at the end of the listing 
and whose implementation is completely missing. Writing their implementations is one of your tasks in this 
assignment. 
Once you are done implementing MyList subclasses, the MyImage class is ready to be operated on. 
Functions corresponding to the operations described in Section 1 are shown in Listing 3 on Page 16 and 
included in the accompanying file src/image operations.py. None of the operations is destructive. That 
is, each operates on a MyImage instance and returns the result as a new MyImage instance. The functions 
are missing implementations. Writing their implementations is another of your tasks in this assignment. 
3.1 Tasks 
❼ Go over the provided files thoroughly in order to understand what they do or are expected to do. 
❼ Provide implementations for unimplemented methods, i.e. those that have pass in their body. 
❼ Derive ArrayList class from MyList and provide its implementation in the same file. ArrayList 
implements the list using python arrays. 
3.2 Requirement 
You will need to install Pillow which will prove the PIL module used in the provided code. 
3.3 Tips 
Below are some tips to avoid the errors that have previously caused tests to fail. Following these may save 
you many frustrating hours of debugging! 
❼ Delay division as much as possible and perform int division wherever needed. 
❼ When writing gray values to file, make sure to clamp them to [0,255]. 
❼ Take care about imagine indexing. 
❼ Be careful when creating a copy of the image. Use the copy where needed and the original where 
needed. 
Page 6 of 20 
RowsCS 201 Data Structures II Homework 1: Lists Spring 2023 
❼ Do not forget to average the RGB values when the corresponding flag in apply_mask is enabled. 
❼ Take care about efficiency. Some structures are slow. If, on top, your code is inefficient, the automated 
tests may fail due to time out. 
3.4 Testing 
Once you have successfully implemented the subclasses and image operations, you can test your code by 
creating an image and performing operations on it. Your submission will be tested automatically by GitHub 
using the accompnaying pytest file, test image.py. 
4 Credits 
This homework is adapted from Homework 3 of the Fall 2014 offering of 15-122: Principles of Imperative 
Computation at Carnegie Mellon University (CMU). 
Part II 
Problems 
The grading is defined in the accompanying rubric file. 
1. Implementation 
Complete the tasks listed in Section 3.1 by providing the implementations in the indicated files. 
2. Amortized Analysis 
Consider an ArrayStack implementation of the List interface with a slightly altered resize() operation. 
Instead of reserving space for 2n elements in the new array, it reserves space for n+⌈ n
4 ⌉ elements. Prove 
that the append() operation still takes O(1) time in the amortized sense. 
Solution: 
Traditional resize() where the length of the array doubles when the array is full works by allocating 
an array b of size 2n, and copies the n elements of the original array a into the new array b and then 
sets a to b. Therefore, a has length of 2n now. This takes O(n) time where the append() operation 
takes O(1) time. 
If the new resize() operation reserves space for n + [ n
4 ] elements, then the append() operation 
would still take O(1) time in the amortized sense. 
This can be undertood better by first understanding the cost of append() for when resize() reserves 
space for 2n elements; 
Resize of 2n: 
Consider an array of size 1. The cost of appending an element would be O(1) [n = 1]. 
Now for the second append(), resize would be called, and then the total cost of appending the 
second element would be O(2)[n = 2]. 
For the third append(), resize() would again be called and the total cost would be O(3)[n = 3]. 
For the fourth append(), resize() won’t be called as the array is not full, and only the cost of 
append() is taken into account, therefore the total cost is O(4), however, this takes into account 
traversal cost as well, and the cost of append() remains O(1). 
Page 7 of 20CS 201 Data Structures II Homework 1: Lists Spring 2023 
With the next append() operation[n = 5], a new array will be created with space reserved for 8 
elements. Then the total cost of appending all elements into the new array is O(5), however, the 
individual cost of append() remains O(1). 
Then using the above, we can make a series such that: 
Series = 1 + (1 + 1) + (1 + 2) + 1 + (1 + 4) + 1 + 1 + 1 + (1 + 8) + · · · 
Therefore, the total cost becomes: 
Cost = 1 + 2 + 4 + 8 + · · · [for resize()] +1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 · · · [for append()] 
The above series for resize can be written as a geometric series where resize() = 2log2(n)−i + 1. 
Hence the total cost of resize() comes out to be O(1) with each append() operation having a cost 
of O(1). 
Resize of n + n
4 : 
Then we can prove that the append() operation has a cost of O(1) in the amortized sense. 
The new size increase is of n + n
4 =⇒ 54n . So space is reserved in the new array for 54n elements(we 
will consider ceil value for decimal numbers). 
Now consider an array of size 1. The cost of appending just one element would be O(1) [n = 1]. 
For another append() operation [n = 2], the total cost would be considering the cost of resize, and 
the cost of append. The resize() function would give us 14 = 0.25. Ceil(0.25) = 1. Therefore, the 
total cost becomes 1 + ceil( n
4 ) = 1 + 1 = O(2). 
For the third append() [n = 3] operation, the total cost would be considering the cost of resize, 
and the cost of append. The resize() function would give us 
2
4 
= 0.5. Ceil of this is equal to 1. 
Therefore the total cost would be 1 + 1 + 1 = O(3). 
For the fourth append() operation, the same takes place. 
For the fifth append() operation, resize() reserves space for 2 elements, as resize() gives us 
5
4 = 1.25, and the ceil of this is 2. Therefore, space is reserved for two elements. Therefore, the 
following append() operation would cost O(1). 
Then using the above, we can make a series such that: 
Series = 1 + (1 + 1) + (1 + 2) + (1 + 3) + (1 + 4) + (1 + 5) + 1 + (1 + 7) + · · · 
Therefore, the total cost becomes: 
Cost = 1 + 2 + 3 + 4 + 5 + 7 + · · · [for resize()] +1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + · · · [for append()] 
Then the series can be written as a geometric series where resize() = n + 
5 log 54n +1 
4 
=⇒ O(n) as 
n gets larger. 
Then the cost of appending one element is O
(n) 
n 
= O(1). Hence proved that the append() operation 
still takes O(1) time in the amortized sense. 
Page 8 of 20CS 201 Data Structures II Homework 1: Lists Spring 2023 
Part III 
Appendices 
A 
MyImage 
1 from PIL 
import 
Image 
2 from 
src . mylist 
import ArrayList 
3
4
5 class MyImage : 
6 
""" Holds a flattened RGB 
image and its dimensions . Also implements Iterator 
7 
methods to allow iteration 
over 
this image . 
8 
""" 
9 
10 
def __init__ ( self , size : (int , int )) -> None : 
11 
""" Initializes a black 
image of the given 
size . 
12 
13 
Parameters : 
14 
- self : mandatory 
reference to this object 
15 
- size : ( width , height ) specifies the dimensions to create . 
16 
17 
Returns : 
18 
none 
19 
""" 
20 
# Save size , create a list of the desired size with black pixels . 
21 
width , height = self . size = size 
22 
self . pixels : ArrayList = ArrayList ( width * height , 
23 
value =(0 , 0 , 0)) 
24 
25 
def __iter__ ( self ) -> ✬MyImage ✬: 
26 
✬✬✬ Iterator function to return an iterator 
( self ) that allows iteration over 
27 
this image . 
28 
29 
Parameters : 
30 
- self : mandatory reference to this object 
31 
32 
Returns : 
33 
an iterator 
( self ) that allows iteration over this image . 
34 
✬✬✬ 
35 
# Initialize iteration indexes . 
36 
self . _iter_r : int = 0 
37 
self . _iter_c : int = 0 
38 
return self 
39 
40 
def __next__ ( self ): 
41 
✬✬✬✬ Iterator function to return the next value from this list . 
42 
43 
Image pixels are iterated over in a left -to - right , top -to - bottom order . 
44 
45 
Parameters : 
46 
- self : mandatory reference to this object 
47 
48 
Returns : 
49 
the next value in this image since the last iteration . 
50 
51 
✬✬✬ 
52 
if self . _iter_r < self . size [1]: 
# Iteration within image bounds . 
53 
# Save current value as per iteration variables . Update the 
54 
# variables for the next iteration as per the iteration 
55 
# order . Return saved value . 
56 
value = self . get ( self . _iter_r , self . _iter_c ) 
57 
self . _iter_c += 1 
58 
if self . _iter_c == self . size [0]: 
Page 9 of 20CS 201 Data Structures II Homework 1: Lists Spring 2023 
59 
self . _iter_c = 0 
60 
self . _iter_r += 1 
61 
return value 
62 
else : 
# Image bounds exceeded , end of iteration . 
63 
# Reset iteration variables , end iteration . 
64 
self . _iter_r = self . _iter_c = 0 
65 
raise StopIteration 
66 
67 
def _get_index ( self , r: int , c: int) -> int : 
68 
""" Returns the list index for the given row , column 
coordinates . 
69 
70 
This is an internal function for use in class methods only . It should 
71 
not be used or called from outside the class . 
72 
73 
Parameters : 
74 
- self : mandatory reference to this object 
75 
- r: the row coordinate 
76 
- c: the column 
coordinate 
77 
78 
Returns : 
79 
the list index co rr es po nd in g to the given row and column 
coordinates 
80 
""" 
81 
# Confirm bounds , compute and return list index . 
82 
width , height = self . size 
83 
assert 0 <= r < height and 0 <= c < width , " Bad image coordinates : "\ 
84 
f"(r, c): ({r}, {c}) for image of size : { self . size }" 
85 
return r* width + c 
86 
87 
def open ( path : str ) -> ✬MyImage ✬: 
88 
""" Creates and returns an image containing from the information at file path . 
89 
90 
The image format is inferred from the file name . The read image is 
91 
converted to RGB as our type only stores RGB . 
92 
93 
Parameters : 
94 
- path : path to the file containing image information 
95 
96 
Returns : 
97 
the image created using the information from file path . 
98 
""" 
99 
# Use PIL to read the image information and store it in our instance . 
100 
img : Image = Image . open ( path ) 
101 
myimg : MyImage = MyImage ( img . size ) 
102 
# Covert image to RGB . https :// s ta ck ove rf lo w . com /a/ 11064935 / 1382487 
103 
img : Image = img . convert (✬RGB ✬) 
104 
# Get list of pixel values 
( https :// st ac ko ve rf low . com /a/ 1109747 / 1382487 ), 
105 
# copy to our instance and return it . 
106 
for i , rgb in enumerate ( list ( img . getdata () )): 
107 
myimg . pixels . set (i , rgb ) 
108 
return myimg 
109 
110 
def save ( self , path : str ) -> None : 
111 
""" Saves the image to the given file path . 
112 
113 
The image format is inferred from the file name . 
114 
115 
Parameters : 
116 
- self : mandatory reference to this object 
117 
- path : the image has to be saved here . 
118 
119 
Returns : 
120 
none 
121 
""" 
122 
# Use PIL to write the image . 
123 
img : Image = Image . new (" RGB ", self . size ) 
124 
img . putdata ([ rgb for rgb in self . pixels ]) 
Page 10 of 20CS 201 Data Structures II Homework 1: Lists Spring 2023 
125 
img . save ( path ) 
126 
127 
def get ( self , r: int , c: int ) -> (int , int , int ): 
128 
""" Returns the value of the pixel at the given row and column 
coordinates . 
129 
130 
Parameters : 
131 
- self : mandatory reference to this object 
132 
- r: the row coordinate 
133 
- c: the column 
coordinate 
134 
135 
Returns : 
136 
the stored RGB value of the pixel at the given row and column 
coordinates . 
137 
""" 
138 
return self . pixels [ self . _get_index (r , c)] 
139 
140 
def set( self , r: int , c: int , rgb: (int , int , int )) -> None : 
141 
""" Write the rgb value at the pixel at the given row and column 
coordinates . 
142 
143 
Parameters : 
144 
- self : mandatory reference to this object 
145 
- r: the row coordinate 
146 
- c: the column 
coordinate 
147 
- rgb : the rgb value to write 
148 
149 
Returns : 
150 
none 
151 
""" 
152 
self . pixels [ self . _get_index (r , c)] = rgb 
153 
154 
def show ( self ) -> None : 
155 
""" Display the image in a GUI window . 
156 
157 
Parameters : 
158 
159 
Returns : 
160 
none 
161 
""" 
162 
# Use PIL to display the image . 
163 
img : Image = Image . new (" RGB ", self . size ) 
164 
img . putdata ([ rgb for rgb in self . pixels ]) 
165 
img . show () 
Code Listing 1: Image Type 
Page 11 of 20CS 201 Data Structures II Homework 1: Lists Spring 2023 
B 
MyList 
1 import array as arr 
2
3 class MyList : 
4 
✬✬✬A list interface . Also implements Iterator functions in order to support 
5 
iteration over this list . 
6 
✬✬✬ 
7
8 
def __init__ ( self , size : int , value = None ) -> None : 
9 
""" Creates a list of the given size , optionally intializing elements to value . 
10 
11 
The list is static . It only has space for size elements . 
12 
13 
Parameters : 
14 
- self : mandatory reference to this object 
15 
- size : size of the list ; space is reserved for these many elements . 
16 
- value : the optional initial value of the created elements . 
17 
18 
Returns : 
19 
none 
20 
""" 
21 
self . lst_arr = 
[ value ] * size 
22 
23 
def __len__ ( self ) -> int : 
24 
✬✬✬ Returns the size of the list . Allows len () to be called on it. 
25 
26 
Ref : https :// st ac ko ve rf lo w . com /q/ 7642434 / 1382487 
27 
28 
Parameters : 
29 
- self : mandatory reference to this object 
30 
31 
Returns : 
32 
the size of the list . 
33 
✬✬✬ 
34 
return len ( self . lst_arr ) 
35 
36 
def __getitem__ ( self , i: int): 
37 
✬✬✬ Returns the value at index , i. Allows indexing syntax . 
38 
39 
Ref : https :// st ac ko ve rf lo w . com /a/ 33882066 / 1382487 
40 
41 
Parameters : 
42 
- self : mandatory reference to this object 
43 
- i: the index from which to retrieve the value . 
44 
45 
Returns : 
46 
the value at index i. 
47 
✬✬✬ 
48 
# Ensure bounds . 
49 
assert 0 <= i < len ( self ) ,\ 
50 
f✬Getting invalid list index {i} from list of size { len ( self )} ✬ 
51 
return self . lst_arr [i] 
52 
53 
def __setitem__ ( self , i: int , value ) -> None : 
54 
✬✬✬ Sets the element at index , i , to value . Allows indexing syntax . 
55 
56 
Ref : https :// st ac ko ve rf lo w . com /a/ 33882066 / 1382487 
57 
58 
Parameters : 
59 
- self : mandatory reference to this object 
60 
- i: the index of the elemnent to be set 
61 
- value : the value to be set 
62 
63 
Returns : 
64 
none 
Page 12 of 20CS 201 Data Structures II Homework 1: Lists Spring 2023 
65 
✬✬✬ 
66 
# Ensure bounds . 
67 
assert 0 <= i < len ( self ) ,\ 
68 
f✬Setting invalid list index {i} in list of size { len ( self )} ✬ 
69 
self . lst_arr [i] = value 
70 
71 
def __iter__ ( self ) -> ✬MyList ✬: 
72 
✬✬✬ Iterator function to return an iterator 
( self ) that allows iteration over 
73 
this list . 
74 
75 
Parameters : 
76 
- self : mandatory reference to this object 
77 
78 
Returns : 
79 
an iterator 
( self ) that allows iteration over this list . 
80 
✬✬✬ 
81 
# Initialize iteration index . 
82 
self . _iter_index : int = 0 
83 
return self 
84 
85 
def __next__ ( self ): 
86 
✬✬✬✬ Iterator function to return the next value from this list . 
87 
88 
Parameters : 
89 
- self : mandatory reference to this object 
90 
91 
Returns : 
92 
the next value in this list since the last iteration . 
93 
✬✬✬ 
94 
if self . _iter_index < len ( self ): 
95 
value = self . get ( self . _iter_index ) 
96 
self . _iter_index += 1 
97 
return value 
98 
else : 
99 
# End of Iteration 
100 
self . _index = 0 
101 
raise StopIteration 
102 
103 
def get ( self , i: int ): 
104 
✬✬✬ Returns the value at index , i. 
105 
106 
Alternate to use of indexing syntax . 
107 
108 
Parameters : 
109 
- self : mandatory reference to this object 
110 
- i: the index from which to retrieve the value . 
111 
112 
Returns : 
113 
the value at index i. 
114 
✬✬✬ 
115 
return self [i] 
116 
117 
def set( self , i: int , value ) -> None : 
118 
✬✬✬ Sets the element at index , i , to value . 
119 
120 
Alternate to use of indexing syntax . 
121 
122 
Parameters : 
123 
- self : mandatory reference to this object 
124 
- i: the index of the elemnent to be set 
125 
- value : the value to be set 
126 
127 
Returns : 
128 
none 
129 
✬✬✬ 
130 
self [i] = value 
Page 13 of 20CS 201 Data Structures II Homework 1: Lists Spring 2023 
131 
132 
133 class ArrayList ( MyList ): 
134 
✬✬✬A list interface . Also implements Iterator functions in order to support 
135 
iteration over this list . 
136 
✬✬✬ 
137 
138 
def __init__ ( self , size : int , value = None ) -> None : 
139 
""" Creates a list of the given size , optionally intializing elements to value . 
140 
141 
The list is static . It only has space for size elements . 
142 
143 
Parameters : 
144 
- self : mandatory reference to this object 
145 
- size : size of the list ; space is reserved for these many elements . 
146 
- value : the optional initial value of the created elements . 
147 
148 
Returns : 
149 
none 
150 
""" 
151 
self . arr_red = arr . array (✬i✬, [ value [0] for i in range ( size )]) 
152 
self . arr_green = arr . array (✬i✬, [ value [1] for i in range ( size )]) 
153 
self . arr_blue = arr . array (✬i✬, [ value [2] for i in range ( size )]) 
154 
155 
def __len__ ( self ) -> int : 
156 
✬✬✬ Returns the size of the list . Allows len () to be called on it. 
157 
158 
Ref : https :// st ac ko ve rf lo w . com /q/ 7642434 / 1382487 
159 
160 
Parameters : 
161 
- self : mandatory reference to this object 
162 
163 
Returns : 
164 
the size of the list . 
165 
✬✬✬ 
166 
return len ( self . arr_blue ) 
167 
168 
def __getitem__ ( self , i: int): 
169 
✬✬✬ Returns the value at index , i. Allows indexing syntax . 
170 
171 
Ref : https :// st ac ko ve rf lo w . com /a/ 33882066 / 1382487 
172 
173 
Parameters : 
174 
- self : mandatory reference to this object 
175 
- i: the index from which to retrieve the value . 
176 
177 
Returns : 
178 
the value at index i. 
179 
✬✬✬ 
180 
# Ensure bounds . 
181 
assert 0 <= i < len ( self ) ,\ 
182 
f✬Getting invalid list index {i} from list of size { len ( self )} ✬ 
183 
return 
(( self . arr_red [i], self . arr_green [i], self . arr_blue [i])) 
184 
185 
def __setitem__ ( self , i: int , value ) -> None : 
186 
✬✬✬ Sets the element at index , i , to value . Allows indexing syntax . 
187 
188 
Ref : https :// st ac ko ve rf lo w . com /a/ 33882066 / 1382487 
189 
190 
Parameters : 
191 
- self : mandatory reference to this object 
192 
- i: the index of the elemnent to be set 
193 
- value : the value to be set 
194 
195 
Returns : 
196 
none 
Page 14 of 20CS 201 Data Structures II Homework 1: Lists Spring 2023 
197 
✬✬✬ 
198 
# Ensure bounds . 
199 
assert 0 <= i < len ( self ) ,\ 
200 
f✬Setting invalid list index {i} in list of size { len ( self )} ✬ 
201 
self . arr_red [i] = value [0]; self . arr_green [i] = value [1]; self . arr_blue [i] = value [2 
] 
Code Listing 2: List Type 
Page 15 of 20CS 201 Data Structures II Homework 1: Lists Spring 2023 
C Image Operations 
1 from src . myimage import MyImage 
2
3 def remove_channel ( src: MyImage , red : bool = False , green : bool = False , 
4 
blue : bool = False ) -> MyImage : 
5 
""" Returns a copy of src in which the indicated channels are suppressed . 
6
7 
Suppresses the red channel if no channel is indicated . src is not modified . 
8
9 
Args : 
10 
- src : the image whose copy the indicated channels have to be suppressed . 
11 
- red : suppress the red channel if this is True . 
12 
- green : suppress the green channel if this is True . 
13 
- blue : suppress the blue channel if this is True . 
14 
15 
Returns : 
16 
a copy of src with the indicated channels suppressed . 
17 
""" 
18 
src_copy = MyImage ( src . size ) 
19 
rows = src . size [1] 
20 
cols = src . size [0] 
21 
for row in range ( rows ): 
22 
for col in range ( cols ): 
23 
src_copy . set( row , col , src . get ( row , col )) 
24 
25 
if red == False and green == False and blue == False : 
26 
for row in range ( rows ): 
27 
for col in range ( cols ): 
28 
temp = list ( src_copy . get ( row , col )) ; temp [0] = 0 
29 
src_copy . set ( row , col , tuple ( temp ) ) 
30 
else : 
31 
for row in range ( rows ): 
32 
for col in range ( cols ): 
33 
temp = list ( src_copy . get ( row , col )) 
34 
if red == True : temp [0] = 0 
35 
if green == True : temp [1] = 0 
36 
if blue == True : temp [2] = 0 
37 
src_copy . set ( row , col , tuple ( temp ) ) 
38 
return src_copy 
39 
40 def convert_to_matrix ( lst , m , n): # converts a flattened r e p r e s e n t a t i o n into an mxn matrix 
such that m and n are known 
41 
mat = 
[] 
42 
for i in range (0 , len ( lst ) , n): 
43 
mat . append ( lst[i:i+n]) 
44 
return mat[:m] 
45 
46 def rotate_90 ( matrix ): # Rotates a given m x n matrix 90 degress clockwise 
47 
res = 
[] 
48 
for i in range ( len ( matrix [0]) ): 
49 
lst = 
[] 
50 
for j in range ( len ( matrix )): 
51 
lst . append ( matrix [j][i]) 
52 
# Reversing the matrix for 90 degree 
53 
lst . reverse () 
54 
res . append ( lst ) 
55 
return res 
56 
57 def rotations ( src: MyImage ) -> MyImage : 
58 
""" Returns an image containing the 4 rotations of src . 
59 
60 
The new image has twice the dimensions of src . src is not modified . 
61 
62 
Args : 
63 
- src : the image whose rotations have to be stored and returned . 
Page 16 of 20CS 201 Data Structures II Homework 1: Lists Spring 2023 
64 
65 
Returns : 
66 
an image twice the size of src and containing the 4 rotations of src . 
67 
""" 
68 
rows = src . size [1] 
69 
cols = src . size [0] 
70 
src_copy = MyImage (( cols * 2 , rows * 2)) 
71 
rot_90_lst = 
[] 
72 
rot_180_lst = 
[] 
73 
rot_270_lst = 
[] 
74 
rot_360_lst = 
[] 
75 
temp = 
[] 
76 
77 
for row in range ( rows ): 
78 
for col in range ( cols ): 
79 
temp . append ( src . get ( row , col ) ) 
80 
rot_360_lst = convert_to_matrix ( temp , rows , cols ) #Og image 
81 
# 90 degree clockwise rotation 
82 
rot_90_lst = rotate_90 ( rot_360_lst ) 
83 
# Image - 180 
84 
rot_180_lst = rotate_90 ( rot_90_lst ) 
85 
# Image - 90 a nt ic lo ck wi se 
86 
rot_270_lst = rotate_90 ( rot_180_lst ) 
87 
src_copy_lst = 
[] 
88 
for i in range ( rows * 2): 
89 
if i < rows : 
90 
for x in range ( len ( rot_270_lst [i]) ): 
91 
src_copy_lst . append ( rot_270_lst [i][x]) 
92 
for x in range ( len ( rot_360_lst [i]) ): 
93 
src_copy_lst . append ( rot_360_lst [i][x]) 
94 
else : 
95 
for x in range ( len ( rot_180_lst [i % rows ]) ): 
96 
src_copy_lst . append ( rot_180_lst [i % rows ][x]) 
97 
for x in range ( len ( rot_90_lst [i % rows ])): 
98 
src_copy_lst . append ( rot_90_lst [i % rows ][x]) 
99 
lst1 = convert_to_matrix ( src_copy_lst , rows *2 , cols *2 ) 
100 
for row in range ( rows *2): 
101 
for col in range ( cols *2): 
102 
src_copy . set( row , col , lst1 [ row ][ col ]) 
103 
return src_copy 
104 
105 def resize ( src : MyImage ) -> MyImage : 
106 
""" Returns an image which has twice the dimensions of src . 
107 
108 
The new image has twice the dimensions of src . src is not modified . 
109 
110 
Args : 
111 
- src : the image which needs to be resized . 
112 
113 
Returns : 
114 
an image twice the size of src . 
115 
""" 
116 
rows = src . size [1] 
117 
cols = src . size [0] 
118 
src_copy = MyImage (( cols * 2 , rows * 2)) 
119 
for row in range ( rows ): 
120 
for col in range ( cols ): 
121 
src_copy . set( row *2 , col *2 , src . get ( row , col )) 
122 
for row in range ( cols *2): 
123 
for col in range ( rows * 2): 
124 
if row % 2 == 0: # All even rows - not black rows 
125 
if col % 2 == 1: 
126 
if col == ( cols * 2) - 1: # The last column - edge case 
127 
pix = src_copy . get ( row , col - 1 ) 
128 
src_copy . set ( row , col , pix ) 
129 
else : 
Page 17 of 20CS 201 Data Structures II Homework 1: Lists Spring 2023 
130 
pix1 = src_copy . get ( row , col -1) 
131 
pix2 = src_copy . get ( row , col +1) 
132 
pix = (( pix1 [0] + pix2 [0]) // 2 , ( pix1 [1] + pix2 [1]) // 2 , ( pix1 [2] + 
pix2 [2]) // 2 ) 
133 
src_copy . set ( row , col , pix ) 
134 
else : pass 
135 
if row % 2 == 1: # Black rows 
136 
if col % 2 == 0: # Not completely black columns 
137 
if row == ( rows * 2) - 1: # Last row - edge case 
138 
pix = src_copy . get ( row - 1 , col ) 
139 
src_copy . set ( row , col , pix ) 
140 
else : 
141 
pix1 = src_copy . get ( row - 1 , col ) 
142 
pix2 = src_copy . get ( row + 1 , col ) 
143 
pix = (( pix1 [0] + pix2 [0]) // 2 , ( pix1 [1] + pix2 [1]) // 2 , ( pix1 [2] 
+ pix2 [2]) // 2) 
144 
src_copy . set ( row , col , pix ) 
145 
if col % 2 == 1: 
146 
if col == ( cols * 2) - 1: 
147 
pix = src_copy . get ( row , col - 1 ) 
148 
src_copy . set ( row , col , pix ) 
149 
else : 
150 
if row 
!= ( rows * 2) - 1: 
151 
pix1 = src_copy . get (( row - 1) , ( col - 1 )) 
152 
pix2 = src_copy . get (( row - 1) , ( col + 1 )) 
153 
pix3 = src_copy . get (( row + 1) , ( col + 1 )) 
154 
pix4 = src_copy . get (( row + 1) , ( col - 1 )) 
155 
pix = (( pix1 [0] + pix2 [0] + pix3 [0] + pix4 [0]) // 4 , ( pix1 [1] + 
pix2 [1] + pix3 [1] 
+ pix4 [1]) // 4 , ( 
pix1 [2] + pix2 [2] 
+ pix3 [2] + pix4 [2 
]) // 4) 
156 
src_copy . set( row , col , pix ) 
157 
158 
for row in range ( rows * 2): 
159 
for col in range ( cols * 2): 
160 
if row % 2 == 1 and col % 2 == 1: 
161 
if col == ( cols * 2) - 1: # Edge case - last col 
162 
pix = src_copy . get ( row , col - 1 ) 
163 
src_copy . set ( row , col , pix ) 
164 
elif row == ( row * 2) - 1: # Edge case - last row 
165 
pix = src_copy . get ( row - 1 , col ) 
166 
src_copy . set ( row , col , pix ) 
167 
else : 
168 
if row 
!= ( rows * 2) - 1: 
169 
pix1 = src_copy . get (( row - 1) , ( col - 1 )) 
170 
pix2 = src_copy . get (( row - 1) , ( col + 1 )) 
171 
pix3 = src_copy . get (( row + 1) , ( col + 1 )) 
172 
pix4 = src_copy . get (( row + 1) , ( col - 1 )) 
173 
pix = (( pix1 [0] + pix2 [0] + pix3 [0] + pix4 [0]) // 4 , ( pix1 [1] + pix2 [1 
] + pix3 [1] + pix4 [1]) 
// 4 , ( pix1 [2] + pix2 
[2] + pix3 [2] + pix4 [2 
]) // 4) 
174 
src_copy . set ( row , col , pix ) 
175 
else : 
176 
pix1 = src_copy . get ( row , col - 1) 
177 
pix2 = src_copy . get ( row , col + 1) 
178 
pix = (( pix1 [0] + pix2 [0]) // 2 , ( pix1 [1] + pix2 [1]) // 2 , ( pix1 [2] 
+ pix2 [2]) // 2) 
179 
src_copy . set ( row , col , pix ) 
180 
return src_copy 
181 
182 def maskreader ( maskfile ): # Reads the maskfile and returns a list with values of maskfile 
183 
✬✬✬ 
Page 18 of 20CS 201 Data Structures II Homework 1: Lists Spring 2023 
184 
Returns a tuple of mask list and length . 
185 
This is a helper function that is used in apply_mask function to read 
186 
the mask file and return a list of n by n. 
187 
188 
maskfile is a text file containing n by n mask . 
189 
190 
Args : 
191 
- maskfile : path to file specifying mask 
192 
193 
Returns : 
194 
Tuple of lst of n by n and length 
195 
✬✬✬ 
196 
f = open ( maskfile , ✬r✬); 
197 
lst = 
[] 
198 
for i in f: 
199 
lst . append (int( i)) 
200 
mat_len = lst [0]; mask_lst = lst [1::] 
201 
f. close () 
202 
return 
( mask_lst , mat_len ) 
203 
204 def apply_mask ( src : MyImage , maskfile : str , average : bool = True ) -> MyImage : 
205 
""" Returns an copy of src with the mask from maskfile applied to it. 
206 
207 
maskfile specifies a text file which contains an n by n mask . It has the 
208 
following format : 
209 
- the first line contains n 
210 
- the next n^2 lines contain 1 element each of the flattened mask 
211 
212 
Args : 
213 
- src : the image on which the mask is to be applied 
214 
- maskfile : path to a file specifying the mask to be applied 
215 
- average : if True , averaging should to done when applying the mask 
216 
217 
Returns : 
218 
an image which the result of applying the specified mask to src . 
219 
""" 
220 
rows = src . size [1]; cols = src . size [0] 
221 
src_copy = MyImage ( src . size ) 
222 
# for row in range ( rows ): 
223 
# 
for col in range ( cols ): 
224 
# 
src_copy . set (row , col , src . get (row , col )) 
225 
vals = maskreader ( maskfile ) 
226 
mask_lst = vals [0]; n = vals [1] 
227 
# print (f" Mask list : { mask_lst } \n length = {n} \n center at { center } with value { 
mask_lst [ center ]}") 
228 
for i , pixels in enumerate ( src ): 
229 
row , col = divmod (i , cols ) # gives row index with co rre sp on di ng 
column index to 
iterate over 
230 
# print (row , col ) 
231 
val = 0; total = 0 
232 
for x in range ( n): 
233 
for y in range ( n): 
234 
mask_row = x - (n // 2) # Computing row mask 
235 
mask_col = y - (n // 2) # Computing col mask 
236 
if row + mask_row >= 0 and row + mask_row < rows and col + mask_col >= 0 and 
col + mask_col < cols : 
237 
total += mask_lst [n * x + y] 
238 
pix = src . get ( row + mask_row , col + mask_col ) 
239 
# print (f" Row { row } 
Col { col } 
RowMask { mask_row } 
ColMask { mask_col } 
pixel { pix }") 
240 
val += (( pix [0] + pix [1] + pix [2]) ) // 3 * mask_lst [n * x + y] 
241 
if average == True : val = val // total 
242 
if val > 255 : val = 255 
243 
if val < 0: val = 0 
244 
src_copy . set ( row , col , ( val , val , val )) 
245 
return src_copy 
Page 19 of 20CS 201 Data Structures II Homework 1: Lists Spring 2023 
Code Listing 3: Image Operations 
Page 20 of 20