The final exam is cumulative. In addition to the concepts below, you should know the concepts that were tested on all the quizzes in the course: Quiz 1, Quiz 2, Quiz 3, Quiz 4, Quiz 5.

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

• Recursion and iteration
• Imperative programming
• 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
• Linked lists, including
  • the LinkedList class
  • the Node class
  • the implementation and running time of various LinkedList methods, such as the constructor, insertAtTail, insertAtHead, deleteHead, and getItemAtPosition
  • how linked lists differ from Python's consecutive-memory ArrayLists

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

• 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.
• How to implement a LinkedList in Python

Practice problems:

1. Write a recursive sumList function that takes a list as an argument and returns the sum of the items in the list. What is the base case of your function? What is the recursive case?
2. Using your sumList function above, draw a complete stack diagram for the following program:

   def main():
       ls = [2, 3, 5]
       x = sumList(ls)
   

3. Write a recursive binarySearch function that takes as arguments: a list, an item to search for, a low index, and a high index. It should return the position of the item in the list, or -1 if the item is not in the list.
4. Write a Student class that stores information for a Swarthmore student. The class should include the following instance variables:
   • id, an integer identifier for the student
   • firstName, a string
   • lastName, a string
   • courses, a list of strings, the course names that the student is enrolled in
   • hobbies, a list of strings, the student's hobbies
   Write the following methods for your Student class:
   • A constructor that, given an id, a first name, and a last name, creates a Student with those values and empty lists of courses and hobbies.
   • A string method that returns a string representing the student.
   • Getter methods for each of the instance variables in the class.
   • An addCourse method that, given a course name, adds that course to the student's course list.
   • An addHobby method that, given a hobby name, adds that hobby to the student's hobby list.
   • A getCredits method that returns the number of courses a student is enrolled in.
   • A getFreeTime method that returns the value 55 - 12*number-of-courses - 5*number-of-hobbies. (Alternatively, this method could just return 0.)
5. Write a LinkedList deleteTail method that deletes the tail of a linked list and returns the value of the item that was stored at the tail. Before attempting this, write pseudocode for the deleteTail method; it's harder than the deleteHead method from class! To delete the tail, you need to set the new tail to be the Node before the current tail; to do that, you need to find that Node by traversing through the list.