Test #2
UNIVERSITY OF CALIFORNIA
Department of Electrical Engineering
and Computer Sciences
Computer Science Division
CS61B P. N. Hilfinger
Fall 2016
Test #2
READ THIS PAGE FIRST. Please do not discuss this exam with people who haven’t taken
it. Your exam should contain 10 problems on 13 pages. Officially, it is worth 17 points
(out of a total of 200).
This is an open-book test. You have two hours to complete it. You may consult any
books, notes, or other non-responsive 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 TA 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
Test #2 Login: Initials: 2
Reference Material.
/** Binary tree. */
public class BinTree
/** The label of this node. */
public final Label label;
/** My left and right children. */
public BinTree
public BinTree(Label label, BinTree
this.label = label;
this.left = left;
this.right = right;
}
}
Test #2 Login: Initials: 3
1. [2 points] Give Θ(·) bounds for the best-case and worst-case running times of the
following calls. Where there are multiple parameters to the call, you may be asked to come
up with some expression, E, involving the parameters, as well as bounds on the value of E.
For example, given a method call with arguments X and Y, you might choose E = X + Y
and say that the worst-case running time is in Θ(E2) and the best case is in Θ(E).
Assume that print and println are constant-time operations. For Java library classes,
determine time bounds based on your knowledge of the data structures that underlie them.
(a) What is the complexity of eval(a, b)? Specify a suitable expression for E involving
a and b and bounds on that expression. Assume a <= b.
public static void eval(int N, int M) {
for (int i = N; i < M; i += 1) {
System.out.println(i + " dabs.");
}
}
Best-case bound: Θ( ) Worst-case bound: Θ( )
where E = .
(b) For the same program as in part (a), what is the complexity of eval(N, 100000000)
as a function of N , assuming that N ≥ 0?
Best-case bound: Θ( ) Worst-case bound: Θ( )
(c) What is the complexity of eval(L, v) as a function of N = L.size()?
public static void eval(LinkedList
for (int x : list) {
if (x == value) {
for (int j = 0; j < list.size(); j += 1) { System.out.println(list.get(j)); } } } } Best-case bound: Θ( ) Worst-case bound: Θ( ) Test #2 Login: Initials: 4 (d) What is the complexity of eval(A, K)? Specify a suitable expression for E involving K and A.length and bounds on that expression. Assume K>=0.
public static void eval(int[] array, int M) {
if (M > 0) {
eval(array, M / 2);
}
for (int i = 0; i < array.length; i += 1) {
System.out.println(M + array[i]);
}
}
Best-case bound: Θ( ) Worst-case bound: Θ( )
where E = .
2. [2 points] For each of the following, give the tightest (smallest) and simplest (shortest)
bounds you can. Use Θ(·) if possible, and otherwise O(·).
(a) n2 + 1/n Bound:
(b) n · sin(n) Bound:
(c) ln(x) + ln(1/x) Bound:
(d) 4n + n2n Bound:
Test #2 Login: Initials: 5
3. [2 points] Consider a hash table that uses external chaining and also keeps track of
the number of keys that it contains. It stores each key at most once; adding a key a second
time has no effect. It takes the steps necessary to ensure that the number of keys is always
less than or equal to twice the number of buckets (i.e., that the load factor is ≤ 2). Assume
that its hash function and comparison of keys take constant time. All bounds should be a
function of N , the number of elements in the table.
(a) Give Θ(·) bounds on the worst-case times of adding an element to the table when
the load factor is 1 and when it is exactly 2 before the addition.
Bound for load factor 1: . Bound for load factor 2: ,
(b) Assume that the hashing function is so good that it always evenly distributes keys
among buckets. What now are the bounds on the worst-case time of adding an
element?
Bound for load factor 1: . Bound for load factor 2: ,
(c) Making no assumption about the goodness of the hashing function, suppose that
instead of using linked lists for the buckets, we use some kind of binary search tree
that somehow keeps itself “bushy.” What bound can you place on the worst-case
time for testing to see if an item is in the table?
Bound:
(d) Using the same representation as in part (c), but with a very good hash function, as
in part (b), what bound can you place on the worst-case time for testing to see if an
item is in the table?
Bound:
Test #2 Login: Initials: 6
4. [2 points] Consider a heap of distinct integers implemented using an array, as discussed
in lecture:
public class MaxHeap {
public MaxHeap(int maxSize) {
_data = new int[maxSize];
_size = 0;
}
/** Assuming that all elements of _data[0.._size-1] are distinct
* and satisfy the heap property, except that element #K
* (0 <= K < _size) may be out of order with respect to its ancestors,
* re-arrange _data to make the heap property apply to all
* elements in _data[0 .. _size-1]. */
private void reheapifyUp(int k) { /* Implementation not shown */ }
/** Assuming that all elements of _data[0.._size-1] are distinct
* and satisfy the heap property, except that element #K
* (0 <= K < _size) may be out of order with respect to its
* descendants, re-arrange _data to make the heap property apply
* to all elements in _data[0 .. _size-1]. */
private void reheapifyDown(int k) { /* Implementation not shown */ }
// reheapify and modify methods are on the next page.
// add, removeLargest, getLargest, and other methods not shown.
}
(a) Implement reheapify on the next page.
(b) Implement modify on the next page.
(c) Worst-case running bound for reheapify, whereN = size: .
(d) Worst-case running bound for modify, whereN = size: .
In your solutions to (a) and (b), do not use extra space or pack multiple statements on
a line.
Test #2 Login: Initials: 7
/** Assuming that all elements of _data[0.._size-1] satisfy the
* heap property, ignoring item K (0 <= K < _size), re-arrange
* _data[0 .. _size-1] to make the heap property apply to all
* elements in _data[0 .. _size-1].
private void reheapify(int k) { // Part (a): Fill in
}
/** Remove value OLDVAL from this heap and replace it with NEWVAL,
* maintaining the heap property. Has no effect if OLDVAL is not
* present. */
public void modify(int oldVal, int newVal) { // Part (b): Fill in
}
Test #2 Login: Initials: 8
5. [2 points]
(a) In the blanks to the left of the game-tree nodes below, put the position values as
determined by minimax, assuming the values at the bottom are as shown. Cross out
the branches that would be pruned in an alpha-beta search. Maximizing nodes are
denoted by △; minimizing nodes by ∇.
△
∇
△
3 1
△
9 7
∇
△
-3 2
△
5 0
(b) Give a possible value for a and a value for b such that the indicated branches would
be pruned in an alpha-beta search. If no possible values for a or b exist, state “not
possible.”
△
∇
△
0 7
△
a 5
∇
△
b 3
△
5 1
a value: b value:
Test #2 Login: Initials: 9
6. [2 points] Fill in the function below to obey its comment. Assume that BinTree is
as defined on page 2. For example, if A is the BinTree
trimHigh(A, 13) produces the tree on the right. Your implementation must not create
any new nodes. Also, the label field is marked final; therefore you must not assign to
this field.
4
2 8
6 16
12
10 14
18
4
2 8
6 12
10
/** Destructively modify binary search tree BST, removing all keys
* that are greater than LIMIT. Returns the modified tree. */
public static BinTree
if ( ) {
return ;
} else if ( ) {
return ;
} else {
return ;
}
}
Test #2 Login: Initials: 10
7. [2 points]
(a) Give a single expression that produces the same value as ((x/512) % 64) + 384 for
integral x ≥ 0, but does not use +, -, *, /, or %.
((x/512) % 64) + 384 ==
(b) Describe succinctly what the number printed by the following program is a count of.
Your answer should involve properties of x and y only (not z), and should not make
any mention of the bitwise operations. Assume that all variables are of type int.
z = x ^ y;
n = 0;
for (int i = 0; i < 32; i += 1) { n += 1 & z; z >>>= 1;
}
System.out.println(n);
8. [1 point] Which name among the following does not belong, and why?
Alice Cary, Robert Browning, William Cullen Bryant, Samuel Coleridge-Taylor,
Paul Laurence Dunbar, Eugene Field, Edgar A. Guest, Langston Hughes
Test #2 Login: Initials: 11
9. [1 point] Fill in the definition of patn with a Java pattern string such that the following
method prints the first sequence in S of one or more decimal integer numerals separated
by commas, or nothing if no such sequence exists. You may assume there are no blanks
embedded in the sequences.
static String patn = ;
static void printNumberList(String S) {
Matcher m = Pattern.compile(patn).matcher(S);
if (m.matches()) {
System.out.println(m.group(1));
}
}
For example if S is
“The lottery numbers are 10,7,9,31,22, and yesterday’s were 19,5,29,48,30.”
then printNumberList(S) should print
10,7,9,31,22
Test #2 Login: Initials: 12
10. [2 points] Consider a program for playing a two-person board game, where the board
is represented by the following Board class:
public class Board implements Comparable
/** Return the Boards that result from taking each of the possible
* legal moves from this position. Always non-empty unless gameOver(). */
public Collection
/** Return true iff this is won or drawn position. */
public boolean gameOver() { … }
@Override
public int compareTo(Board b) { … }
}
That is, a Board is a kind of tree whose children are possible next positions in the
game. Board objects are comparable; if A and B are Boards, then A is larger than B iff the
position represented by A is more favorable to the first player (whom we’ll call “white.”)
Just exactly how Board determines this ordering is irrelevant to this problem (you do not
have to implement minimax search.)
We want an iterator over Boards that produces a sequence of Boards that would result
from optimal play, starting with white’s move. That is, a new BoardIterator(b0) (where
b0 must not be null) would first return b0, then the largest child, b1, of b0, then the
smallest child of b1, etc. Complete the following to have this behavior.
/* These might come in handy. Both take a single argument,
* a Collection, and return the object in the collection that is
* last (max) or first (min) in natural order. */
import static java.util.Collections.max;
import static java.util.Collections.min;
public class BoardIterator
public BoardIterator(Board startingBoard) {
}
Test #2 Login: Initials: 13
public boolean hasNext() {
}
/** Assumes hasNext(). */
public Board next() {
}
}
Test #2 Login: Initials: 14