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:

Practice problems:

  1. Using the LinkedList implementation from class, work through the code below. You should be able to draw the linked list after every line of code. Note: some professors use different names for the same methods. For example, insertAtTail() might be called append(), insertAtHead() might be prepend(), getData() might be getItem(), and so on...
    LL = LinkedList()
    LL.insertAtTail(30)
    LL.insertAtHead(10)
    LL.insertAtHead(100)
    LL.insertAtTail(56)
    # draw the linked list as it would look here
    
  2. Compare the complexity of python lists and Linked Lists for different operations:
    • What is the big-O complexity of searching an unsorted list versus an unsorted 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 operation.
  3. 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 must break the problem up into a main program and at least one additional function.

    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: pony
    Please enter an integer!
    Enter guess: 588
    Please enter an integer from 1 to 100...
    Enter guess: 75
    Number is lower than 75
    Enter guess: 65
    Number is higher than 65
    Enter guess: 67
    You guessed it in 4 tries!
    


  4. 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 0 course-credits and 0 course load.
    • A registerCurrent method that sets the current course load. The course load must be positive and not greater than 4 credits, otherwise no change happens
    • A withdraw method, which decreases the course load by one credit (but courseLoad should never go below 0).
    • A passedCourse method, which removes one course from the current course load and adds it to the student's 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"