Description
Important reminder
- You must submit your lab via web-submit.
- Please make sure you correctly submit your files (two files – py, MinMaxList.py).
- Please follow the instructions carefully – read the lab carefully to understand everything you need to do. This lab requires you to modify the MinMaxList that we have used in previous lectures.
- GOALS/OUTCOMES FOR LAB
– To practice multi-file programming with import. – To consider the efficiency with “insertion” vs. “sort.” – To continue to practice general programming.
- LAB 9 – TASK/INSTRUCTIONS
Task 0: [This will be the same for all labs]: Start your code with comments that include this lab’s ID, your full name, email address, and student id as follows. Note – add this information to both of your files.
This lab involves modifying the MinMaxList object to have two methods for getting the min and max element and an additional method called “printList().” You will also change how the insertItem() method is implemented. See Task 1 and Task 2 instructions.
A video of this lab is shown provided here:
https://www.eecs.yorku.ca/~mbrown/EECS1015_Lab9.mp4
This lab has two (2) tasks.
See the explanation of the lab on the next page
Lab 9 – Improving MinMaxList efficiency
STARTING CODE – main.py [https://trinket.io/python/44a3131856]
from MinMaxList import MinMaxList # Import MinMaxList from separate file from random import randint
# Main function is given. def main(): aList = MinMaxList([10, 11, 99, 1, 34, 88])
print(“–Insert Item–“) for i in range(30):
x = randint(1, 100)
aList.insertItem(x, True) # You need to modify insertItem (See Task 2)
print(“–Get Min–“) for i in range(10): print(“Min item %d ” % aList.getMin() ) # Notice that the getMinMax() method has been changed.
aList.printList() # printList() is a new method
print(“–Get Max–“) for i in range(10): print(“Max item %d ” % aList.getMax() ) # Notice that the getMinMax() method has been replaced.
aList.printList() # printList() is a new method
if __name__ == “__main__”: main()
Task 1 – MinMaxList: simple modifications
- Write the code the MinMaxList class in a separate file named “py.” In PyCharm, this should be in the same project and folder as your main.py code. Note that the code above imports the MinMaxList class.
- Modify the MinMaxList class (— see Lecture 9— https://trinket.io/python/19a5baaa92 ) as follows:
Remove the getMinMax() and replace it with two methods as follows (see code above too that calls these methods):
getMin() – returns the minimum item from the list, deletes the item from the list. getMax() – returns the maximum item from the list, deletes the item from the list.
- Add a new method called printList printList() – prints the instance variable storing the list
See next page for Task 2 – Making insert more efficient
Task 2: Making MinMaxList more efficient by modifying the insertItem() method
The current implementation of the MinMaxList is to perform a sort() in the constructor and when an item is inserted. For the constructor, apply sort() reasonable.
The current implementation of insertItem() is as follows: def insertItem(self, item): self.listData.append(item) self.listData.sort()
For inserting an item into an already sorted list, the current approach is highly inefficient. The time complexity of a sort() algorithm is O(nlogn) (this means, n * log(n)), which is slower than O(n). We can modify insertItem() to have a time-complexity of O(n) by searching the list for the correct location to insert the item. Recall that a list object has a method called “insert(index, item)” to insert an item at a particular index.
You need to make two modification to insertItem(). The first is to remove the sort, the second is to allow the method to printout information regarding how your insertion worked.
Modification #1 – do not use sort, instead, find the correct location to insert the item
Pseudo-code for performing the insertion: if the List is empty
Append item to end of the List (same as adding item to the list) else if item >= last element in the List: Append item to end of the List
otherwise
Find the appropriate index in the list to
insert the new item.
- Start by setting the index to 0.
- Add one to the index if the item is larger than the current position.
- Stop when you find an item is smaller than the element at the current position. (d) Insert the item at this index to the List.
See diagram on the right à
Modification #2 – have insertItem() printout information on your insertion
insertItem(self, item, printResult=False/True)
Add an additional parameter to allow a print out of where you inserted the item. Your print out should be as follows:
Item (86) inserted at location 5 # print out the item and location you inserted it [1, 2, 10, 11, 34, 86, 88, 99, 99] # print out the the list after insertion
Note that the provided code above uses this option.
Sample Output
If your MinMaxList is implemented correctly, your main.py (provided to you – see above) should work.
An example output is shown below. Note that the inserted numbers are randomly generated, so your output will look different.
— Insert Item —
Item (99) inserted at location 5
[1, 10, 11, 34, 88, 99, 99]
Item (2) inserted at location 1
[1, 2, 10, 11, 34, 88, 99, 99]
Item (86) inserted at location 5
[1, 2, 10, 11, 34, 86, 88, 99, 99]
Item (83) inserted at location 5
[1, 2, 10, 11, 34, 83, 86, 88, 99, 99]
Item (39) inserted at location 5
[1, 2, 10, 11, 34, 39, 83, 86, 88, 99, 99]
Item (16) inserted at location 4
[1, 2, 10, 11, 16, 34, 39, 83, 86, 88, 99, 99]
Item (81) inserted at location 7
[1, 2, 10, 11, 16, 34, 39, 81, 83, 86, 88, 99, 99]
Item (98) inserted at location 11
[1, 2, 10, 11, 16, 34, 39, 81, 83, 86, 88, 98, 99, 99]
Item (17) inserted at location 5
[1, 2, 10, 11, 16, 17, 34, 39, 81, 83, 86, 88, 98, 99, 99]
Item (78) inserted at location 8
[1, 2, 10, 11, 16, 17, 34, 39, 78, 81, 83, 86, 88, 98, 99, 99]
Item (97) inserted at location 13
[1, 2, 10, 11, 16, 17, 34, 39, 78, 81, 83, 86, 88, 97, 98, 99, 99] — I SKIPPED A FEW INSERTS —-
[1, 2, 10, 11, 16, 17, 33, 34, 39, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] Item (41) inserted at location 9
[1, 2, 10, 11, 16, 17, 33, 34, 39, 41, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] Item (50) inserted at location 10
[1, 2, 10, 11, 16, 17, 33, 34, 39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] Item (24) inserted at location 6
[1, 2, 10, 11, 16, 17, 24, 33, 34, 39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] Item (24) inserted at location 6
[1, 2, 10, 11, 16, 17, 24, 24, 33, 34, 39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99]
— Get Min —
Min item 1
[2, 10, 11, 16, 17, 24, 24, 33, 34, 39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] Min item 2
[10, 11, 16, 17, 24, 24, 33, 34, 39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] Min item 10
[11, 16, 17, 24, 24, 33, 34, 39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] Min item 11
[16, 17, 24, 24, 33, 34, 39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] Min item 16
[17, 24, 24, 33, 34, 39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] Min item 17
[24, 24, 33, 34, 39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] Min item 24
[24, 33, 34, 39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] Min item 24
[33, 34, 39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] Min item 33
[34, 39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] Min item 34
[39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] — Get Max —
Max item 99
[39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99] Max item 99
[39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98]
Max item 98
[39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97]
Max item 97
[39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95]
Max item 95
[39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93]
Max item 93
[39, 41, 50, 78, 81, 81, 83, 85, 86, 88]
Max item 88
[39, 41, 50, 78, 81, 81, 83, 85, 86]
Max item 86
[39, 41, 50, 78, 81, 81, 83, 85]
Max item 85
[39, 41, 50, 78, 81, 81, 83]
Max item 83
[39, 41, 50, 78, 81, 81]
- GRADING SCHEME (
To get full marks you need to make sure you follow the instructions correctly. The following will be our grading scheme for the Lab components specified in Section 2 of this document.
Task 0: (0 points, but deduction if you skip this part)
- Filenames must be “py” and “MinMaxList.py”
- The Python comments at the beginning of your program must include your name, email, and York student id (this is important for grading)
- If your file name is incorrect, or you do not put in the required information we will deduct -5 points (Why are we so harsh? Because if you don’t put in your name and student id it can be challenging for the TAs to determine whose submission this is.) Main Tasks :
- 5 points for Task 1
- 5 points for Task 2
See pages below on how to submit your lab code.
MAKE SURE TO SELECT Lab9 with websubmit
Note, if you use the new experimental testing platform it can perform websubmit for you!
- SUBMISSIONS (EECS web-submit)
You will submit your lab using the EECS web submit.
Click on the following URL: https://webapp.eecs.yorku.ca/submit
For more details on websubmit, see EECS department instructions: https://wiki.eecs.yorku.ca/dept/tdb/services:submit:websubmit
