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:

• Running time of an algorithm
  • Big-O notation (also known as "order notation")
• Searching
  • Linear search, including its input requirements, the details of the algorithm, and its worst-case running time
  • Binary search, including its input requirements, the details of the algorithm, and its worst-case running time
• Sorting
  • Bubble sort, including the details of the algorithm and its worst-case running time
  • Selection sort, including the details of the algorithm and its worst-case running time

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

• How lists and dictionaries are passed as function arguments on the stack.
• How to apply python dictionaries to real-world problems (such as google's "Did you mean?" problem and databases of information like zip codes).

Practice problems:

1. True/False 1-4, 9 from Chapter 13 (pgs. 460-461)
2. Multiple choice problems 1,2,6,7 on page 460 (Chapter 13)
3. Discussion question 1 on page 462 (Chapter 13)
4. 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?
5. Write a sort function (any sort) that takes in a list and sorts it. Show what a call to your sort function would look like from main.
6. Show the low, high, and mid values for each step of a binary search for the value 7 in this list: [ -3, 4, 5, 10, 14, 18, 22, 31, 44, 66, 70]
7. Write a function that takes a value, k, and a list of values, and for every occurrence of k in the list, the function should replace that list item with k squared. Your function should also return the number of times k appeared in the list. Show what a call to your function would look like from main.
8. 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.