Description

Magic List Goal The goal of this assignment is to get some practice with data structure implementation and usage in python. In Part (a) of the assignment you have to complete some functions of the Magic List data structure. In Part (b) of the assignment you have to use a Magic List to solve the given problem. Part (a) - Magic List Magic List is a special type of list L in which the elements are arranged according to the following properties : 1. The first element of the list is always 0 (L[0] = 0). 2. For each index i (>= 1), L[i] <= L[2i] and L[i] <= L[2i+1]. 3. For each index i (>= 1), L[i/2] is called the parent of L[i], and L[2i], L[2i+1] are called the children of L[i]. 4. L[1] has no parent. In this list, all the elements besides the first one are called magic elements. The size of Magic List is the number of magic elements in the list. Observe that L[1] will be the smallest magic element in list (Due to point 2. above). A class called MagicList has been given to you (inside MagicList.py). You have to complete the following functions inside the file : 1. findMin Complete the findMin function and return the smallest magic element in the Magic List. If there are no magic elements (i.e. size of Magic List is zero), then return None. 2. insert Complete the insert function and return the modified list. To insert an element in the Magic List, first append the element to the end of the list. Start at last element and keep comparing with parent L[i/2]. If parent is larger, swap the parent and the element. Keep doing this till parent is smaller, or the element has no parent. 3. deleteMin Complete the deleteMin function, delete the smallest magic element in the Magic List, and return the modified list. To delete the minimum element, swap the minimum element (E1) with the last element (E2) and remove the last element. Keep comparing E2 with children L[2i] and L[2i+1] and swap with the smaller child. Keep doing this till both children are greater than E2 or E2 has no more children. Part (b) - k-sum In this part, you have to complete the function k-sum. The function takes a list L and an integer K as input, and you need to find the sum of smallest K elements of the list. You need to do this with the help of a Magic List. To convert the input list L into a Magic list, you can start with an empty MagicList M and insert all the elements of L into M (Code given below). Then use M to find the sum of smallest K elements and return the sum. Note that K <= size of L 1. # Convert a list L to Magic List M 2. M = MagicList () 3. for i in L : 4. M. insert ( i ) 5. # M now contains all elements of L Testing The given code contains a few test cases for each function. You need to ensure that each test case passes correctly. Do not change anything in the code except completing the given functions. Submission You need to submit completed MagicList.py on moodle. Grading would be done on the basis of a demo (viva). You should be able to run your code using python3 during the demo. What is allowed? What is not? 1. This is an individual assignment. 2. Your code must be your own. You are not to take guidance from any general purpose code or problem specific code meant to solve these or related problems. 3. We will run plagiarism detection software. Anyone found guilty will be awarded a suitable penalty as per IIT rules.