C343 Midterm March 5th, 2020
Name:
Question:
1
2
3
Total
Points:
10
8
7
25
Score:
At the end of the exam, you will documentation for Java classes you might need.
C343 Midterm, Page 2 of 12 March 5th, 2020
1. Short Questions.
(a) (2 points) Recall our implementation of dequeues using dynamic arrays. The gen- eral invariants we used were:
• front points to an empty location;
• back points to an empty location;
• inserting to the front of the dequeue decrements front
• inserting to the back of the dequeue increments back
• when an insertion is not possible because the array is full, a new array of double the capacity is created and all the elements are copied (in the proper order) to the initial segment of the new array
Consider a dequeue in the following state:
back front
We perform the following operations:
• insert 7 to the front; • insert 8 to the front; • insert 9 to the front; • insert 10 to the front; • insert 11 to the back;
Draw the resulting dequeue clearly marking the locations of front and back
456—123
C343 Midterm, Page 3 of 12
(b) (2 points) Consider the same dequeue in the same original state:
back front
We perform the following operations:
• delete from the front; • delete from the front; • delete from the front; • delete from the front;
March 5th, 2020
456—123
Draw the resulting dequeue clearly marking the locations of front and back
C343 Midterm, Page 4 of 12 March 5th, 2020 (c) (2 points) Consider the following hash table with the following parameters:
• hash function h(x) = x mod 10; • quadractic probing
0123456789
We perform the following operations:
• insert 11 • insert 21 • insert 31 • insert 41 • insert 51 • insert 61
Show the state of the table after these insertions.
C343 Midterm, Page 5 of 12 March 5th, 2020
(d) (1 point) Traverse the following tree in pre-order and print the nodes as you visit them:
3
46
87
11 15
13 10 12 9
(e) (1 point) Traverse the following tree in post-order and print the nodes as you visit them:
3
46
87
11 15
13 10 12 9
C343 (f)
Midterm, Page 6 of 12 March 5th, 2020
(2 points) The following test checks that a method sumDiffSquares behaves as excepted. The method is supposed to take a stream of pairs of numbers and return the sum of the squares of the differences of the numbers in each pair:
public void testSDS () {
Stream
Stream.of(new Pair<>(1,4),new Pair<>(4,1),new Pair<>(3,7));
assertEquals(34,sumDiffSquares(pairs));
}
Write the method using the stream interface provided at the end of the exam:
int sumDiffSquares(Stream
}
C343 Midterm, Page 7 of 12 March 5th, 2020
2. Dynamic Programming. An Uber driver is experimenting with various algorithms to solve the following problem. Given that the driver can work a maximum of M minutes, which rides, among a list of possible rides, should be chosen to maximize profit?
(a) (3 points) Consider the following list of 4 rides:
• R1: length = 5, profit = 10 • R2: length = 4, profit = 40 • R3: length = 6, profit = 30 • R4: length = 3, profit = 50
The driver can only work for 10 minutes. The following table can be used to record the maximum profit that can be achieved under various conditions. The top row ranges over the amount of minutes that the driver can work (which is initially 10 minutes). The next row filled with 0 states that the maximum profit if the driver accepts no rides is 0. The row marked with R1 should give the maximum profit by taking only R1 into account. The next row should give the maximum profit by taking only R1 and R2 into account. Then the last row gives the maximum profit taking all the possible rides into account. Your task is to fill the entire table and circle the total profit that the driver can gain in this scenario.
0
1
2
3
4
5
6
7
8
9
10
–
0
0
0
0
0
0
0
0
0
0
0
R1
R2
R3
R4
(b) (1 point) What profit would be computed by a greedy algorithm?
C343 (c)
Midterm, Page 8 of 12 March 5th, 2020
(3 points) Write the method schedule below. You only need to write the plain recursive solution. Do not worry about adding a hash table to memoize the results of repeated recursive calls. The definitions for the classes Ride and Pair are at the end of the exam.
static Pair
schedule(List
(d)
}
(1 point) Construct an example consisting of exactly 4 rides such that the initial call to schedule will compute the final answer using exactly 4 additional recursive calls to schedule.
C343 Midterm, Page 9 of 12 March 5th, 2020
3. Balanced Parentheses. You are given a list of characters. The list may include arbitrary characters but our focus is on the four special characters: (, ), [, and ]. We would like to check if these characters are balanced, i.e., that each opening symbol has a corresponding closing symbol and that the pairs of open-close symbols are properly nested. If the occurrences of the four special characters are balanced, we call the entire list balanced.
(a) (1 point) Should the empty list be considered balanced?
(b) (1 point) Write a list of 4 characters that could be used as a test case for a balanced list.
(c) (1 point) Write a list of 4 characters that could be used as a test case for a non- balanced list.
(d) (1 point) Write another list of 4 characters that could be used as a test case for a non-balanced list. The reason for why this list is not balanced should be distinct from the reason why the list in part (c) is not balanced.
C343 Midterm, Page 10 of 12 March 5th, 2020
(e) (3 points) Write the method matchingParens below. Make sure you read the com- ment carefully and that your solution satisfies the stated requirement.
public class Parens {
static boolean isOpen (char c) {
return c == ’(’ || c == ’[’;
}
static boolean isClose (char c) {
return c == ’)’ || c == ’]’;
}
static boolean match (char c, char d) {
return (c == ’(’ && d == ’)’) || (c == ’[’ && d == ’]’);
}
static boolean matchingParens (List
// solve using a loop and an appropriate helper data structure
// so that the whole algorithm is O(n)
} }
C343 Midterm, Page 11 of 12
March 5th, 2020
The Class: Pair
class Pair
private A a;
private B b;
Pair (A a, B b) { this.a = a; this.b = b; }
A getFirst () { return a; }
B getSecond () { return b; }
}
The Class Hierarchy: List
class EmptyListE extends Exception {}
abstract class List
abstract E getFirst() throws EmptyListE;
abstract List
abstract boolean isEmpty();
abstract int length();
abstract List
}
class Empty
class Node
C343 Midterm, Page 12 of 12
March 5th, 2020
The Class: Ride
public class Ride {
private String name;
private int length;
private int profit;
Ride (String name, int length, int profit) {
this.name = name;
this.length = length;
this.profit = profit;
}
int getLength () { return length; }
int getProfit () { return profit; }
}
Stream Interface
interface Stream
T reduce(T identity, BinaryOperator
}