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:

• Searching: linear and binary search
• Sorting: selection, bubble, and insertion sort

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

• swapping two values in a list
• ord() and chr() functions
• searching and sorting algorithms
• complexity (big O, number of steps) of searching and sorting algorithms
• string comparisons ("alice" < "zelda")

Practice problems:

1. True/False questions 1-4 on page 460 (Chapter 13)
2. Multiple choice questions 1, 2, and 6 on page 461 (Chapter 13)
3. Discussion question 1 on page 462 (Chapter 13)
4. Write a sort function (any sort) that takes in a list and sorts it in place. Show what a call to your sort function would look like from main.
5. Write a function to return the index of the smallest item in a given list.
6. Show the values for low, high, and mid for each step in searching the list L for the value x using binary search.

   x = 99
   L = [-20, -12, -4, 1, 7, 44, 45, 46, 58, 67, 99, 145]     low   mid   high
                                                             ----------------
   
   

7. Consider the following function, oneLoop, which is similar to the inner loop from bubble sort:

   def oneLoop(ls):
     print "in oneLoop"
     for j in range(len(ls)-1):
       if ls[j] > ls[j+1]:
         tmp = ls[j+1]
         ls[j+1] = ls[j]
         ls[j] = tmp
   

   (1) Given the list ls = [17, 4, 19, 3, 11, 8], what is ls after one call to oneLoop(ls)?

   (2) Given the following main function, trace through its execution showing all program output and drawing the stack right before the call to function oneLoop returns:

   def main( ):                    
     print "in main"
     my_list = [6, 8, 19, 3, 7]
     print my_list
     oneLoop(my_list)
     print my_list 
   

8. Given the following definition:

      ls = ["fish", "squirrel", "cat", "dog", "monkey", "pony"]
   

   What are the value and type of the following expressions:

     (1) ls[3] > "apple" 
     (2) ls
     (3) ls[3]
     (4) ls[3][1]
     (5) ord('b') < ord('f')
     (6) 'b' < 'f'
     (7) chr(ord('a'))
   
   

9. Show how the following list would be changed after selection sort does its first 3 swaps:

   [15, 99, 4, 30, 3, 82, 7, 42]