Description
Dynamic List ADT
In this assignment, you will implement a dynamic list ADT in Python that allows for inserting and deleting
elements at a specified index and retrieving elements at a specified index. The list should be implemented
as both a dynamic array and a linked list.
1 Implementation Details and Tasks
❼ Implement the DynamicArrayList and LinkedList classes in the accompanying file, listadt.py, in
the accompanying src/ sub-folder.
❼ In the DynamicArrayList and LinkedList classes, implement the following methods:
– insert(index, value): inserts value at the specified index
– delete(index): deletes the element at the specified index
– get(index): returns the element at the specified index
– size(): returns the number of elements in the list
– display(): returns the string representation of the list
❼ The dynamic array should be implemented using Python arrays. Upon creation, the dynamic array
will have a size of one, and all empty items will be initialised as -1.
❼ The dynamic array should dynamically resize itself when necessary to ensure efficient use of memory
i.e., the array should double it’s size when it is full and reduce by half once it is quarter
the size of array.
❼ The cost of resizing the array should be linear in the size of the array.
❼ The linked list should be implemented as a singly linked list.
❼ The program should take as an input a file that specifies which data structure should be used to
implement the dynamic list ADT and which operations should be performed on the list.
❼ The program should read the input file, create the appropriate data structure, and perform the specified
operations. The program should then output the result of each operation.
❼ The function load which parses the input file and saves the output of the program to a given file, has
already been implented in the accompanying file, listadt.py, in the accompanying src/ sub-folder.
1CS 201, Spring 2023 HW 2: Skiplists and Dynamic List ADT L5 – Group 3
1.1 Input and Output
The input file will specify which data structure should be used to implement the Dynamic List ADT and
which operations should be performed on the list. The input file will have the following format:
<data s t r u c t u r e >
<o p e r a ti o n> <arg1> <arg2>
❼ ⟨data structure⟩ is either array or linkedlist, indicating which data structure should be used to
implement the Dynamic List ADT
❼ ⟨ operation⟩ is one of the following:
– insert: Insert an item into the list. The ⟨arg1⟩ is the index at which to insert the item and ⟨arg2⟩
is the item to be inserted.
– delete: Delete an item from the list. The ⟨arg1⟩ is the index of the item to be deleted.
– get: Return the item at the specified index in the list. The ⟨arg1⟩ is the index of the item to be
returned.
– size: Return the number of items in the list.
– display: Return the string representation of the list.
The output of the program will be the result of each operation, one per line.
1.2 Example
In the following examples, the input file specifies which data structure should be used to implement the
Dynamic List ADT. The program then performs the specified operations on the list and outputs the result
of each operation.
1.2.1 Linked List
l i n k e d l i s t
i n s e r t 0 10
i n s e r t 0 20
i n s e r t 1 30
g e t 0
g e t 1
g e t 2
d e l e t e 1
s i z e
d i s pl a y
Code Listing 1: Sample input file for creating a LinkedList
20
30
10
2
[ 2 0 , 1 0]
Code Listing 2: Sample output generated by the program
Page 2 of 9CS 201, Spring 2023 HW 2: Skiplists and Dynamic List ADT L5 – Group 3
1.2.2 Dynamic Array List
a r r a y
i n s e r t 0 10
d i s pl a y
i n s e r t 0 15
d i s pl a y
i n s e r t 1 5
d i s pl a y
s i z e
i n s e r t 2 30
d i s pl a y
d e l e t e 1
d i s pl a y
d e l e t e 1
d i s pl a y
s i z e
d e l e t e 1
d i s pl a y
Code Listing 3: Sample input file for creating a DynamicArrayList
[ 1 0 ]
[ 1 5 , 1 0]
[ 1 5 , 5 , 1 0 , ❂1]
3
[ 1 5 , 5 , 3 0 , 1 0]
[ 1 5 , 3 0 , 1 0 , ❂1]
[ 1 5 , 1 0 , ❂1, ❂1]
2
[ 1 5 , ❂1]
Code Listing 4: Sample output generated by the program
1.3 Testing
Once you have successfully implemented the DynamicArrayList and LinkedList classes, you can test your
code by reading from the accompanying data file, data/input.txt, and performing operations on the list
adt. For grading purposes, your submission will be tested automatically by GitHub using the accompanying
pytest file, test listadt.py.
Page 3 of 9CS 201, Spring 2023 HW 2: Skiplists and Dynamic List ADT L5 – Group 3
Part II
Skiplists
The solutions to the problems in this part are to be entered inline below. Remove all the other parts and
sections from this document. Enter your team name as the author in the document’s title.
- A Ranked Set
[10 points]
1 Design a version of a skiplist that implements the SSet interface, but also allows fast access to elements
by rank. That is, it also supports the function get(i), which returns the element whose rank is i in
O(log n) expected time. (The rank of an element x in an SSet is the number of elements in the SSet
that are less than x.) Describe how your version differs from a regular skiplist and provide pseudocode
of find(x) and get(i) for this version.
Solution:
To allow for faster access to elements by rank we can alter the regular skiplist such that it keeps track
of the size of the sublist rooted at each node. This will allow us to minimize the time complexity of
get() operation, which returns the element at a given index in the sorted set.
In this altered version we would include two additional pieces of information for each node:
❼ size: the number of elements in each sublist starting at the node
❼ rank: the rank of the node in the SSet, computed using the size
In a regular skiplist, to find the element at a given index, one would need to traverse the list from
the beginning until reaching the desired index. This would take O(n) time, where n is the number
of elements in the set. However, in this altered version of the skiplist, the size of each subtree is
stored at each node, so we can use this information to efficiently locate the element at the given
index.
To do this, we start at the sentinel node and traverse the skiplist, keeping track of the rank of
each node (the total number of elements visited so far, including the subtree sizes). When we reach
a node whose rank equals the desired index, we return its element. This takes O log(n) time on
average, where n is the number of elements in the set.
While this version of skiplist is similar to a regular skiplist in that it uses a linked list with multiple
levels of nodes to provide efficient search, insertion, and deletion operations, it differs in that it
maintains subtree sizes and uses them to efficiently support the get() operation.
The pseudocode of find(x) for this version is given below:
1
def find_pred_node (x):
2
u = sentinel
3
r = h
4
while r >= 0:
5
while u. next [r] is not None and u . next [r].x < x:
6
u = u . next [r]
# go right in
list r
7
r -= 1
# go down
into list r -1
8
return u
9
10
def find ( x):
11
u = find_pred_node ( x)
12
if u. next [0] is None :
13
return None
14
return u. next [0].x
1Adapted from Exercise 4.9 in the textbook.
Page 4 of 9CS 201, Spring 2023 HW 2: Skiplists and Dynamic List ADT L5 – Group 3
The pseudocode of get(i) for this version is given below:
1
def get (i ):
2
if i < 0 or i >= n:
3
raise IndexError ()
4
u = sentinel
5
r = h
6
rank = 0
7
while True :
8
while u. next [r] is not None and rank + u . next [r]. size <= i:
9
rank += u. next [r]. size
10
u = u. next [r]
11
if rank == i:
12
return u.x
13
r -= 1
In both the functions for the modified SSetSkipList, the average time complexity for both find(x)
and get(i) is O log(n).
Page 5 of 9CS 201, Spring 2023 HW 2: Skiplists and Dynamic List ADT L5 – Group 3
- Finger Search
[10 points]
2 A finger in a skiplist is an array that stores the sequence of nodes on a search path at which the search
path goes down. (The variable stack in the add(x) code on page 87 is a finger; the shaded nodes in
Figure 4.3 show the contents of the finger.) One can think of a finger as pointing out the path to a node
in the lowest list, L0.
A finger search implements the find(x) operation using a finger, walking up the list using the finger
until reaching a node u such that u.x < x and u.next = nil or u.next.x > x and then performing a
normal search for x starting from u. It is possible to prove that the expected number of steps required
for a finger search is O(1 + log r), where r is the number values in L0 between x and the value pointed
to by the finger.
Design, i.e. provide the necessary pseudo code for, a version of a skiplist that implements find(x)
operations using an internal finger. This subclass stores a finger, which is then used so that every
find(x) operation is implemented as a finger search. During each find(x) operation the finger is
updated so that each find(x) operation uses, as a starting point, a finger that points to the result of
the previous find(x) operation.
Solution:
To implement a skiplist that uses an internal finger for find(x) operations, we can store the finger
as an attribute of the skiplist. Whenever a find(x) operation is performed, we first use the finger
to perform a finger search and then update the finger to point to the node found by the search.
The find(x) method traverses the skip list from the highest level to the lowest level, moving the
current node pointer down to the next node in the list until it finds a node with a value greater
than or equal to the search value x. If it finds a node with a value equal to x, it returns True and
resets the finger to the head. Otherwise, it updates the finger to point to the last node before x and
returns False. This is done so we are able to use the finger for subsequent find(x) operations and
the only way we can guarantee that the finger points to a valid node is if it points to the node just
before x.
The pseudocode for this version of find(x) is given below:
1
class FingerSkipList :
2
initialize ():
3
head = fsl . Node ( None )
4
finger =
[ head ] * max_level
5
6
def find ( x):
7
i = finger [-1]
# start at the node pointed to by
the finger
8
for level in reversed ( range ( len (i. next ) )):
9
while i. next [ level ] and i. next [ level ]. val < x:
10
i = i . next [ level ]
11
if i . next [0] and i. next [0]. val == x:
12
finger =
[ head ] * max_level
# reset the finger
to the head
13
return True
14
finger =
[ None ] * len (i. next ) +
[i]
15
# update the finger
to point to the last node before x
16
return False
2Adapted from Exercise 4.10 in the textbook.
Page 6 of 9CS 201, Spring 2023 HW 2: Skiplists and Dynamic List ADT L5 – Group 3
Part III
Implementing a Database Index using a
Skiplist
Figure 1: An index over the Name attribute of a table. The index stores values of the Name attribute as
keys with the associated value being the address of the corresponding record in the table.
You have learned about database indexes in CS 355 Database Systems. Indexes in databases are similar
to indexes in books. In a book, an index allows you to find information quickly without reading the entire
book. In a database, an index allows the database program to find data in a table without scanning the
entire table. An index in a book is a sorted list of words with the page numbers that contain each word. An
index in a database is a sorted list of key values with the storage locations of rows in the table that contain
the key value. Each key in the index is associated with a particular pointer to a record in the data file.
Figure 1 shows an index on the Name attribute of an Instructor table stored in a data file. Note that key
values in the figure are not sorted.
The most popular data structure used for indexing in relational databases is Btree (or its variant, such
as B+tree). Btrees rose to popularity because they do fewer disk I/O operations to run a lookup compared
to other balanced trees. SingleStore is the first commercial relational database in production today to use a
skiplist, not a Btree, as its primary index data structure for in-memory data [1].
You are given a data file, data/books.csv, that contains records of books. Each record contains the
following attributes:
❼ Book Code
❼ Title
❼ Category
❼ Price
❼ Number of Pages
For some of the attributes, all the values are unique. Such attributes can be used to index the table. Others
have repeating values and are thus unsuitable to be used for indexing.
2 Implementation Details and Tasks
You are required to provide the missing implementations for the methods in the files, skiplist.py and
db.py, in the accompanying src/ sub-folder. skiplist.py contains classes to implement a skiplist. db.py
Page 7 of 9CS 201, Spring 2023 HW 2: Skiplists and Dynamic List ADT L5 – Group 3
contains a Table class to store records which can be indexed using a skiplist. Every individual field in the
Table is stored as strings. Further details are provided in the doc strings in the files. The methods to be
implemented are identified with a pass in their body.
2.1 Requirement
You will need to install the typing module to support certain type hints used in the code.
2.2 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!
❼ Store each field that is read from file as a str.
❼ Store a record as a list of field values.
❼ Store a table as a collection of records.
❼ Make sure that the Table can be re-indexed during run-time.
❼ Take care that the keys for the index are the values of the specified attribute. And that the value
associated with each key is not the corresponding record, but a means to locate the record in the table.
❼ For the select_range query, think of an approach better than submitting multiple select queries.
2.3 Testing
Once you have successfully implemented the methods, you can test your code by reading from the accompa
nying data file, data/books.csv, and performing queries on it. For grading purposes, your submission will
be tested automatically by GitHub using the accompanying pytest file, test index.py.
Page 8 of 9CS 201, Spring 2023 HW 2: Skiplists and Dynamic List ADT L5 – Group 3
References
[1] The Story Behind SingleStore’s Skiplist Indexes,
https://www.singlestore.com/blog/
what-is-skiplist-why-skiplist-index-for-memsql/, last accessed on 16 Feb 2022.
Page 9 of 9
Habib University
Spring 2023
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
Page 3 of 20CS 201 Data Structures II Homework 1: Lists Spring 2023
(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 4×3 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.
- Implementation
Complete the tasks listed in Section 3.1 by providing the implementations in the indicated files.
- 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
- 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
