< Back

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

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 10

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

(10 points)

---

Question 11

In a file called question_10.py, write a recursive function subtraction_reverse(my_linked_list_node) that takes a linked list node and subtracts each successive element (in reverse order).

For example, consider the list:

head -> 4 -> 3 -> 2 -> 1 -> 0 -> None

Your program should compute:

\[ 0 - 1 - 2 - 3 - 4 = -10 \]

  >>> 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
  >>> subtraction_reverse(my_linked_list.head)
  -10
  

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

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 as a list. 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_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)

 

---

---

---

Submission

When you have finished, create a tar file of your