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 a recursive function

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

Practice problems

  • NOTE: There are additional search-specific questions in the searchWorksheet.txt file in your week 10 class notes directory.

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

      • linear search

      • binary search

      • bubble sort

      • selection sort

    2. 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))

    3. Consider a similar pair of nested loops in a function:

      def loops(N):
    for i in range(N):
        for j in range(N):
            print("i:%d j:%d" % (i,j))

      Using big-O notation, how many times will this function print given an integer input N?

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

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

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

      def mystery(n):
    if n == 1:
        # Draw stack here
        return 0
    else:
        return 1 + mystery(n//2)

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

main()

      Draw a stack diagram to show the contents of the stack just before returning from the base case.

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

    1. 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'