HW02: Filing and Piling Solution

1. Introduction

In this exercise, we will complete three functions to simulate three different methods for file organization.

 

2. Objectives

The purpose of this assignment is to help you:

•   Refresh knowledge on list and function in Python.

•   Refresh knowledge on reading files in Python.

•   Do a little bit study on different file organizing methods.

 

Note: Before you start, if you are not familiar with list, for loop or function in Python, you are recommended to review the sample codes we covered in lecture first.

 

3. Background

 

3.1. Filing and Piling

In our daily lives, we are always dealing with a lot of different files. As a college student, we need to organize our graded paper homework, exams, lecture notes etc. Some of us may just insert documents randomly into a big drawer and whenever we need to fetch a specific document in our storage, we may do a linear search1 starting from the leftmost document to the right. If we are careful enough, we cannot miss the one we want to find. After using the document, we may randomly insert the document back into the drawer. And whenever we need a certain document again, we can redo the linear search and  random insert process, which is simple but reliable.

 

Let’s consider the time complexity of the  random insert  and linear search. Random insert takes constant time since what we need to do is just to open the drawer and put the file in randomly. Nothing seems easier than that. But for  linear search, given a pile of documents, in order to

find a specific one, we have to check each of them  linearly starting from leftmost one up to the

one we want. So, how many documents do we have to pass before finding the one we want? If the documents are  randomly inserted into the pile, a certain document has an equal possibility

of locating at each position in the pile. So, if there are in total  𝒏    documents, the expected number of documents we have to pass before finding the specific one is around  𝒏  /𝟐 .

 

1 In this assignment, we assume linear search is always conducted from the leftmost location of the pile to right.

Here we can see that the time complexity of  linear search is strongly related to the way how documents are inserted into the pile. We may wonder, are there any other ways of insertions? Just simply recap how we are organizing things, the answer has to be yes. In this assignment, we will implement three other types of insertions (filing schemes) and compare their performance in file organization.

 

4. Assignment

In the skeleton zip file, you can find a skeleton code, named filing.py. All you need to do is to complete the skeleton code based on the following instructions and submit the filing.py

(together with  data.txt) to the Mimir system.

 

4.1. Leftmost Filing

Now, open the skeleton code. There are three functions for you to complete. The first function

is the leftmostfiling function, where people always insert the document to the leftmost position of the pile. The function’s skeleton is as the following:

 

def leftmostfiling(L):                   # L: list of document IDs acquired from the pile

M = [x for x in range(20)]       # initialize a pile of 20 documents: [0, 1, 2, …, 19]

count = 0                                  # sum of total number of docs checked before finding each doc in L

for l in L:

### add your code here return count

 

 

In the leftmostfiling function, we first initialize a pile of 20 documents in the form of list. The 20 documents in list  M are with their unique document IDs from 0 to 19 that initially piled up with ascending order from left to right. The parameter variable  L is the input of the function.  L contains a list of document IDs to be acquired from the pile. Variable count denotes the sum of total number of documents checked and passed before finding each required document in  L. In the for loop, we pick each document ID in  L, and update the  count and the pile list  M with leftmost filing scheme. The following is a simple example with  L = [4, 2, 2], where we will request Doc 4, Doc 2 and Doc 2 one by one.

 

First, we initialize the documents in  M with IDs from 0 to 19:

 

 

0        1        2       3        4        5        6

 

… …           17      18      19

 

Then, we need to find Doc 4 by using linear search from left to right in  M as the following:

 

 

0        1        2       3        4        5        6

 

… …           17

 

18      19

Here, we passed 4 documents Doc 0, Doc 1, Doc 2 and Doc 3 until we found Doc 4. So, we update the value of  count = 0 + 4 = 4.

 

After using Doc 4, we insert Doc 4 back to  M at the leftmost position,

 

 

4        0        1       2        3        5        6

 

… …            17

 

18      19

 

Then, we need to find Doc 2 in the new pile.

 

4        0        1       2        3        5        6          … …

 

17      18      19

Here, we passed 3 documents Doc 4, Doc 0, Doc 1 until we found Doc 2. And we update the value of  count = 4 + 3 = 7. Similarly, we insert Doc 2 back to  M as the following,

 

2        4        0       1        3        5        6          … …

 

17      18      19

 

According to  L, we request Doc 2 again, where we find Doc 2 is at the leftmost location of  M. so, we can simple update  count = 7 + 0 since we do not need to pass any document before we

find Doc 2.

 

2        4        0       1        3        5        6          … …

 

17      18      19

 

 

After going through the documents in  L one by one, we return the  count value 7.

 

In the test case, there can be a much longer  L, and what we need to do is to follow the same procedure, request each document in  L, update M and count in each iteration.

 

4.2. Rightmost Filing

The second function we need to implement is the rightmostfiling. The only difference between the leftmost filing and the rightmost filing is that we always insert the document to the

rightmost location of the pile. We will also need to calculate the count and return its value.

 

4.3. Fixed Filing

The third function we need to implement is the fixedfiling. Different from leftmost filing and rightmost filing, fixed filing always inserts the document to its original position in the pile. In term of time complexity, the fixed filing needs to pay efforts in both insertion and searching,

while leftmost and rightmost filing only takes time in searching since their insertion is too simple to count.

 

In fixed filing, for a certain requested document, we need to use  linear search to find the document in  M. When we end up using the document, we have to use  linear search again to get the file’s original location in the pile and put it back. So, here, in each iteration, we need to

use  linear search twice and the  count is somehow doubled.

 

After implementing the three filing methods, we can compare their performance with different file request patterns with different given test cases in the skeleton code. It is meaningful to mention that, in the first test case, the given code uses a file operation to read each line in file data.txt and save them in list  L. Very likely, in the near future, we need to write our own code

to implement different file operations.

 

L = [int(line) for line in open('data.txt')]

 

5. Submit your work to Mimir

Submit your code filing.py (together with  data.txt) to Mimir after you complete your code. The Mimir will automatically grade your submission based on different unit tests. You can submit your code to Mimir up to  30 times to refresh your existing score before the submission deadline.

 

6. Due date

This lab assignment is worth  4 points in the final grade. It will be due by  11:59pm on Tues. Sep

7. Getting help

Start your project early, because you will probably not be able to get timely help in the last few hours before the assignment is due.

•   Go to the office hours of instructors and TAs.

o Prof. Wei Wei: Mon. 2:30 - 3:15pm, Wed. 2:30 - 3:15pm, Thurs. 2:30 - 3:15pm, Fri. 2:30 - 3:15pm @ITE258

o Jenny Blessing: Fri. 12pm - 2pm @ITE140

o Param Bidja: Tues. 2pm - 3pm @ITE140

o Yamuna Rajan: Tues. 11am - 12pm, Wed. 9:30am – 10:30am @ITE140

o Zigeng Wang: Mon. 3pm - 4pm @ITE140

•     Post your questions on Piazza. TAs and many of your classmates may answer your questions.

•     Search the answer of your unknown questions on the Internet. Many questions asked by you might have been asked and answered many times online already.