2008 September 24 / jjddaavviiss@@ccaarrlleettoonn..eedduu

Introduction to Efficiency

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.

0. Prepare Yourself

Download the following files to your computer.

linkedlist.py implements the UnorderedList class that we discussed in class.

As usual, you'll be editing code in Smultron and running code in Terminal.

1. Implement `append()`

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.

2. Test Appending to UnorderedList and Python's 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.)

print "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)

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 how 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?

3. Test Prepending to UnorderedList and 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 timeUnorderedPrepend and 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.

4. Implement `setitem()` and `getitem()`

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 str(13), not 13.__str__().)

There are also special methods __setitem__() and __getitem__(), which are used through the following special syntax:

# This is really mylist.__setitem__(7, 'bob').
mylist[7] = 'bob'
# This is really mylist.__getitem__(7).
mylist[7]

Edit linkedlist.py to add __setitem__() and __getitem__() methods to UnorderedList.

5. Test Accessing UnorderedList and Python's List

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.

6. Hand In Your Work

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:

Do append(), __setitem__(), and __getitem__() work? (3 points)
Is your code comprehensible and appropriately commented? (1 point)
For appending, are your test code, numerical results, graphs, and discussion understandable and insightful? (3 points)
For prepending, are your test code, numerical results, and discussion understandable and insightful? (3 points)
For accessing, are your test code, numerical results, and discussion understandable and insightful? (3 points)