# CS21: Quiz 5 Study Guide

### 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: