$ mkdir ~/cs170/labs/lab36 $ cd ~/cs170/labs/lab36
It seems that many of you had trouble figuring out the knights tour. I again want to show you the backtracking solution for that, using recursion. The stack method would work for this one, but you would basically need 3 - 4 different stacks. The recursive method is much cleaner.
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. Make sure you follow all coding conventions, including !
Download the file linked_list.py,
which contains a LinkedList class. Add a method called
slice(self, start_index, end_index), which returns a
new linked list containing only the elements from the current list
between the two indicies specified (including start_index, excluding
end_index). Read the provided code carefully for this exercise.
>>> linked_list = Linked_List() >>> for i in range(0, 11): >>> linked_list.append(i) >>> new_linked_list = linked_list.slice(2, 4) >>> print(linked_list) head -> 10 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 -> None >>> print(new_linked_list) head -> 8 -> 7 -> None >>> new_linked_list = linked_list.slice(1, 8) >>> print(linked_list) head -> 10 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 -> None >>> print(new_linked_list) head -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> None
Download the file tree.py, which
contains a BinaryTree class. Add a method called
double_nodes(root), which inserts a duplicate of each
node as their own left child.
>>> my_tree = BinaryTree() >>> my_tree.insert(5) >>> my_tree.insert(3) >>> my_tree.insert(8) >>> my_tree.insert(4) >>> my_tree.insert(6) >>> my_tree.insert(7) >>> print(my_tree.pre_order()) 5 3 4 8 6 7 >>> my_tree.double_nodes(my_tree.root) >>> print(my_tree.pre_order()) 5 5 3 3 4 4 8 8 6 6 7 7
Write a function called compute_anagrams(a_string),
which takes as parameter a string, and an
initially empty list of anagrams. This function should recursively
compute all of the anagrams of the input word. They do not need to
be real words. You may need to write a helper function for this problem.
>>> print(compute_anagrams("bob"))
['bob', 'bbo', 'obb', 'obb', 'bbo', 'bob']
>>> print(compute_anagrams("cpsc"))
['cpsc', 'cpcs', 'cspc', 'cscp', 'ccps', 'ccsp', 'pcsc', 'pccs',
'pscc', 'pscc', 'pccs', 'pcsc', 'scpc', 'sccp', 'spcc', 'spcc',
'sccp', 'scpc', 'ccps', 'ccsp', 'cpcs', 'cpsc', 'cscp', 'cspc']