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, Quiz 6.

The final exam will include questions about each of the big ideas and skills in the course, such as:

• Understanding python expressions and types
• Writing a complete program with multiple functions and a clear, concise main
• Tracing a program, showing output and the stack diagram
• Writing and testing a class
• Recursion and iteration
• Analysis of algorithms
• Searching and sorting
• Linked Lists

Below are some of the new topics covered since the last quiz and some additional practice problems.

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

• 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 lists

Practice problems:

1. Write a recursive sumList function that takes a python 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. Using your LinkedList implementation from class, write a LinkedList maximum method that returns the maximum value from the items in a linked list.
4. Write a complete python program that prompts a user for a new password and then verifies that the password meets the following conditions:
   • At least 7 characters long.
   • Contains at least one uppercase letter.
   • Contains at least one lowercase letter.
   • Contains at least one digit.
   As long as the password is invalid, the program should report the problem and prompt the user for a new password. Once a correct password has been provided the program should report success and end. Recall that python includes string methods: islower(), isupper(), and isdigit() that could be helpful in solving this program.