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:
Historically, the final exam includes questions about each of the big
ideas and skills in the course, such as:
- Python expressions and types
- Write a complete program
- Write and test a class
- Trace a program, showing output and the stack diagram
- Recursion and iteration
- Analysis of algorithms
- Searching and sorting
- Linked Lists
Below are some of the new topics covered since the ultimate quiz and
some additional practice problems.
You should be able to define and explain the following terms:
- Recursion and iteration
- Merge Sort: description and analysis of algorithm
- Object-oriented programming, including
- an object's data fields (instance variables)
- the constructor, or __init__ method
- the string, or __str__, method
- access methods, getters, accessors
- update methods, setters, mutators
- Linked lists, including
- the LinkedList class
- the Node class
- the implementation and running time of various LinkedList methods, such as the constructor, insertAtTail, insertAtHead, deleteHead, and getItemAtPosition
- how linked lists differ from Python's consecutive-memory ArrayLists
You should understand and be able to use the following Python concepts:
- 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 data fields that it uses.
- How to implement a LinkedList in Python
- Trace through the following program, writing down any program output
and drawing the stack up until just before the base case return.
print "in foo n = ", n
if n == 0:
# draw the stack here
print "in main"
x = foo(3)
- 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.)
- Using your sumList function above, draw a complete stack diagram for the following program:
ls = [2, 3, 5]
x = sumList(ls)
- Programming exercise 4 on Zelle page 463 (recursive max of list).
- 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.
- Using the LinkedList implementation from class, trace through
the code below. You should be able to draw the linked last after every
line of code is executed. Assumed the LinkedList class has a method
function getHead() that returns the head of the linked list:
Trace through the following code , drawing the resulting linked list,
and list the value and type of each expression given below:
LL = LinkedList()
# (1) draw the linked list as it would look here (after the above insert operations)
curr = LL.getHead()
# (2) List the type and value of these expressions
- For the code in the previous problem, implement a python program
that creates a similar sequence of elements using the python list
class instead of LinkedLists. That is, for each line of code in the linked list
example above, what is the
corresponding expression using python lists?
- Using the LinkedList implementation from class,
write a LinkedList sum method that returns the sum
of the items in the linked list.
- 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.
- 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!
- Write a Student class that stores information for a Swarthmore student.
The class should include the following data fields (or instance variables):
Write the following methods for your Student class:
- 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
- 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.
- An 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 "email@example.com"