Objects and Data Structures Midterm Exam 1
Name:
October 3, 2016
1
1 Stacks and Queues
Consider the following minimal implementations of a Stack and a Queue using a python list.
class Stack :
def def def def def
init (self): self.items = []
push( self , item ):
self .items.append(item)
pop(self):
return self.items.pop() isEmpty( self ):
return len(self.items)==0
str (self):
return str(self.items)
class Queue:
def def def def def
init (self): self.items = []
enqueue( self , item ):
s e l f . items . i n s e r t (0 , item )
dequeue( self ):
return self.items.pop() isEmpty( self ):
return len(self.items)==0
str (self):
return str(self.items)
Below each code listing, write the output printed by the program. Recall that a list gets printed with brackets and commas as in [0, 42, “Hello,world”].
1.1 (5 points) 1.2 (5 points)
1.3 (5 points)
s = Stack() q = Queue() s . push (0)
s . push (1)
q . enqueue (4)
q . enqueue ( s . pop ( ) ) q . enqueue ( s . pop ( ) ) q . enqueue (2)
s . push (4)
s . push (3)
print(s)
print(q)
s = Stack() q = Queue()
q . enqueue q . enqueue q . enqueue s . push (1) s . push (3) s . push (2) s . push ( q . q . enqueue q . enqueue q . enqueue print(s) print(q)
(1) (3) (2)
dequeue ( ) )
( q . dequeue ( ) ) ( q . dequeue ( ) ) ( s . pop ( ) )
s = Stack() q = Queue() q . enqueue (5) s . push (1)
s . push (0)
s . push ( q . dequeue ( ) ) q . enqueue ( s . pop ( ) ) q . enqueue (2)
s . push (3)
print(s)
print(q)
2
2 Linked Lists
Suppose we wanted to take a linked list L of integers and replace each one by itself modulo 3. That is, given a linked list containing [2, 4, 7], it modifies it so that its elements are [2, 1, 1]. Below are several attempts. Assume that L is not empty and that every node has an integer for data. It is intentional that the method does not return anything. Explain what (if anything) is wrong with each function.
def reduceMod3 (L ) :
for i in range(len(L)):
current.setData(current.getData() % 3) current = current.getNext()
2.1 (5 points)
def reduceMod3 (L ) : current = L. head
while current is not None: x = current . getData () x=x%3
current = current.getNext()
2.2 (5 points)
def reduceMod3 (L ) : current = L. head
while current is not None:
current = current.getNext() current.setData(current.getData() % 3)
2.3 (5 points)
3
2.4 (5 points) In each of these examples, if one calls reduceMod3(myList) does the code modify the Linked List, myList, or just a copy of it? Explain. (Think about boxes and arrows if that helps you.)
2.5 (10 points) Implement the reduceMod3 function when the input is a python list instead of a linked list.
def reduceMod3 (L ) : .
. . . . . . .
2.6 (10 points) Fill in the code for the following method that takes a linked list L and a positive integer k and returns True if the first items in the linked list sum up to exactly k. Otherwise, it returns False. For example if the list L has items [1,2,1,3,1] in that order, then prefixSum(L,k) returns true if and only if k is 1, 3, 4, 7, or 8. This is because 1 = 1, 3 = 1 + 2, 4 = 1 + 2 + 1, 7 = 1 + 2 + 1 + 3, and 8 = 1 + 2 + 1 + 3 + 1.
def prefixSum(L,k): .
. . . . . . .
4
3 Asymptotic Analysis
Here are a collection of functions on a python list L. If the length of L is n, give the worst- case, asymptotic running time of each of the following methods in terms of n. Recall that concatenating lists of lengths m and n takes O(m + n) time. Indexing into a list and finding the length take O(1) (constant) time.
Be careful. There are tricks! 3.1 (3 points)
3.2 (3 points)
3.3 (3 points)
3.4 (3 points)
3.5 (3 points)
def alpha(L): x=0
for i in range(len(L)): x += i
return x
def beta(L):
for i in range(alpha(L)):
j = i % len(L) L[j] = L[j] + L[j]
return L
def gamma(L):
return alpha ( beta (L))
def delta(L):
for i in range(len(L) ∗ len(L)):
return i
def epsilon(L): x=2
i=1
while i < len(L):
x = xˆ2 i=2∗i
return x
5
4 Lists vs. Linked Lists
4.1 (10 points) Give three operations that are asymptotically faster on a linked list than on
a python list. 1.
2. 3.
4.2 (5 points) Give one operation that is asymptotically faster on a python list than on a linked list. Bonus points for more.
1. 2.
6
5 Recursion
Don’t forget the last question on the bottom of the page!
Binary search is a classic example of an algorithm that is easiest to implement recursively. If the list L is sorted, the following method will work.
5.1 (5 points) What is the asymptotic running time of this code in terms of n = length(L). Put your answer in the code box.
def binarySearch(L, k, i = 0, j = None): if j is None:
j = len(L) if i == j−1:
return i if k==L[i] else −1 mid = (i + j) // 2
else :
if L[mid] <= k:
return binarySearch (L, k , mid ,
j ) return binarySearch (L, k , i , mid)
5.2 (5 points) If the list is not sorted, we can modify the code so it still produces the right answer. The code is given below. What is the worst-case asymptotic running time in terms of n = length(L). Put your answer in the code box.
def binarySearch2(L, k, i = 0, j = None): if j is None:
j = len(L) if i == j−1:
return i if k==L[i] else −1 mid = (i + j) // 2
right = binarySearch2 (L, k , if right != −1:
return right else :
return binarySearch2 (L,
mid ,
k , i ,
j )
mid)
5.3 (5 points) Given a list L of length n. For which element of L will binarySearch2 make the fewest recursive calls? How many such calls will be made?
7