## Lecture 25 - Test Review

As usual, create a directory to hold today's activities:

$mkdir ~/cs170/labs/lab25$ cd ~/cs170/labs/lab25


Test Review

In addition to the written portion of the test, there will be a coding portion. This will be done on the computers. For practice, attempt the following exercises in a file called test_review.py, alone:

1. Write a function recursive_search, which takes a linked list node as a parameter, and an item being searched for. It will return True if the item is in the linked list, and False otherwise. You must use recursion for this exercise

  >>> my_linked_list = linked_list.LinkedList()
>>> for i in range(20, -1, -1):
True
False
True
False

2. Write a function permutations(a_set), which takes a list of data as its sole parameter. This function should print all possible permutations of the set a_set. A permutation of a_set is any ordering of items from a_set.

Permutations can be computed using a backtracking algorithm. A permutation can be found by selecting an element from the list, finding all permutations of the rest of the list. Then, select the next element from the list, and finding all permutations of the rest of that list. This continues until the the list is exhausted.

>>> permutations([1, 2, 3, 4])
[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 1, 3]
[2, 4, 3, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 1, 2, 3]
[4, 1, 3, 2]
[4, 2, 1, 3]
[4, 2, 3, 1]
[4, 3, 1, 2]
[4, 3, 2, 1]