UC Berkeley – Computer Science
CS61B: Data Structures
Midterm #2, Spring 2018
This test has 9 questions worth a total of 240 points and is to be completed in 110 minutes. The exam is closed book, except that you are allowed to two double sided written cheat sheets (can use front and back on both sheets). No calculators or other electronic devices are permitted. Give your answers and show your work in the space provided. Write the statement out below in the blank provided and sign. You may do this before the exam begins.
“I have neither given nor received any assistance in the taking of this exam.”
Signature: ___________________________
Name: __________________________
SID: ___________________________
Three-letter Login ID: _________
Login of Person to Left: _______
Login of Person to Right: ______
Exam Room: _____________________
Points #
16 14
247 46 288 46 329 30
20
TOTAL 240
There may be partial credit for incomplete answers. Write as much of the solution as you can, but bear in mind that we may deduct points if your answers are much more complicated than necessary. There are a lot of problems on this exam. Work through the ones with which you are comfortable first. Do not get overly captivated by interesting design issues or complex corner cases you’re not sure about.
Not all information provided in a problem may be useful, and you may not need all lines. Unless otherwise stated, all given code on this exam should compile. All code has been compiled and executed before printing, but in the unlikely event that we do happen to catch any bugs in the exam, we’ll announce a fix. Unless we specifically give you the option, the correct answer is not ‘does not compile.’
○ indicates that only one circle should be filled in.
□ indicates that more than one box may be filled in.
For answers which involve filling in a ○ or □, please fill in the shape completely.
Throughout the exam, assume that hash table resizing takes linear time.
Optional. Mark along the line to show your feelings Before exam: [____________________☺]. on the spectrum betweenand☺. After exam: [____________________☺].
#
0
1
2
3 40
Points
5
Tips:
• •
• •
• • • •
UC BERKELEY Login: _______
0. So it begins (1 point). Write your name and ID on the front page. Write the exam room. Write the IDs of your neighbors. Write the given statement and sign. Write your login in the corner of every page. Enjoy your free point☺.
1. Tree time.
a) (4 points). Suppose we have the BST shown below. Give a valid tree that results from deleting “7” using the procedure from class (a.k.a. Hibbard deletion). Draw your answer to the right of the given tree in the box.
b) (4 points). Give an example of a rotation operation on the original tree from 1a (on the left) that would increase the height. You do not need to draw the tree, just write the operation, e.g. “rotateRight(11)”.
c) (4 points). Draw the 2-3 tree that results from inserting 1, 2, 3, 7, 8, 9, 5 in that order.
d) (3 points). Draw the LLRB that results from inserting 1, 2, 3, 7, 8 9, 5 in that order. Write the word “red” next to any red link.
2
CS61B MIDTERM, SPRING 2018
Login: _______
e) (3 points). Draw a valid BST of minimum height containing the keys 1, 2, 3, 7, 8 9, 5.
f) (6 points). Under what conditions is a complete BST containing N items unique? By unique we mean the BST is the only complete BST that contains exactly those N items. By complete we mean the same idea that was required for a tree to be considered a heap (not repeated here). Reminder: We never allow duplicates in a BST.
2. Hash Tables.
a) (5 points). Draw the hash table that is created by the following code. Assume that XList is a list of integers, and the hash code of an XList is the sum of the digits in the list. Assume that XLists are considered equal only if they have the same length and the same values in the same order. Assume that FourBucketHashMaps use external chaining and that new items are added to the end of each bucket. Assume FourBucketHashMaps always have four buckets and never resize. The result of the first put is provided for you. Represent lists with square bracket notation as in the example given.
FourBucketHashMap
fbhm.put(XList.of(1, 2, 3), “cat”);
fbhm.put(XList.of(1, 4), “riding”);
fbhm.put(XList.of(5), “a”);
fbhm.put(XList.of(3, 4), “bull”);
fbhm.put(XList.of(1, 4), “below”);
3
UC BERKELEY Login: _______
b) (4.5 points). Next to the calls to get, write the return value of the get call. Assume that get returns null if the item cannot be found.
FourBucketHashMap
XList firstList = XList.of(1, 2, 3);
fbhm.put(firstList, “cat”);
fbhm.get(XList.of(1, 2, 3)); _____________________
firstList.addLast(0); // list is now [1, 2, 3, 0] fbhm.get(firstList); _____________________
fbhm.get(XList.of(1, 2, 3)); _____________________
c) (10.5 points). Next to the calls to get, write the return value(s) of the get call. Assume that get returns null if the item cannot be found.
FourBucketHashMap
XList firstList = XList.of(1, 2, 3);
fbhm.put(firstList, “cat”);
firstList.addLast(1); // list is now [1, 2, 3, 1]
fbhm.get(firstList);
fbhm.get(XList.of(1,
fbhm.get(XList.of(1,
fbhm.get(XList.of(3,
2, 3));
2, 3, 1));
4));
_____________________
_____________________
_____________________
_____________________
_____________________
_____________________
_____________________
fbhm.put(firstList, “dog”);
fbhm.get(firstList);
fbhm.get(XList.of(1,
fbhm.get(XList.of(1,
2, 3));
2, 3, 1));
d) (4 points). What are the best and worst case get and put runtimes for FourBucketHashMap as a function of N, the number of items in the HashMap? Don’t assume anything about the distribution of keys.
.get best case: .get worst case: .put best case: .put worst case
_Θ__________ _Θ__________ _Θ__________ _Θ__________
e) (4 points). If we modify FourBucketHashMap so that it triples the number of buckets when the load factor exceeds 0.7 instead of always having four buckets, what are the best and worst case runtimes in terms of N? Don’t assume anything about the distribution of keys.
.get best case: .get worst case: .put best case: .put worst case
_Θ__________ _Θ__________ _Θ__________ _Θ__________
As noted on the front page, throughout the exam you should assume that a single resize operation on any hash map takes linear time.
4
CS61B MIDTERM, SPRING 2018
Login: _______
3. Weighted Quick Union.
a) (10 points). Define a “fully connected” DisjointSets object as one in which connected returns true for any arguments, due to prior calls to union. Suppose we have a fully connected DisjointSets object with 6 items. Give the best and worst case height for the two implementations below. The height is the number of links from the root to the deepest leaf, i.e. a tree with 1 element has a height of 0. Give your answer as an exact value. Assume Heighted Quick Union is like Weighted Quick Union, except uses height instead of weight to determine which subtree is the new root.
Best Case Height Worst Case Height
Weighted Quick Union Heighted Quick Union
b) (8 points). Suppose we have a Weighted Quick Union object of height H. Give a general formula for the minimum number of objects in a tree of height H as a function of H. Your answer must be exact (e.g. not big theta).
c) (6 points). Draw a Quick Union tree of 6 objects or fewer that would be possible for Heighted Quick Union, but impossible for Weighted Quick Union. If no such tree exists, simply write “none exists.”
d) (8 points). Create a set for storing SimpleOomage objects Assume that hashCode for SimpleOomage is the perfect hashcode you were expected to write in HW3, where hash code values are unique and always between 0 and 140,607, inclusive.
public class SimpleOomageSet {
private WeightedQuickUnionUF wq = new WeightedQuickUnionUF(____________);
public void add(T item) {
________________________________________
}
public boolean contains(T item) {
________________________________________
}
} // reminder: WeightedQuickUnionUF methods are union() and connected()
4. PNH (0 points). This 1996 simulation video game by Maxis had a hidden feature introduced secretly by a programmer, where on certain dates of the year, “muscleboys in swim trunks” would appear by the hundreds and hug and kiss each other.
5
UC BERKELEY Login: _______
5. Multiset. The Multiset interface is a generalization of the idea of a set, where items can occur multiple times.
public interface Multiset
public void add(T item); // adds item.
public boolean contains(T item); // true if item occurs at least once.
public int multiplicity(T item); // number of times item occurs.
}
For example, if we call add(5), add(5), add(10), add(15), add(5), then the resulting Multiset contains {5, 5, 10, 15, 5}. In this case, multiplicity(5) will return 3.
a) (12 points). A 61B student suggests that one way to implement Multiset is to modify a BST so that it is instead a “Trinary Search Tree”, where the left branch is all items less than the current item, the middle branch is all items equal to the current item, and the right branch is all items greater than the current item. The multiplicity is then simply the number of times that an item appears in the tree. Implement the add method below.
public class TriSTMultiset
private class Node {
private T item;
private Node left, middle, right;
public Node(T i) { item = i; }
}
Node root = null;
public void add(T item) {
_____________________________________________________
}
private Node add(T item, Node p) {
if (p == null) { ________________________________________ }
int cmp = item.compareTo(p.item);
if (cmp < 0) {
_________________________________________________________
} else if (cmp > 0) {
_________________________________________________________
} else {
_________________________________________________________
}
return p;
} …
b) (4 points). Let X be an item with multiplicity M, and let N be the number of nodes in the tree. Give an Omega bound for the best case runtime of any possible implementation of multiplicity(X) for a TriSTMultiset. Give the tightest possible bound you can.
Ω(_____________)
6
CS61B MIDTERM, SPRING 2018
Login: _______
c) (6 points). Rather than implementing an entirely new data structure from scratch, we might consider using delegation or extension to implement Multiset. Which is better, delegation or extension? If delegation, what class should you delegate to? If extension, what class should you extend? If applicable, provide generic types. Fill in one of the bubbles and the corresponding blank below.
○ Delegation to an instance of the __________________________________ class is better. ○ Extending the __________________________________ class is better.
6. Min Heaps (14 points). Consider the min heap below, where each lette represents some value in the tree. For each question, indicate which letter(s) correspond to the specified value. Assume each value in the tree is unique.
a) Assuming values are inserted into the heap in increasing order, indicate all letters which could represent the following values:
Smallest value:
Median value:
Largest value:
□A □B □C □A □B □C □A □B □C
□D □E □F □D □E □F □D □E □F
□G □H □K □L □M □G □H □K □L □M □G □H □K □L □M
b) Assuming values are inserted into the heap in decreasing order, indicate all letters which could
represent the following value:
Smallest value: □A □B □C □D □E □F □G □H □K □L □M
c) Assuming values are inserted into the heap in an unknown order, indicate all letters which could represent the following values:
Median value: □A □B □C □D □E □F □G □H □K □L □M Largest value: □A □B □C □D □E □F □G □H □K □L □M
7
UC BERKELEY Login: _______
7. Iteration.
a) (12 points). Fill in the toList method. It takes as input an Iterable
public class IterableUtils {
public static
__________________________________________
for (_______________________) {
if (___________________) {
__________________________________________
}
_________________________
}
___________________________________
}
} // assume any classes you need from java.util have been imported
b) (8 points). The ReverseOddDigitIterator implements Iterable
ReverseOddDigitIterator rodi = new ReverseOddDigitIterator(12345770);
for (int i : rodi) {
System.out.print(i);
}
Write a JUnit test that verifies that ReverseOddDigitIterator works correctly using your toList method from before. Use the List.of method, e.g. List.of(3, 4, 5) returns a list containing 3 then 4 then 5.
import org.junit.Test;
import static org.junit.Assert.*;
public class TestRODI {
@Test
public void testRODI() {
ReverseOddDigitIterator odi = new ReverseOddDigitIterator(__________);
________________________________________________________________
________________________________________________________________
________________________________________________________________
}
} // assume any classes you need from java.util have been imported
8
CS61B MIDTERM, SPRING 2018
Login: _______
c) (18 points). Fill in the implementation of the ReverseOddDigitIterator class below. public class ReverseOddDigitIterator implements Iterable
Iterator
private int value;
public ReverseOddDigitIterator(int v) {
value = v; }
public boolean hasNext() {
if (value == 0) {
return ___________________;
}
if (_______________________) {
return ________________;
} else {
value = value / 10;
return ________________________;
}
}
public Integer next() {
int d = ___________________________;
value = ___________________________;
return d; }
public Iterator
return _____________________;
// hint: this class should // be implemented
// so that the example
// code that prints
// 77531 on the previous
// page works.
}
} // assume any classes you need from java.util have been imported
d) (8 points). If you didn’t complete part c, assume it is completed and compiles. For each of the following, which file (if any) will fail to compile as a direct result of the removal? By “direct result”, we mean the compilation failure is not caused by a dependency failing to compile.
Suppose we remove “implements Iterable
Suppose we instead remove implements Iterator
○ IterableUtils ○ TestRODI ○ ReverseOddDigitIterator Suppose we instead remove the hasNext method, which file will fail to compile?
○ IterableUtils ○ TestRODI ○ ReverseOddDigitIterator
Suppose we instead remove the iterator method, which file will fail to compile? ○ IterableUtils ○ TestRODI ○ ReverseOddDigitIterator
○ None ○ None ○ None
9
UC BERKELEY Login: _______
8. Asymptotics
a) (12 points). Give the runtime of the following functions in Θ notation. Your answer should be a function of N that is as simple as possible with no unnecessary leading constants or lower order terms. Don’t spend too much time on these!
_Θ_____ public static void g1(int N) {
for (int i = 0; i < N*N*N; i += 1) {
for (int j = 0; j < N*N*N; j += 1) {
System.out.print("fyhe");
} }
}
_Θ_____ public static void g2(int N) {
for (int i = 0; i < N; i += 1) {
} }
int numJ = Math.pow(2, i + 1) - 1; // <-- constant time!
for (int j = 0; j < numJ; j += 1) {
System.out.print("fhet");
}
_ Θ_____ public static void g3(int N) {
for (int i = 2; i < N; i *= i) {}
for (int i = 2; i < N; i++) {}
}
b) (4 points). Suppose we have an algorithm with a runtime that is Θ(N2 log N) in all cases. Which of these statements are definitely true about the runtime, definitely false, or there is not enough information (NEI)?
O(N2 log N) Ω(N2 log N) O(N3)
Θ(N2 log4 N)
c) (6 points). Suppose we have an algorithm with a runtime that is O(N3) in all cases.
○ True ○ True ○ True ○ True
○ False ○ False ○ False ○ False
○ NEI ○ NEI ○ NEI ○ NEI
There exists some inputs for which the runtime is Θ(N2) There exists some inputs for which the runtime is Θ(N3) There exists some inputs for which the runtime is Θ(N4) The worst case runtime is O(N3)
The worst case runtime has order of growth N3
○ True ○ True ○ True ○ True ○ True
○ False ○ False ○ False ○ False ○ False
○ NEI ○ NEI ○ NEI ○ NEI ○ NEI
10
CS61B MIDTERM, SPRING 2018
Login: _______
d) (12 points). Give the best and worst case runtime of the following functions in Θ notation. Your answer should be as simple as possible with no unnecessary leading constants or lower order terms. Don’t spend too much time on these! Assume K(N) runs in constant time and returns a boolean.
public static void g4(int N) {
if (N == 0) { return; }
g4(N - 1);
if (k(N)) { g4(N - 1); }
}
Best case: _Θ_______
Worst case: _Θ_______
public static void g5(int N) {
if (N == 0) { return; }
g5(N / 2);
if (k(N)) { g5(N / 2); }
}
Best case: _Θ_______
Worst case: _Θ_______
e) (6 points). Give the best and worst case runtime of the code below in terms of N, the length of x. Assume HashSets use the idea of external chaining with resizing used in class, and that resize is linear. public Set
HashSet
for (int i = 0; i < x.size(); i += 1) {
items.add(x.get(i));
}
return items;
}
Best case runtime for uniques: _ Θ_____ Worst case runtime for uniques: __Θ_____
f) (6 points). Consider the same code from part b, but suppose that instead of Planets, x is a list of Strings. Suppose that the list contains N strings, each of which is length N. Give the best and worst case runtime.
Best case runtime for uniques: _ Θ_____ Worst case runtime for uniques: __Θ_____
11
UC BERKELEY Login: _______
9. (30 points). Imagine that we have a list of every commercial airline flight that has ever been taken, stored as an ArrayList
The trick we use to store a flight start time (or end time) as an int, rather than as some sort of Time object, is to store the number of minutes that had elapsed in the Pacific Time Zone since midnight on January 1st, 1914, which was the first day of commercial air travel.
For example, a flight taking off at 2:02 PM on March 6th, 1917 and landing at 3:03 PM the same day carrying 30 passengers would have takeoff time 1,671,243, landing time 1,671,304, and number of passengers 30.
Give an algorithm for finding the largest number of people that have ever been in flight at once.
Your algorithm must run in N log N time, where N is the number of total commercial flights ever taken. Your algorithm must not have a runtime that is explicitly dependent on the number of minutes since January 1st, 1914, i.e. you can’t just consider each minute since that day and count the number of passengers from each minute and return the max.
Your algorithm may use any data structures discussed in the course (e.g. arrays, ArrayDeque, LinkedListDeque, ArrayList, LinkedList, WeightedQuickUnion, TreeMap, HashMap, TreeSet, HashSet, HeapMinPQ, etc.)
a. List any data structures needed by your algorithm, including the type stored in the data structure (if applicable). If you use a data structure that requires a compareTo or compare method, describe briefly how the objects are compared. Do not include the provided ArrayList
b. Briefly describe your algorithm in plain English. Be as concise and clear as possible.
12