Introduction to Computer Science

Final Exam Study Guide

The final exam for this course is comprehensive: it covers all of the material we have discussed this semester, a list of which can be found on the Course Schedule. You are encouraged to use all of the following material to prepare yourself for the final exam:

Exam Composition

The final exam will consist of eight multi-part questions, each of which will cover a topic that we have discussed in class. As a general rule, any topic on which we have had a lab assignment is an example of a topic about which a question may be asked (recursion, classes and objects, loops, etc.). Questions may also be asked regarding material given significant attention during lecture (e.g. algorithmic complexity). You will not be asked questions about material which was not covered either in lecture or lab. We expect that this exam will take most students between 1½ to 2 hours; the exam is scheduled in a 3 hour time slot.

During the exam, you may be expected to

The quizzes administered during class give examples of all of these tasks.

Practice Questions

In addition to the previous study guides, labs, and quizzes, the following is a collection of practice questions which should help you prepare for the exam.

Types

Determine the value to which each of the following expressions evaluates. Then, give the Python type of that value.

Functions

Write both iterative and recursive functions to perform the following tasks:

Classes and Objects

Consider the following code:

class Turtle(object):
  def __init__(self, name):
    self.name = name
    self.diet = "lettuce"
  def __str__(self):
    return "A turtle named %s that eats %s" % (self.name, self.diet)
  def get_diet(self):
    return self.diet
  def set_diet(self, diet):
    self.diet = diet
  def can_eat(self, food):
    return food == self.diet
    
def main():
  turtle = Turtle("Sanjana")
  print turtle
  print turtle.can_eat("lettuce")

main()

Given the above, answer the following questions:

Now, write a class called TurtleFarm which keeps track of zero or more turtles. It should have the following methods:

Complexity

What is the complexity of each of the following algorithms on a list of size n? (Note: the links below lead to Wikipedia pages which contain the answer. Try to guess answers for all of these before clicking the links.)

Consider the following code:

def make_special_list(n):
  lst = []
  for i in range(n):
    for j in range(n):
      for k in range(n):
        lst.append(i+j+k)
  return

What is the complexity of this method in terms of n?

Searching and Sorting

Consider the following list:

    [   'a'  ,  'c'  ,  'd'  ,  'e'  ,  'h'  ,  'i'  ,  'j'  ,  'm'  ,  'o'  ,  'q'  ,  'r'  ,  't'  ,  'v'  ,  'x'  ,  'z'  ]
(index)  0       1       2       3       4       5       6       7       8       9      10      11      12      13      14

Show how a binary search would proceed on this list by giving the values of L, R, and M determined at each step.

The bubble sort algorithm consists of two loops: an inner loop (which compares and may swap a single pair of elements) and an outer loop. Given the list [3,6,1,2,8,2,4,5], show how bubble sort will change that list after each iteration of the outer loop.

Tracing and Debugging

For each of the following two programs, draw a stack trace for the moment that the program reaches the comment # HERE.

def f(x):
  if x > 0:
    # HERE
    print "Positive!"
    return x * 2
  else:
    print "Not positive!"
    return x + 5

def main():
  x = -3
  x = f(x)
  x = f(x)
  x = f(x)

main()

class TicketDispenser(object):
  def __init__(self):
    self.counter = 0
  def next_ticket(self):
    # HERE
    return self.counter + 1

def main():
  dispenser = TicketDispenser()
  for n in range(5):
    print dispenser.next_ticket()

main()

Suppose the second program was intended to print the numbers of the first 5 tickets in the ticket dispenser (which should be 1, 2, 3, 4, and 5). There is a bug in this program. Identify it and explain how to correct it.

Writing Programs

Write a program which determines what a student’s course letter grade will be depending on how well they do on their final exam. You will ask the user for the name of a file which contains 3 lines. Those lines are:

From this information, you should:

Given the above data, your program might output

Final exam score:  60   Course grade: 83.1
Final exam score:  65   Course grade: 84.4
Final exam score:  70   Course grade: 85.7
Final exam score:  75   Course grade: 87.0
Final exam score:  80   Course grade: 88.4
Final exam score:  85   Course grade: 89.7
Final exam score:  90   Course grade: 91.0
Final exam score:  95   Course grade: 92.3
Final exam score: 100   Course grade: 93.6

You should write at least three functions (including your main function).

Remember: try to write this program without the aid of the Python interpreter! You will be expected to write a similar program on paper during the exam.

Linked Lists

Consider the linked list code we used in the most recent lecture (found here). Add to that code the following methods: