Quiz 5 Study Guide

You are responsible for all material covered through the end of Week 10 (Recursion).

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

Python concepts

  • Analysis of algorithms/big-O notation:

    • \$O(1)\$ — constant time

    • \$O(\log N)\$ — logarithmic (e.g. binary search)

    • \$O(N)\$ — linear (e.g. linear search)

    • \$O(N^2)\$ — quadratic (e.g. bubble sort)

  • Sorting: bubble vs selection sort

  • Swapping two values in a list

  • Recursion

    • base case

    • recursive call

    • recursion on numbers, strings, and lists

    • recursion vs iteration

You should be able to

  • compare different runtime analyses for algorithms

  • trace the execution of different searching and sorting algorithms

  • trace the execution of recursive function

  • write a recursive function that takes a number, string or list as a parameter

Practice problems

  1. What would the output of the following code be?

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

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

    • linear search

    • binary search

    • bubble sort

    • selection sort

  3. Consider the following function, oneLoop(L), which is similar to the inner loop from bubble sort:

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

    Suppose we run oneLoop on the list L=[17,4,19,3,11,8]. What are the new contents of L?

  4. Show how the list L=[17,4,19,3,11,8] would be changed after selection sort does its first 3 swaps:

    For concreteness, here is some Python code for selection sort:

    def selection_sort(lst):
    n = len(lst)
    for i in range(n-1):
        min_index = i
        for j in range(i+1, n):
            if lst[j] < lst[min_index]:
                min_index = j
        lst[i], lst[min_index] = lst[min_index], lst[i]

  5. What would the output of the following code be?

    def mystery(n):
    if n == 1:
        return 0
    else:
        return 1 + mystery(n//2)

def main():
    result = mystery(11)
    print("Result: %d" % (result))

main()

  6. Given the code below:

    def unknown(lst):
    if len(lst) <= 1:
        return True
    elif lst[0] > lst[1]:
        return False
    else:
        return unknown(lst[1:])

def main():
    result = unknown([3, 5, 7, 1])
    print("Result:", result)

main()

    • What is the return type of the recursive function?

    • What is the base case(s)?

    • What is the recursive step(s)?

    • What is the output of the program show above?

    • Provide another list (instead of [3, 5, 7, 1]) with the same length that gives a different output.

    • What does the unknown function do?

  7. Write a recursive function, insert_many, that takes a string, a character, and a number and returns a new string with the character inserted between every letter of the original string and repeated the given number of times. For example:

insert_many('swat','x', 3) => 'sxxxwxxxaxxxt'
insert_many('hello','!', 0) => 'hello'
insert_many('cs21', '!', 2) => 'c!!s!!2!!1'