CS21 Practice QUIZ 5, Swarthmore College, Fall 2008

Q1] Write a recursive function called 
removeRecur that takes a value and a list and returns a new
list where all instances of that value have been removed.  For
example, removeRecur(-1, [-1, 0, -1, 1, 2]) would return a
new list [0, 1, 2].

Write an iterative version of the same function
called removeIter. 

Q2] What types of algorithms are particularly well suited
for recursive solutions?  Explain why and give the name of one such
algorithm. 

Q3] What is the minimum and maximum possible number of iterations 
linear search will need to find a value in a list of 64 items? 
What are the min and max for a binary search with N=64?

Q4] If an algorithm takes x steps to run, where x is n**2, n, log(n), or 
nlog(n), for an input of size n, which is the "best" for large n? Which is the worst?

Q5] Write a recursive function to calculate h(n), where:

h(n)=1 if n=1 and 
h(n)=2*h(n-1)+1 if n >1

Q6a] What does the following function do,
and what would be the output of mystery("hannah")?

def mystery(astring):
  if len(astring) <= 1:
    return True
  else:
    if astring[0] == astring[len(astring)-1]:
      return mystery(astring[1:len(astring)-1])
    else:
      return False


Q6b] Trace through a call to mystery("pop") and draw the stack
at the deepest point in the recursion.

Q7] Write a sort function (any sort, but don't use the built-in 
python sort method) that takes in a list and sorts it.