2008 September 24 / jjddaavviiss@@ccaarrlleettoonn..eedduu
Carleton College CS 201, Prof. Joshua R. Davis
This assignment has two goals. The first goal is to thoroughly understand linked lists; you demonstrate your understanding by adding new methods to the class. The second goal is to start thinking about the efficiency of algorithms and datastructures; we collect empirical data about the efficiency of lists, and describe/explain it using theory.
Download the following files to your computer.
Editing the file linkedlist.py, add an
append() method to UnorderedList. It should take in one item and add it to the end of the list.
Write a function (not a method) called
timeUnorderedAppend, that takes in a positive integer, builds an UnorderedList of that many objects, and then measures the time required to append one more object to the list. (For help on timing, see Section 4.2. Remember that you are timing just a single call to
append(), not the building of the whole list.) Then, using the following code, test how long it takes to append to lists of various sizes. (I hope that the test doesn't take longer than a minute. If it seems to be taking too much or too little time, then adjust the numbers.)
Make a precise graph of your data, using a spreadsheet, Mathematica, pen and paper, or whatever you like. Describe the trend that you see. Describe it using big-O notation (Section 4.2.1). Also, based on your knowledge of howprint "For UnorderedList append:" print timeUnorderedAppend(10000) print timeUnorderedAppend(20000) print timeUnorderedAppend(30000) print timeUnorderedAppend(40000) print timeUnorderedAppend(50000) print timeUnorderedAppend(60000) print timeUnorderedAppend(70000) print timeUnorderedAppend(80000) print timeUnorderedAppend(90000) print timeUnorderedAppend(100000)
append()is implemented, explain why the trend occurs.
Similarly, write a function
timePythonAppend that performs the same test for regular Python lists. Run it for the same test cases as above. Graph your data, and describe the trend in words and in big-O notation. Which is better at appending: UnorderedList or Python's list?
Whereas appending adds an element to the end of a list, prepending adds and element to the start of a list. How do you prepend to UnorderedList? To an ordinary Python list? (Hint: You don't need to write any methods.)
Just as you did for appending, write functions
timePythonPrepend that time how long prepending takes. Then collect data and describe the efficiency using big-O notation. You can make graphs, if you like, but this is not required. Which is better at prepending: UnorderedList or Python's list? Explain.
As you know, Python classes can possess special methods that hook into the language syntax in special ways. One is the constructor
__init__(), which is never actually used by that name, but rather by the name of the class. (For example, to make an UnorderedList you say
mylist = UnorderedList(), not
mylist.__init__().) Another is
__str__(), which returns a string representation of the object. (For example, if 13 is the integer 13, then
str(13) returns the string "13". You call this method using
There are also special methods
__getitem__(), which are used through the following special syntax:
Edit linkedlist.py to add# This is really mylist.__setitem__(7, 'bob'). mylist = 'bob' # This is really mylist.__getitem__(7). mylist
__getitem__()methods to UnorderedList.
As we did for appending and prepending, test the speed of getting an item (that is,
__getitem__()) from the middle of a list, for various sizes of lists, for both UnorderedList and regular Python lists. Collect data, describe the trend using big-O notation, and explain what is happening as well as you can.
This assignment is due at the start of class on Monday. It should be submitted on paper, in a clear, organized manner. Print out the three methods that you added to UnorderedList. (Of course, your code should be commented appropriately.) For each timing test, print the commands that constitute the test, the timing data, the graph (if required), and your typed commentary on efficiency, big-O notation, etc. Your work will be graded based on this rubric:
__getitem__()work? (3 points)