Quiz 5 Study Guide

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

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

Python concepts

  • Analysis of algorithms, and run times:

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

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

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

  • Sorting: bubble vs insertions 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 inclass/w09/rich/worksheet.txt file.

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

      In terms of the parameter \$N\$, how many times will this function print given, i.e., is the run time, logarithmic, linear, quadratic, or something else?

    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, idx):
    if (idx >= (len(lst) - 1)):
        return True
    elif lst[idx] > lst[idx + 1]:
        return False
    else:
        return unknown(lst, idx + 1)

def main():
    result = unknown([3, 5, 7, 1], 0)
    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, and what would be a better name for this function?