$ mkdir ~/cs170/labs/lab19 $ cd ~/cs170/labs/lab19
We very briefly talked about algorithmic analysis when we discussed linear search versus binary search. Today, we are going to look a little bit more in depth into the topic. Specifically, we have looked at many different ways to sort a list of integers. Which one is better? Does it matter what is in the lists?
In addition, we are going to have a few more recursion activities for you to try today. This is intended to get you back on your feet as far as programming goes. However, we can also analyze the algorithms we are writing recursively today!
One thing to note about a recursive function is that you can usually write an iterative solution (essentially one using a loop) if you use some additional storage space. Certain recursive functions can be written iteratively without using this additional storage space. Factorial is one example of this type of recursive function, where your power function needs that additional storage space.
Determining whether a given string is a palindrome (a word that can is read the same forwards and backwards) is another good example of this. You may recall in CPSC 120 that you wrote a function to do this computation. Today, you are going to write both a iterative and recursive function to compute these.
Create a file called palindromes.py in your directory. You
will write two functions for this
activity: is_palindrome_recursive(a_string)
and is_palindrome_loop(a_string). Both functions
should behave the same way: return True if the given string is a
palindrome, return False otherwise. The sole difference is that the
recursive function must use recursion, where the loop function must
use a loop.
For the sake of this exercise, we will say that "Bob" is not a palindrome, where "bob" is a palindrome. Case matters!
Once you have written your functions and have tested them sufficiently and are certain they work, analyze the run time of your algorithms. Do they have the same run time? Are they different? Write your analysis in comments in your palindromes.py file.
| Function Parameter | Sample Output |
|---|---|
| racecar | True |
| racecars | False |
| bob | True |
| Bob | False |
| lonelytylenol | True |
| abba | True |
| aba | True |
| abca | False |
You will essentially have two base cases for your recursive function: an empty string and a string of one character are both palindromes.
A string is a palindrome if the first and last characters of the string are the same and if the string with those characters removed is also a palindrome.
Your looping version should behave the same way as the recursive version. Instead of making a recursive call, you will essentailly be removing information from the string at the end of each for loop iteration. Make sure you use a boolean variable to keep track of whether what you have seen so far is a palindrome!
A few of you last semester figured out how to use Python's list syntax to your advantage. The algorithm you wrote could potentially be classified as \(O(1)\)!
Write a third
function is_palindrome_constant(a_string) which
behaves the same way as the prior two but uses neither a loop nor
recursion. In the comments for this function, argue whether or
not this should count as a \(O(1)\) algorithm.
The Towers of Hanoi is a classic thought puzzle originally created in the 1800's. The concept of the game is simple: There are some \(N\) number of disks placed atop one another on a peg, with the size of each disk decreasing from the bottom disk to the top. There are two additional pegs in the game. The goal of the game is to move all of the disks from the first peg to the third peg, where:
While there are many different ways to figure out a solution, one of the most elegant is a recursive solution. Your task today is to implement a recursive solution that will indicate how many times a disk must be moved in order to solve the puzzle.
Create a file called hanoi.py in your directory.
In this file, create a function
called compute_hanoi(number_of_disks). This function
takes an integer number_of_disks, which is the number of
disks to compute the number of moves necessary to solve the towers
of hanoi problem.
The recursive solution is as follows. Label the towers A, B, and C. Tower A contains all of the disks to start, and Tower C is the desired destination. The recursive solution is in three parts:
| Function Parameter | Sample Output |
|---|---|
| 1 | 1 |
| 2 | 3 |
| 3 | 7 |
You will want to create a recursive helper function
called hanoi_helper(N, tower_A, tower_B,
tower_C), which takes an integer N which is the number
of disks being moved, and 3 lists of integers labelled
tower_A, tower_B, and tower_C respectively. This is where the
recursion listed above will take place.
Your base case is going to be when N is 0. In this case, there is nothing to do. You could write if N == 0: pass, but the better way to handle this is to make your base case implicit and use an if statement to prevent entering your recursive case in the base case.
Don't forget to return! You need to return not only in the base case but the recursive cases as well!
Just printing out the number of moves necessary is boring. It makes the recursion must easier, but isn't really solving the actual problem.
Modify your function so the full list of moves can be printed out.
When you have finished, create a tar file of your lab19 directory. To create a tar file, execute the
following commands:
cd ~/cs170/labs tar czvf lab19.tgz lab19/
To submit your activity, go
to inquire.roanoke.edu. You
should see an available assignment called Lab Assignment
19. Make sure you include a header
listing the authors of the file.