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.

Historically, the final exam includes questions about each of the big ideas and skills in the course, such as:

• Python expressions and types
• Write a complete program
• Write and test a class
• Trace a program, showing output and the stack diagram
• Recursion and iteration
• Analysis of algorithms
• Searching and sorting
• Linked Lists

Below are some of the new topics covered since the ultimate 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 ArrayLists

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

• How to implement a LinkedList in Python

Practice problems:

1. Using the LinkedList implementation from class, write a LinkedList sum method that returns the sum of the items in the list.
2. Using the LinkedList implementation from class, 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.
3. Consider a file storing each professor's name and the names of students in that professor's class. For example:

   Charlie:Abigail,Annie,Avery,Gabe,Naudia,Radwan
   Lisa:Bowen,Celia,Chelsea,Chris,Nick
   Jeff:Carolyn,Davis,Paul,Reed,Vincent
   

   Each line is formatted as the name of the professor, a colon, and then the students in that professor's class (with the students' names separated by commas).
   • Write a function getClassLists which, given a file name as a string argument, returns a dictionary where each key in the dictionary is a professor's name and the value for each key is the list of students in that professor's class (as a list of strings).
   • Write a function getProfsForStudent that, given the dictionary from the problem above and a student's name as arguments, returns a list of professor names who have that student in their class.
4. Write a complete program that plays a guessing game with numbers. The goal is for the user to guess a randomly selected number between 1 and 100 as quickly as possible. The program will inform the user whether the hidden number is higher or lower than the current guess. You can assume that the user will always enter integers, but you must verify that the integers entered are between 1 and 100. You must break the problem up into a main program and at least two additional functions.

   The following is a sample run of the program:

   I'm thinking of a number between 1 and 100.
   Enter guess: 50
   Number is higher than 50
   Enter guess: 588
   Invalid, try again: 75
   Number is lower than 75
   Enter guess: 62
   Number is lower than 62
   Enter guess: 56
   You guessed it in 4 tries!
   

5. 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? (Note: this problem is asking about regular Python lists, not linked lists.)
6. Using your sumList function above, draw a complete stack diagram for the following program:

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

7. Write a complete 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. If a password is invalid for multiple reasons, it's OK if the program reports just one of those reasons. Once a correct password has been provided, the program should report success and end. Note that python includes built-in string methods .islower(), .isupper(), and .isdigit() that could help you solve this problem:
   • str.islower() returns True if the string str contains just lowercase characters.
   • str.isupper() returns True if the string str contains just uppercase characters.
   • str.isdigit() returns True if the string str contains just digit characters.