Quiz 6 Study Guide

You are responsible for all material covered through the end of Week 13 (Classes and Objects).

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

Python concepts

  • Recursion

    • base case

    • recursive call

    • recursion on numbers, strings, and lists

    • recursion vs iteration

  • Writing Classes

    • the self parameter

    • defining and calling methods

    • initializing and using member variables

    • constructors (__init__())

    • methods to print information about the class

You should be able to

  • trace the execution of a recursive function

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

  • write new methods to add functionality to a class

Practice problems

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

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

  3. 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, False if not

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

  4. Draw a stack diagram for the following program. Show what the stack would look like at it’s largest point (i.e. just before the return statement in the base case). Then write down the complete output of the program (i.e. when main is done running).

    def main():
        n = 5
        ans = factorial(n)
        print(ans)
    
    def factorial(x):
        if x == 0:
          return 1
        else:
          return x * factorial(x-1)
    
    main()
  5. 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'
  6. Consider the StudentRecord class we used for in-class exercises (code below); for each of the following features, modify both the class and the main program as instructed.

    • Academic concern: write a method that returns True if a student’s GPA is below 2.0, then write a function that applies this method to each student in a list, printing out their name if the method returns true.

    • Graduating year: add a member variable to the class to store the year a student will graduate (e.g. 2022); modify the constructor to take an additional argument, then write getter and setter methods for this new field. Next, write a method called years_left() that takes in the current year as a parameter, and returns the number of years remaining before a student graduates (e.g. if the student should graduate in 2024 and the method is passed 2022, it should return 2). Write some code to test out this new functionality.

      
      class StudentRecord(object):
        """
        Remember, the body of an object must all be indented to the same level, just
        like the body of any other block of Python code
        """
      
        def __init__(self, name, age, major, gpa):
          """
          Constructor; parameters are initial values for:
            name (string), age (int), major (string), gpa (float)
          """
          # initialize several member variables with parameter values
          self.name = name
          self.age = age
          self.major = major
          self.gpa = gpa
          # initialize an empty list to store student's grades
          self.grades = []
      
        ##########################
        """
        Getter methods; each returns the value of the appropriate member variable
        """
      
        def get_name(self):
          """ Getter method for name
            - no parameters beyond 'self'
            - returns value of "name" field
          """
          return self.name
      
        def get_age(self):
          """ Getter method for age
            - no parameters beyond 'self'
            - returns value of "age" field
          """
          return self.age
      
        def get_major(self):
          """ Getter method for major
            - no parameters beyond 'self'
            - returns value of "major" field
          """
          return self.major
      
        def get_gpa(self):
          """ Getter method for gpa
            - no parameters beyond 'self'
            - returns value of "gpa" field
          """
          return self.gpa
      
        def get_grades(self):
          """ Getter method for grades
            - no parameters beyond 'self'
            - returns value of "grades" field
          """
          return self.grades
      
        ##########################
        """
        Setter methods; each modifies the value of the appropriate member variable
        """
      
        def set_name(self, newName):
          """ Setter method for name
            - takes a new value for the 'name' field
            - no return value
          """
          self.name = newName
      
        def set_major(self, newMajor):
          """ Setter method for major; must be in list of options
            - takes a new value for the 'major' field
            - no return value
          """
          validMajors = ["CS", "Math", "English", "Philosophy"]
          if (newMajor in validMajors):
            self.major = newMajor
          else:
            print("Warning; trying to set invalid major: \"%s\"" % (newMajor))
      
        def set_age(self, newAge):
          """ Setter method for age
            - takes a new value for the 'age' field
            - no return value
          """
          if (age >= 0):
            self.age = newAge
          else:
            print("Warning; age must not be negative")
      
      
        ##########################
        """
        Modifier methods change values of members, but don't directly assign
        new values to them
        """
      
        def add_grade(self, newGrade):
          """ modifier method for list of grades
            - takes a new grade to add to list
            - no return value
          """
          self.grades.append(newGrade)
      
        def birthday(self):
          """
          Method to run if it's a student's birthday; print a message and
          increment the student's age.
            No parameters or return value.
          """
          print("Happy birthday, %s!", (self.name))
          self.age = self.age + 1
      
        def update_gpa(self):
          """
          Method to re-calculate GPA based on list of grades
          No parameters or return value.
          """
          total = 0
          for i in range(len(self.grades)):
            total = total + self.grades[i]
      
          self.gpa = total / len(self.grades)
      
        ##########################
      
        def toString(self):
          """
          to-string method, returns a string containing info about the student
            No parameters
            returns string
          """
          return "%-12s (age: %d,   major: %s, \tgpa: %.2f)" % \
                  (self.name, self.age, self.major, self.gpa)
      
      ##########################
      # End of class definition
      ##########################
      
      def main():
        """
        main function for testing the class
        """
      
        print("Running tests for StudentRecord class...")
      
        print("Testing constructor...")
        ada = StudentRecord("Ada", 21, "CS", 4.0)
        beth = StudentRecord("Beth", 19, "Math", 3.8)
        cal = StudentRecord("Cal", 20, "English", 3.4)
      
        slst = [ada, beth, cal]
        print("Testing to-string...")
        for s in slst:
          print(s)
      
        print("Testing getter methods...")
        print(ada.get_name())
        print(ada.get_age())
        print(ada.get_major())
        print(ada.get_gpa())
        print(ada.get_grades())
      
        print("testing grade list methods...")
        ada.add_grade(4.0)
        ada.add_grade(4.0)
        ada.add_grade(3.5)
        print("grade list should be: [4.0, 4.0, 3.5]")
        print(ada.get_grades())
        ada.update_gpa()
        print("new gpa should be: 3.83")
        print("%.2f" % ada.get_gpa())
      
      
      
      # only run main if Python was run directly on this file (don't run on import)
      if (__name__ == "__main__"):
        main()