CS201 Homework 2 -Solved

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. 
1. 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 
2. 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