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__()
) -
to-string (
__str__()
)
-
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
-
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.
-
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?
-
-
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)
-
find the largest number in a list
-
-
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. whenmain
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()
-
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'
-
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 __str__(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()
-