CS21: Quiz 6 Study Guide

In addition to the concepts below, you should also know the concepts that were tested on all of the previous quizzes: Quiz 1, Quiz 2, Quiz 3, Quiz 4, Quiz 5.

You should be able to define and explain the following terms:

You should understand and be able to use the following Python concepts:

Practice problems:

  1. Write two versions of each of the following functions, one version using iteration and one using recursion:

    • sum all values in a given list of integers

    • return True if a list is sorted/in order, otherwise False

    • count/return how many times a given value (v) is found in a list (L)

    • find the largest number in a list

  2. Draw a stack diagram for the following program. Show what the stack would look like at it's largest point.
    def main():
        n = 3
        ans = summation(n)
        print(ans)
    
    def summation(n):
        if n == 0:
           return 0
        else:
           return n + summation(n-1)
    
    main()
    

  3. Show the output for the following program:
    def main():
        result = mystery("swarthmore")
        print(result)
    
    def mystery(x):
        if len(x) == 0:
            return ""
        elif x[0] == 'a':
            return '@' + mystery(x[1:])
        elif x[0] == 'e':
            return '3' + mystery(x[1:])
        elif x[0] == 'o':
            return '*' + mystery(x[1:])
        else:
            return x[0] + mystery(x[1:])
    
    main()
    

  4. Here are several possible solutions to the problem of finding the product of a list of numbers. For example, product([4,2,5]) should return 40, which is equivalent to 4*2*5. Which of these solutions is correct? For incorrect solutions, what would be returned when each is called on the test list [4,2,5] and how would you fix the problem?
    def product1(ls):
        if len(ls) == 0:
            return 0
        else:
            return ls[0] * product1(ls[1:])
    
    def product2(ls):
        if len(ls) == 0:
            return 1
        else:
            return ls[0] * product2(ls)
    
    def product3(ls):
        if len(ls) == 0:
            return 1
        else:
            ls[0] * product3(ls[1:])
    
    def product4(ls):
        if len(ls) == 0:
            return 1
        else:
            return ls[0] * product4(ls[1:])