Quiz 4 Study Guide

You are responsible for all material covered through the end of Week 8 (Searching).

In addition to all concepts from Quiz 3, you should understand the following:

Python concepts

  • common string methods: upper(), lower(), split(), and strip()

  • adding to a list with the append() method

  • top-down design

  • bottom-up implementation

  • stubbed-out (prototyped) functions

  • list of lists

  • searching: linear search and binary search

  • analysis of algorithms/big-O notation:

    • O(log N) — logarithmic (ex: binary search)

    • O(N) — linear (ex: linear search)

Practice problems

  1. The following get_numbers(n) function doesn’t work. Find and fix the bug in the code below.

    def get_numbers(n):
    """
    Purpose: Read n numbers from the user and return them as a list
    Parameters: n -- the number of values to read from the user (integer)
    Return: a list of the numbers entered by the user
    """
    for i in range(n):
    	value_list = []
	value = int(input("Enter a number: "))
	value_list.append(value)
    return value_list

  2. Given the assignments for S and L, what is the value and type of each expression?

    S = "ab-cd-ef"
L = ["This is", "a list with", "some words", "inside of it"]
data = [['PA', 20], ['NJ', 14], ['OH', 18], ['WI', 10]]

                                 VALUE            TYPE
                                 -----            ----
    len(L)
    len(L[0])
    len(S)
    "some" in L[2]
    "cd" in S
    L[1][0]
    S.upper()
    S.split('-')
    S < "ZEBRA"
    data[0]
    data[0][1]
    data[2][0] < data[3][0]

  3. Assume you have these two functions already written:

    • getPick() asks the user for "r,p,s?" and returns:

      • "rock" if they enter r

      • "paper" if they enter p

      • "scissors" if they enter s

    • winner(user,comp) returns:

      • "user" if user won the game (e.g., user="rock", comp="scissors")

      • "comp" if comp won the game (e.g., user="rock", comp="paper")

      • "tie" if it’s a tie game (e.g., user="rock", comp="rock")

        Write a main() function that uses the above functions to play one round of rock-paper-scissors. Here are a few sample runs of the program:

        $ python3 rps.py
r,p,s?: r
Computer chose rock
tie...
$ python3 rps.py
r,p,s?: r
Computer chose paper
Computer wins!
$ python3 rps.py
r,p,s?: r
Computer chose scissors
You win!

  4. Write the stub for the winner(user, comp) function.

  5. Write the implementation for the getPick() function. Your getPick() function should only accept r, p, or s from the user. If they enter anything else, print an error message and ask again.

    r,p,s?: w
please enter r, p, or s!!!
r,p,s?: zebra
please enter r, p, or s!!!
r,p,s?: r

  6. 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 O(N) algorithm (T/F)

    • The number of times N can be divided by 2 before reaching 1 is the log (base 2) of N (T/F)

  7. 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?

  8. 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?

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

  10. 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] | comparison
- - - - - - - - - - - - - - - - - - - -
    |      |     |        |
    |      |     |        |
    |      |     |        |
    |      |     |        |

  11. 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] | comparison
- - - - - - - - - - - - - - - - - - - -
    |      |     |        |
    |      |     |        |
    |      |     |        |
    |      |     |        |