In addition to the concepts below, you should also know the concepts that were tested on all of the previous quizzes.

You should be able to define and explain the following terms:

• Recursion and iteration
• Merge sort (uses recursion)
• Object-oriented programming, including
  • methods
  • an object's instance variables
  • the constructor, or __init__ method
  • the string, or __str__, method
  • access methods, getters
  • update methods, setters

You should understand and be able to use the following Python concepts:

• complexity (big O, number of steps) of merge sort algorithm
• recursive function base case
• how variables are stored and function arguments are passed on the stack for recursive functions
• how to create a Python object, including its constructor, string method, and the instance variables that it uses

Practice problems:

1. Write two versions of each of the following functions...one version using iteration and one using recursion:
   • sum all values in a given list of integers
   • return True if a list is sorted/in order, False if not
   • count/return how many times a given value (v) is found in a list (L)
   • find the largest number in a list
2. Draw a stack diagram for the following program. Show what the stack would look like at it's largest point.

   def main():
       n = 5
       ans = factorial(n)
       print ans
   
   def factorial(x):
       if x == 0:
         return 1
       else:
         return x * factorial(x-1)
   
   main()
   

3. Write a Patient class to be used by a medical application. Each patient object should have a name, age, and a list of current diseases they are suffering from. Include in your class the following:
   1. a constructor with parameters for name and age (patient is initially healthy)
   2. an __str__ method to allow printing a patient object
   3. an addDisease() method to add a disease to the patient's list of diseases
   4. a cure() method to cure the patient of all diseases
   Your class should work with a main() such as this:

      draco = Patient("Malfoy", 15)
      draco.addDisease("spattergroit")
      draco.addDisease("dragon pox")
      print draco
      draco.cure()