CS21: Quiz 5 Study Guide

In addition to all concepts from Quiz 1, Quiz 2, Quiz 3, and Quiz 4...

You should understand the following terms and concepts:

• Top-down design
• File reading
• Lists of lists
• Searching: linear search and binary search
• Analysis of algorithms/big-O notation (O(1) vs O(log(n)) vs O(n) vs O(n²))

Practice problems:

1. Write a program that reads in the lines from a file called infile.txt and creates an acronym from the first letter of each line. For example, if the input file is:

Thank
Goodness
It's
Friday

Your program will create and print out the string "TGIF"

2. Assume that the following assignment has been made:

L=[["cat", "mammal"], ["boa", "reptile"], ["dove", "bird"], ["dog", "mammal"]]

Show the value and type of each expression given below:

                             VALUE                     TYPE
                             -----                     ----
len(L)

L[1]

L[1][0]

L[0][1] == L[3][1]

L[0][1] + "-" + L[0][0]

3. What would the output of the following be?

for i in range(2):
    for j in range (3):
        print("i:%d j:%d" % (i,j))

4. True/False questions:

• Linear search requires a number of steps proportional to the size of the list being searched (T/F)
• The python in operator performs a binary search (T/F)
• Binary search is an N² algorithm (T/F)
• The number of times N can be divided by 2 (before reaching 1) is log₂N (T/F)

5. How many steps would it take to do binary search on a list of size 1 million when the item you are searching for is NOT in the list?

6. How many steps would it take to do linear search on a list of size 1 million when the item you are searching for is NOT in the list?

7. Binary search is much faster than linear search, so why don't we use it for every search problem?

8. For each iteration of the loop in binarySearch(x, L), show the index values for low, high, and mid, and the value stored at location mid. What will be returned by this function call?

x = 67
L = [10, 12, 14, 21, 37, 44, 45, 46, 58, 67, 99]  
      0   1   2   3   4   5   6   7   8   9  10   

low | high | mid | L[mid]
-------------------------
    |      |     |
    |      |     |
    |      |     |
    |      |     |

9. For each iteration of the loop in binarySearch(y, L), show the index values for low, high, and mid, and the value stored at location mid. What will be returned by this function call?

y = 4
L = [10, 12, 14, 21, 37, 44, 45, 46, 58, 67, 99]  
      0   1   2   3   4   5   6   7   8   9  10   

low | high | mid | L[mid]
-------------------------
    |      |     |
    |      |     |
    |      |     |
    |      |     |

10. Write a function to return the index of the smallest item in a given list.

def indexOfSmallest(ls):
   """
   Inputs:  A list of values
   Returns: The index of the smallest item in the list, -1 if the list
   is empty
   Purpose: To find the location of the smallest item in the given list
   """
   # complete this function

11. How many steps are required for each of the following?

for i in range(N):
    for j in range(N):
        print(i, j)

while N > 1:
    print(N)
    N = N//2

for i in range(N):
    for j in range(10):
        print(i*j)

12. Which algorithm requires time directly proportional to the size of the input list?

    • linear search
    • binary search
    • bubble sort
    • selection sort