< 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

$ 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.

---

---

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

 

---

---

---

Submission

When you have finished, create a tar file of your