Quiz 6 Study Guide

You are responsible for all material covered through the end of Week 12.

Python concepts

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

Analysis of algorithms, and run times:
- \(\log N\) — logarithmic (binary search)
- \(N\) — linear (linear search)
- \(N^2\) — quadratic (bubble/selection sort)
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:

compare different runtime analyses for algorithms
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

Binary search is much faster than linear search, so why don’t we use it for every search problem?
Which algorithm requires time directly proportional to the size of the input list?
- linear search
- binary search
- selection sort
Consider the following function:
```
def loops(N):
    for i in range(N):
        for j in range(N):
            print("hello")
```
In terms of the parameter \(N\), how many times will the function print "hello"? That is, is the run time logarithmic, linear, quadratic, or something else?
Consider the following function:
```
def loops(N):
    total = N
    while N >= 1:
        print("hello")
        N = N // 2
```
In terms of the parameter \(N\), how many times will the function print "hello"? That is, is the run time logarithmic, linear, quadratic, or something else?
Consider the following function:
```
def loops(N):
    for i in range(N // 2):
        print("hello")
```
In terms of the parameter \(N\), how many times will the function print "hello"? That is, is the run time logarithmic, linear, quadratic, or something else?

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. 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()
```
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 Employee 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.

Add a new member variable to the class to store the number of awards the employee has won at the company. When you create a new employee, set their number of awards to 0. Add a getter method to the class for this. Add a method called celebrate that takes no parameters and increases the number of awards they’ve won.
Modify the _str_ method to include the number of awards the employee has won.
Add a new method to the class called promote. If the employee has won at least 5 awards, increase their salary by 10%, then decrease the number of awards they’ve won by 5. (This is not a while loop - just do this once.)
Add a call to the promote method in celebrate method so that you can try to promote an employee as soon as they earn 5 awards.

Write some tests in main to test your understanding of how to use the class and the new methods you wrote.


class Employee:

    def __init__(self, name, idno, salary):
        """
        This is the constructor, which is the function that is called
        when an instance of the class (object) is created.
        Parameters:
         * self: refers to this object, i.e. the object being created
         * name (str): the name of the employee
         * idno (int): the employee's ID number
         * salary (float): the employee's annual salary
        Returns: None. The name, id, and salary are modified as a result.
        """
        # note that we need to refer to the name instance of
        # "this object" using the parameter "self"
        self.name = name
        self.idno = idno
        self.salary = salary

    def get_name(self):
        """
        Accessor ("getter") method to access the employee's name.
        Parameter:
         * self: refers to this object; it is implicitly passed as
           an argument when this method is called
        Returns: the value of the name field (str)
        """
        return self.name # note that it is not simply "return name"

    def set_name(self, new_name):
        """
        Mutator ("setter") method to change the employee's name.
        Parameters:
         * self: refers to this object
         * new_name (str): the new name for this employee
        Returns: None. The name field is modified as a result.
        """
        self.name = new_name # note that it is not "name = new_name"

    def get_ID(self):
        """
        Accessor method for employee's ID.
        """
        return self.idno

    def get_salary(self):
        """
        Accessor method for employee's salary.
        """
        return self.salary

    def increase_salary(self, amount):
        """
        Method that increases the employee's salary by the given amount.
        """
        self.salary = self.salary + amount

    def __str__(self):
        """
        Method that creates and returns a string representation of this
        object. This allows us to print the object using the print()
        function.
        """
        return "Name: %s; ID: %d; Salary: %.2f" % \
            (self.name, self.idno, self.salary)

if __name__ == "__main__":
    # This will only execute when employee.py is executed with python3.
    # It will NOT execute when this file is imported into some other file.
    # That makes this a useful place to test your class.

    print("Put test code here!")