CS21: Final Exam Study Guide

The final exam is cumulative. In addition to the concepts below, you should know the concepts that were tested on all the quizzes in the course: Quiz 1, Quiz 2, Quiz 3, Quiz 4, Quiz 5, Quiz 6.

Historically, the final exam includes questions about each of the big ideas and skills in the course, such as:

Below are some of the new topics covered since the last quiz and some additional practice problems.

You should be able to define and explain the following terms:

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

Practice problems:

  1. Trace through the following program, writing down any program output and drawing the stack up until just before the base case return.
       def foo(n):
         print "in foo n = ", n
         if n == 0:
            # draw the stack here
            return 1
         else:
            return 5*foo(n-1)
    
       def main()
          print "in main"
          x = foo(3)
          print x
    
  2. Write a recursive sumList function that takes a python list of integers as an argument and returns the sum of the items in the list. What is the base case of your function? What is the recursive case? (Note: this problem is asking about regular Python lists, not linked lists.)
  3. Using your sumList function above, draw a complete stack diagram for the following program:
    def main():
        ls = [2, 3, 5]
        x = sumList(ls)
    
  4. Programming exercise 4 on Zelle page 463 (recursive max of list).
  5. Show the merge-sort tree for the list L = [1, 9, 5, 2, 0, 3, 4, 6, 8, 7]. Here is an example of a merge-sort tree, where the top-half represents the split phase and the bottom half the merge phase.
  6. Using the LinkedList implementation from class, trace through the code below. You should be able to draw the linked list after every line of code. Assumed the LinkedList class has a function getHeadNode() that returns the head of the linked list.
    def getHeadNode():
      return self.head
    
    After tracing the code, give the value and type of each expression below:
    LL = LinkedList()
    LL.insertAtTail(30)
    LL.insertAtHead(10)
    LL.insertAtHead(100)
    LL.insertAtTail(56)
    
    # draw the linked list as it would look here
    curr = LL.getHeadNode()
    
    ###Give the type and value of these expressions
                                        TYPE       VALUE
                                        ----       -----
    LL
    curr
    curr.getValue()
    curr.getNext()
    curr.getNext().getValue()
    
  7. For the code in the previous problem, implement a python program that creates a similar sequence of elements using the python list instead of LinkedLists. That is, for each line of code, what is the corresponding expression using python lists?
  8. Using the LinkedList implementation from class, write a LinkedList sum method that returns the sum of the items in the linked list.
  9. Compare the complexity of python lists and Linked Lists for different operations. What is the big-O complexity of searching an unsorted list versus linked list? How about if the list/linked list is sorted? What is the big-O complexity of inserting an item at the beginning of each list representation? How about at the end of each list? In some cases, python lists and linked lists may have different complexities for the same problem.
  10. Using the LinkedList implementation from class, write a LinkedList deleteTail method that deletes the tail of a linked list and returns the value of the item that was stored at the tail. Before attempting this, write pseudo-code for the deleteTail method; it's harder than the deleteHead method from class! To delete the tail, you need to set the new tail to be the Node before the current tail; to do that, you need to find that Node by traversing through the list.
    • In big-O notation, how does the running time of deleteHead depend on the size of the linked list, N?
    • In big-O notation, how does the running time of deleteTail depend on the size of the linked list, N?
  11. Write a complete program that plays a guessing game with numbers. The goal is for the user to guess a randomly selected number between 1 and 100 as quickly as possible. The program will inform the user whether the hidden number is higher or lower than the current guess. You can assume that the user will always enter integers, but you must verify that the integers entered are between 1 and 100. You must break the problem up into a main program and at least two additional functions.

    The following is a sample run of the program:

    I'm thinking of a number between 1 and 100.
    Enter guess: 50
    Number is higher than 50
    Enter guess: 588
    Invalid, try again: 75
    Number is lower than 75
    Enter guess: 62
    Number is lower than 62
    Enter guess: 56
    You guessed it in 4 tries!
    

  12. 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
    • lastName, a string for the student's last name
    • credits, an integer representing the number of course-credits the student has earned
    • courseLoad, an integer representing the current number of credits in progress
    Write the following methods for your Student class:
    • A constructor that, given an id, and a name, creates a Student with those values and no course-credits and no course load.
    • Accessor (getter) and mutator (setter) methods for each piece of data encapsulated by the class.
    • A registerCurrent method that sets the current course load. The course load must be positive and no greater than 4 credits, otherwise no change happens
    • A withdraw method, which decreases the course load by one credit, but never goes below 0.
    • A passedCourse method, which removes one course from the current course load and adds to the students overall course-credits.
    • A createEmail method, which returns a string. The string should be an email address of the student's name combined with their ID and the post-fix @swarthmore.edu. For example, a student with last name "Soni", and ID 25 should return "soni25@swarthmore.edu"