This assignment is Homework 19, and is due at classtime on Wednesday, April 12.

Assignment

1. Write a recursive function that prints the sequence of moves necessary to solve the Tower of Hanoi problem.

   Specifically, your program should first ask the user for a number of disks, and then print the sequence of moves required to move the stack of disks from post 1 to post 3. Recall that only one disk may be moved at a time, and a large disk may not be placed on top of a smaller disk. Assume disk 1 is smaller than disk 2, which is smaller than disk 3, and so on.

   For example, the Python console might look something like this when you run your program:

   How many disks? 2
Move disk 1 from post 1 to post 2
Move disk 2 from post 1 to post 3
Move disk 1 from post 2 to post 3
DONE

2. Write a function that implements the binary search algorithm to search for an item in a sorted list.

   Your function header should be:

   def binarySearch(alist, item):

   This function requires that the list alist be sorted in ascending order. The function returns True if item is in the list alist, and False otherwise.

   Recall the binary search algorithm from class:

   • If the list is empty, then return False.
   • Otherwise, look at the middle item in the list; if that is the desired item, then return True.
   • Otherwise, recursively search either the left half or the right half of the list, depending on whether the desired item is greater than or less than the middle item of the current list.

   You must write a recursive algorithm to receive full credit.

3. Answer the following questions.
   1. What is the smallest number of moves that will solve the Tower of Hanoi problem for 4 disks?
   2. What is the smallest number of moves that will solve the Tower of Hanoi problem for n disks? (Your answer will be an expression that depends on n.)
   3. Suppose you have a sorted list of 7 items. If you do a binary search on this list, what is the maximum number of items in the list that will need to be examined before the search algorithm can return True or False?
   4. What is the size of the largest list such that a binary search on the list will always return True or False by examining no more than 5 items in the list?

Submitting your work

After you have finished your solutions, paste them into a single Python file. Make sure that Python can run your file without error! Please use comments (lines that begin with a # symbol) to clearly state the problem number for each solution in your file. Save your file and upload it to the HW19 assignment on Moodle.