Assignment 3

Problems

  1. Another "pencil and paper"* exercise on algorithmic complexity.

    1. A straight selection sort algorithm,O(n2), takes 10ms (milliseconds) to sort an array of 100 elements. How long do you estimate it will take to sort an array with 2000 elements?

    2. An O(2n) algorithm takes 5 seconds to process a dataset with 20 entries. How long will it take it to process a dataset with 300 entries?

    3. A Shellsort implementation, O(n log n), takes 11 seconds to sort a list of 1,000 elements. How long do you estimate it will take to sort a list with 40,000 elements?

    4. An O(n!) algorithm takes 2 seconds to process a list with 10 entries. How long will it take to process a list with 100 entries?

    5. A binary search of a list of 2,000 items takes takes 2 microseconds. How long do you estimate it will take to search a list with 120,000 elements?

    * "Pencil and paper" does not mean that it has to be done with pencil and paper, it just points out that it can be and doesn't require a program as an answer. The Python shell might provide a convenient way of doing the calculations and you could submit the Python expressions that calculate the answers, e.g. an answer for a2p2e might be print pow(2,12000)/pow(2,100)*4, 'microseconds'.

  2. Here are a couple of problems just to give you a bit of practice with recursion and help you internalize the idea.

    1. Write a recursive function called list_max named that returns the largest value in a list it is passed. Note that like some of the lists in the notes the list could be recursive, e.g. [2, [[100, 7], 90], [1, 13], 8, 6].

    2. Write a recursive function called is_palindrome that determines if a string it is passed is a palindrome. (A palindrome is a string that is the same forward and backward, i.e. where the first and last letters are the same and the second and second-last letters are the same etc., e.g. "eye", "dad" and "madam" are palindromes. Word enthusiasts also count phrases that are palindromic once you remove the spaces, capitalization and punctuation, e.g. "Do geese see God?" and "Murder for a jar of red rum.")

    3. Write a recursive function called power that raises a number to an exponent. The naive way is to use an explicit loop to multiply the number by itself the required number of times, e.g. computing 216 would require 15 multiplications. But we can be more efficient by noting that 216 = 28 × 28, and that 28 = 24 × 24 and that 24 = 22 × 22 and finally that 22 = 2 × 2. Putting this together we could calculate 216 as (22)2)2)2 and do only 4 multiplications. It doesn't work out quite so well if the original number isn't an even power of two, but it's not terrible even then. The trick is to view 29 as 24× 24 ×2. The general relationship is that an = an/2 × an/2 if n is even and an = an/2 × an/2 × a if n is odd. Write a recursive function called power that raises a whole number to a whole power (e.g. power(2, 9) using this method.

  3. Persistent Life

    Modify a working game of life program (yours or mine: life_v3.py*) so that it can store and retrieve states of the universe. It should be able to store in any of the three formats discussed in the notes. It should also be able to read files in all three formats and should autodetect which format the file is in, i.e. it shouldn't need to ask the user.

    * if you find there is too much code in the version linked to, version 3, you might find it helpful to look at the stepping stone on the way there: life_v2.py.

Logistics