Lecture 24 - Test

If you do not currently have a directory for tests, create one in your cs170 directory, and also create a directory for test2 

$ mkdir ~/cs170/tests
$ mkdir ~/cs170/tests/test2
$ cd ~/cs170/test/test2

This portion of the test is worth 50 total points. You may reference any files within your directory. You may only access the Python documentation website and the tkinter documentation website. NO OTHER WEBSITES ARE PERMITTED. As usual, you are not allowed to directly copy any code from the Internet or another individual without citation. You should also follow all coding standards discussed thus far.

Test 2

Question 8

Download the linked_list.py file into your directory. Add a method called double_all, which creates a duplicate node for every node in the linked list, and appends it immediately after the original node. 

>>> my_linked_list = LinkedList()
>>> my_linked_list.double_all()
>>> print(my_linked_list)
head -> None
>>> my_linked_list.append("Hello")
>>> my_linked_list.double_all()
>>> print(my_linked_list)
head -> "Hello" -> "Hello" -> None
>>> my_linked_list.append("World")
>>> my_linked_list.double_all()
>>> print(my_linked_list)
head -> "World" -> "World" -> "Hello" -> "Hello" -> "Hello" -> "Hello" -> None

(10 points)

Question 9

In a file called question_9.py, write a function called list_powers(a_list). This function should take a list of integers as a parameter, and uses recursion to compute the result of chaining each number together with the exponentiation operator:

[2, 3, 4] => 2 (34) 

>>> print(list_powers([]))
0
>>> print(list_powers([1]))
1
>>> print(list_powers([1, 2, 3]))
1
>>> print(list_powers([2, 3, 4]))
2417851639229258349412352

(10 points)

Question 10

In a file called question_10.py, write a recursive function print_reverse(my_linked_list_node) that takes a linked list node and prints the elements of the list in reverse order, all on their own line.

Hint: If you can print the elements in the correct order, it is a very simple change to make it print in reverse order. 

  >>> my_linked_list = linked_list.LinkedList()
  >>> for i in range(5):
  ...     my_linked_list.append(i)
  >>> print(my_linked_list)
  head -> 4 -> 3 -> 2 -> 1 -> 0 -> None
  >>> print_reverse(my_linked_list.head)
  0
  1
  2
  3
  4

(10 points)

Question 11

We have discussed a handful of sorting algorithms this semester. One very simple sorting algorithm is known as Pigeonhole Sort. Pigeonhole Sort relies on the fact that more can be known about the data in the list before sorting. For example, we might know that all of the numbers are in the range [0, 100]. In this case, performing one of our usual sorting algorithms is actually less efficient.

Pigeonhole sort creates a list that contains a counter for every element in the range of values. For the above example, that would be a list of size 100, all with 0 as their default value. For every element in the list to be sorted, you increment the count in the appropriate list location. Once you have iterated through the entire list to be sorted, your counter list contains a frequency count for each of the elements in the index. To build a sorted list, you simply iterate over your counter list, and append the index of that list the number of times you found it in the list.

In a file called question_11.py, create a function called sort_grades(a_list), which takes a list of integers in the range [0, 100]. It should perform the pigeonhole sort algorithm, and return a copy of the original list in ascending order. You will not recieve credit for this exercise if you do not follow the above algorithm. 

  >>> my_list = [80, 82, 79, 96, 88, 100, 91, 81, 100, 61]
  >>> my_sorted_list = sort_grades(my_list)
  >>> print(my_list)
  [80, 82, 79, 96, 88, 100, 91, 81, 100, 61]
  >>> print(my_sorted_list)
  [61, 79, 80, 81, 82, 88, 91, 96, 100, 100]

(20 points)

 

Bonus

In the comments of your question_11.py file, write your estimate of the Big-Oh class of pigeonhole sort.

(2 points)

 

Challenge

In a file called carpet.py, create a function called draw_carpet, which creates a tkinter window and produces an image of the sierpinski carpet to some specified maximum depth. The Sierpinski Carpet is similar to the Sierpinski Triangle, except instead of removing the center triange, you remove the center square of the window. You then recursively call the algorithm on the 8 surrounding squares.

(5 points)

 

Challenge

Download the file called julia.py to store this extra credit activity.

Julia sets are sets of complex numbers that are related to the Mandelbrot set, and can produce interesting images. A complex number is determined to be in a Julia set in a similar fashion as the Mandelbrot set. The difference is the quadratic polynomial:

cn = cn-12 + z

Where z is a constant complex coordinate in the complex plane. All pixels in the image are computed using the came z. c0 is computed the same way as the Mandelbrot image. The file julia.py contains a skeleton of a program to generate a ppm image of a particular julia set. Complete the julia and compute_pixel_colors functions to produce an image of a julia set. Once you get the image like the one below, you can play with different values of Z to find more interesting sets.

(5 points)

Submission

When you have finished, create a tar file of your test2 directory. To create a tar file, execute the following commands:

cd ~/cs170/tests
tar czvf test2.tgz test2/

To submit your activity, go to cseval.roanoke.edu. You should see an available assignment called Test 2. Make sure you include a header listing the authors of the file.

Last modified: Fri Mar 21 12:35:54 EDT 2014