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:

Sorting: selection and merge sort
Recursion and iteration
Object-oriented programming, including
- methods
- an object's instance variables
- the constructor, or __init__ method
- the string, or __str__, method
- access methods, getters
- update methods, setters

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

swapping two values in a list
various sorting algorithms
complexity (big O, number of steps) of sorting algorithms
string comparisons ("alice" < "zelda")
how variables are stored and function arguments are passed on the stack for recursive functions
how to create a Python object, including its constructor, string method, and the instance variables that it uses

Practice problems:

Multiple choice questions 1, 2, and 6 on page 461 (Chapter 13)
Discussion question 1 on page 462 (Chapter 13)
Programming exercise 4 on Zelle page 463.
Write a sort function (any sort) that takes in a list and sorts it in place. Show what a call to your sort function would look like from main.
Write a function to return the index of the smallest item in a given list.
Show how the following list would be changed after selection sort does its first 3 swaps:
```
[15, 99, 4, 30, 3, 82, 7, 42]
```

In the following problem, the recursive function isPalindrome takes a string as an argument, returning True if the string is a palindrome and False otherwise. Draw a stack diagram for the program until the first time at which the program reaches the line marked with a comment below.

def main():
    ans = isPalindrome("badjab")
    print ans

def isPalindrome(s):
    if len(s) <= 1:
        result = True
    elif s[0] != s[len(s)-1]:
        result = False
    else:
        result = isPalindrome(s[1:len(s)-1])
    # draw stack diagram here
    return result

main()

Write a Student class that stores information for a Swarthmore student. The class should include the following instance variables:
- id, an integer identifier for the student
- firstName, a string
- lastName, a string
- courses, a list of strings, the course names that the student is enrolled in
- hobbies, a list of strings, the student's hobbies
Write the following methods for your Student class:
- A constructor that, given an id, a first name, and a last name, creates a Student with those values and empty lists of courses and hobbies.
- A string method that returns a string representing the student.
- Getter methods for each of the instance variables in the class.
- An addCourse method that, given a course name, adds that course to the student's course list.
- An addHobby method that, given a hobby name, adds that hobby to the student's hobby list.
- A getCredits method that returns the number of courses a student is enrolled in.
- A getFreeTime method that returns the value 55 - 12*number-of-courses - 5*number-of-hobbies. (Alternatively, this method could just return 0.)