Quiz 5 Study Guide

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

Python concepts

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

Sorting: selection sort
Analysis of algorithms, and run times:
- $\log N$ — logarithmic (e.g. binary search)
- $N$ — linear (e.g. linear search)
- $N^2$ — quadratic (selection sort)
Recursion:
- base case
- recursive call
- recursion on numbers, strings, and lists
- recursion vs iteration

You should be able to:

trace the execution of selection sort
compare different runtime analyses for algorithms
trace the execution of a recursive function
write a recursive function that takes a number, string and/or list as a parameter

Practice problems

Assume you have a StudentRecord class that contains the following methods:

StudentRecord(name, age, major, gpa): creates a new StudentRecord object
              name: the student's name    (string)
              age: the student's age     (int)
              major: the student's major (string)
              gpa: the student's gpa     (float)

get_age(): returns the age value (int)
get_gpa(): returns the gpa value (float)
get_major(): returns the major value (string)
get_name(): returns the name value (string)

Write a function majors that takes a list of StudentRecord objects and a float representing a GPA, and returns a list of the distinct majors of students whose GPA is greater than the specified value.

For instance, the following code should print ['Computer Science', 'Math']:

s1 = StudentRecord("Bluey", 7, "Computer Science", 3.8)
s2 = StudentRecord("Bingo", 5, "Computer Science", 3.7)
s3 = StudentRecord("Bandit", 31, "Math", 3.3)
s4 = StudentRecord("Chilli", 30, "Math", 3.6)

students = [s1, s2, s3, s4]

print(majors(students, 3.5))

Note that "Computer Science" should only be included in the returned list once, even though there are two students whose GPA is greater than 3.5 and have "Computer Science" as their major.

Which algorithm requires time directly proportional to the size of the input list?
- linear search
- binary search
- selection sort
Consider a pair of nested loops in a 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?
Show how the list L=[17,4,19,3,11,8] would be changed after selection sort does its first 3 swaps.

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 the 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:" +  str(result))

main()

What is the return type of the recursive function?
What is the base case(s)?
What is the recursive case?
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 a recursive function called numbers that takes a string s and an int idx as its parameters and returns a new string that contains only the numbers found in string s starting at index idx. For example:
```
def main():
    print(numbers("$3,141.59", 0)) # "314159"
    print(numbers("52ze47mk3n", 1)) # "2473"
    print(numbers("982", 0)) # "982"
    print(numbers("quiz", 0)) # ""
    print(numbers("867-5309", 2)) # "75309"
```
Hint: s.isdigit() will return True if the string s represents a digit.