Test #2
UNIVERSITY OF CALIFORNIA
Department of Electrical Engineering
and Computer Sciences
Computer Science Division
CS61B P. N. Hilfinger
Fall 2015
Test #2
READ THIS PAGE FIRST. Please do not discuss this exam with people who haven’t taken
it. Your exam should contain 9 problems on 10 pages. Officially, it is worth 17 points (out of
a total of 200).
This is an open-book test. You have 110 minutes to complete it. You may consult
any books, notes, or other inanimate objects available to you. You may use any program
text supplied in lectures, problem sets, or solutions. Please write your answers in the spaces
provided in the test. Make sure to put your name, login, and lab section in the space provided
below. Put your login and initials clearly on each page of this test and on any additional
sheets of paper you use for your answers.
Be warned: my tests are known to cause panic. Fortunately, this reputation is entirely
unjustified. Just read all the questions carefully to begin with, and first try to answer those
parts about which you feel most confident. Do not be alarmed if some of the answers are
obvious. Should you feel an attack of anxiety coming on, feel free to jump up and run around
the outside of the building once or twice.
Your name: Login:
Login of person to your Left: Right:
Discussion TA:
1. /2 2. /1 3. /2 4. / 5. /2
6. /2 7. /3 8. /3 9. /2
1
Test #2 Login: Initials: 2
1. [2 point] For each of the methods below, give the best case and worst case runtime in
Θ(·) notation, as a function of n. Your answers should be as simple as possible, excluding
unnecessary constants and lower-order terms. Assume there is no limit on the size of an int
(otherwise all run times are technically constant). The answer may be infinity.
a. public static void first(int n) {
for (int outer = 1; outer < n; outer *= 2) {
int inner;
inner = 0;
while (inner < n) {
inner++;
}
}
}
Best case: Θ( ); Worst case: Θ( )
b. public static boolean second(int[] arr) {
int n = arr.length;
for (int index1 = 0; index1 < n; index1 += 1) {
int index2 = index1 + 1;
while (index2 < n) {
if (arr[index1] + arr[index2] == n) {
return true;
}
index2 += 1;
}
}
return false;
}
Best case: Θ( ); Worst case: Θ( )
Problem continues on the next page.
Test #2 Login: Initials: 3
c. public static int third(int n) {
return third(n, n);
}
public static int third(int x, int n) {
if (x == 1) {
return x;
} else {
int sum = 0;
for (int i = 0; i < n; i++) {
sum += third(x - 1, n);
}
return sum;
}
}
Best case: Θ( ); Worst case: Θ( )
d. Ignore the cost of resizing the heap.
public static void fourth(PriorityQueue
int n = in.length;
for(int x : in) {
heap.add(x);
}
}
Best case: Θ( ); Worst case: Θ( )
2. [1 point] Suppose that A is an array of n ints sorted into non-descending order, and
suppose that B is formed from A by adding random integers between −3 and 3 to each element
(so that A = [1, 4, 5, 7] might become [2, 1, 8, 4]). Give best and worst-case times
for insertion sort to sort B back into non-descending order. Justify your answer.
Best case: Θ( ); Worst case: Θ( )
Test #2 Login: Initials: 4
3. [2 points] Given the following (max-) heap,
15
11
2 7
10
6
a. Show what the heap looks like after inserting 1 and then 20 (just show the final heap;
you don’t need to show it just after inserting 1).
b. Starting from the original heap (shown at the top), show what the heap looks like after
removing 15.
Test #2 Login: Initials: 5
4. [1 point] Between 1 January and 1 June, a certain star seems to shift by 1/36000 degrees
against the background of very distant stars. About how far away is it?
5. [2 points] For parts (a) and (b), suppose we have a HashMap implementation that has
an initial capacity of 1, and a load factor of 1. In this hashmap implementation, each resizing
of the hashmap increases the number of buckets by 1. Assume we are using a good hash
function—one that (miraculously) always divides our data sets evenly between the buckets.
Give a Θ(·) worst-case bound for the running times of the following operations. Justify your
answers.
a. Inserting n key-value pairs (assume distinct keys).
b. Looking up a key after the n insertions from part (a).
For parts (c) and (d) now suppose we have the same HashMap implementation, except resizing
doubles the capacity, and we use a hash function that maps all keys to 0. Give a Θ(·) bound
for the average runtime of the following operations. Justify your answers.
c. Inserting n key-value pairs (assume distinct keys).
d. Looking up a key after the n insertions from part (c).
Test #2 Login: Initials: 6
6. [2 points] Suppose the instance methods hashCode1() and hashCode2() in class A are
both “good” hash functions. For each of the following computations, answer whether or not
it is also guaranteed to yield a good hash value and explain why or give an example of a
situation when it wouldn’t be “good.”
a. hashCode1() ^ hashCode2().
b. hashCode1() if hashCode2() is 0 and hashCode2() otherwise.
c. Generate a random number. If that number is odd, yield hashCode1() and otherwise
hashCode2()
d. -hashCode1() if hashCode1() is even, and otherwise hashCode1().
Test #2 Login: Initials: 7
7. [3 points] For each of the parts below, the first lines gives the (same) initial array, and
the remaining lines show the state of the array at major steps during a sort (not necessarily
evenly spaced steps). For each item, indicate which algorithm can generate it: heap sort,
quicksort, LSD radix sort, MSD radix sort, or insertion sort. Assume that quicksort always
chooses the first element in a subsequence as the pivot; the particular partitioning algorithm
might not be the stable one used in homework 8.
a. 658 613 095 997 783 226 754 442 333 572 628 421 291 093 598 257
257 613 095 226 442 333 572 628 421 291 093 598 658 783 997 754
093 095 226 257 442 333 572 628 421 291 613 598 658 783 997 754
093 095 226 257 291 333 421 442 572 628 613 598 658 783 997 754
b. 658 613 095 997 783 226 754 442 333 572 628 421 291 093 598 257
997 783 754 613 658 421 598 442 333 572 628 226 291 093 095 257
783 658 754 613 628 421 598 442 333 572 257 226 291 093 095 997
658 628 598 613 572 421 095 442 333 093 257 226 291 754 783 997
c. 658 613 095 997 783 226 754 442 333 572 628 421 291 093 598 257
421 291 442 572 613 783 333 093 754 095 226 997 257 658 628 598
613 421 226 628 333 442 754 257 658 572 783 291 093 095 997 598
d. 658 613 095 997 783 226 754 442 333 572 628 421 291 093 598 257
613 658 095 997 783 226 754 442 333 572 628 421 291 093 598 257
095 226 613 658 783 997 754 442 333 572 628 421 291 093 598 257
e. 658 613 095 997 783 226 754 442 333 572 628 421 291 093 598 257
095 093 226 291 257 333 442 421 572 598 658 613 628 783 754 997
095 093 226 257 291 333 421 442 572 598 613 628 658 754 783 997
Test #2 Login: Initials: 8
8. [3 points] A certain TrieSet class represents a node such as that shown on the left by
the linked structure shown on the right.
a
b g s
a
a …
b g s
… … …
That is, internal nodes contain the character on the edge leading from their parent (ignored
for the root node), plus a pointer to their first child, plus a pointer to the next sibling node to
their right. Leaf nodes also contain the entire string that they represent (their child pointers
are null). Sibling nodes are linked in order of the characters on the edges leading from their
parents. For simplicity, assume that the end-of-string “character”, which we’ve represented
as ✷ in lecture and in DSIJ, is represented by the ASCII NUL character (in Java, ’\0’), is
always the last character of a key, and only appears at the end. (Usually in Java, unlike C or
C++, there is no explicit end-of-string character actually present, but for this problem, we’ll
pretend that there is).
Below and on the next page is a small part of the Java rendition of this class. You are to
fill in the two private .contains() methods. Each of them takes two parameters: the key
being searched for and the node’s level in the trie (0 for the root).
public class TrieSet implements Set
TrieSet() {
_root = null;
}
…
@Override
public boolean contains(String key) {
if (_root == null) {
return false;
} else {
return _root.contains(key, 0);
}
}
private Node _root;
Continues on next page
Test #2 Login: Initials: 9
Continuation of TrieSet class
private static class Node {
…
/** Return true iff the subtree rooted at me contains KEY,
* assuming that I appear at level K of this trie, and that
* the length of KEY is at least K+1. */
boolean contains(String key, int k) { // FILL IN
}
private char _c;
private Node _firstChild;
private Node _nextSibling;
}
private class LeafNode extends Node {
…
@Override
boolean contains(String key, int k) { // FILL IN
return
}
/** The (single) String represented by this leaf node. */
private String _value;
}
}
Test #2 Login: Initials: 10
9. [2 points]
a. Show the 2-4 tree corresponding to the following red-black tree (shaded nodes are black):
25
8
5
3
15
11 20
30
b. Show an alternative red-black tree that corresponds to the same 2-4 tree as in part (a).
c. If a certain 2-4 tree has a height of H (that is, has H+1 levels) what are the maximum
and minimum heights of the corresponding red-black trees? Do not count the empty
(null) nodes at the bottom of any of these trees in computing heights (so a 2-4 tree
with just a root node has one level and height 0). Your answers should *not* use Θ(·)
notation.
Maximum: ; Minimum:
d. Show two 2-4 trees containing values 1–15 and having maximum and minimum depths.