In addition to the concepts below, you should also know the concepts from Quiz 1, Quiz 2, Quiz 3, and Quiz 4. Many of the earlier concepts -- especially functions -- are fundamental to what we've been studying recently.

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

• Searching: linear and binary search

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

• swapping two values in a list
• searching algorithms
• complexity (big O, number of steps) of searching 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 function to return the index of the smallest item in a given list.
5. 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
                                                             ----------------
   
   
   
   
   
   

6. 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) 'b' < 'f'
   
   

Home Page

Last updated: Tuesday, September 22, 2020 at 09:07:40 AM