Test #2

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/tests/test2


This portion of the test is worth 30 total points. You may only access the Python documentation website and the tkinter documentation website. NO OTHER WEBSITES ARE PERMITTED. You should also follow all coding standards discussed thus far.

Test 2

Question 10

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

$[2, 3, 4] => 2^{(3^4)}$

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


(8 points)

Question 11

In a file called question_11.py, write a recursive function increase_list(a_list). This function takes a list of integers, and returns a list of integers. For each index i in the resulting list, you should store the sum of everything in the rest of the list (plus the value of the current index).

  >>> my_list = [1, 2, 3, 4]
>>> print(increase_list(my_list))
[10 ,9, 7, 4]


(8 points)

Question 12

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.

Because Pigeonhole sort knows the range of the values, it can create a counter for each value in the range. You can store these counters in a list, similar to how we created "bins" in radix sort. This will allow us to compute a histogram for the values that exist within the list. For each element in the list, you increment the counter for the appropriate element. Once you have finished iterating over the entirety of the list, you have the number of times each value from the range appeared in the list to be sorted.

To recreate the sorted list, you simply iterate over the range of values. For each value in the range, you append it to the sorted list the number of times the counter specifies.

In a file called question_12.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]
>>> 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]


(14 points)

Bonus

In the comments of your question_12.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. You also need to download the ppm.py file which generates the image file.

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 same 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 inquire.roanoke.edu. You should see an available assignment called Test #2.