CPSC 170 A

- Location
- Trexler 363
- Times
- MWF 3:30 - 5:30

- Office Hours
- M-Th 6 - 7pm
- Office
- Trexler 365B
- chssmith AT roanoke DOT edu

< Back

## 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

### Question 10

### Question 11

### Question 12

### Bonus

### Challenge

### Challenge

#### Submission

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

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:

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

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)

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] >>> 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]

(14 points)

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

(2 points)

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)

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:

c_{n} = c_{n-1}^{2} + z

Where z is a constant complex coordinate in the complex
plane. All pixels in the image are computed using the same
z. c_{0} 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)

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`

.