1. The problem was to complete the following method, making use of methods associated to the "List with Cursors" paradigm, as covered in lecture and lab.
/* Removes the k-th occurrence of x from the given list.
** Example: Suppose list is [5, 3, 9, 3, 7, 5, 6, 3],
** x is 3, and k is 2. Then the effect is to remove
** the 2nd occurrence of 3 from this list, changing its
** value to [5, 3, 9, 7, 5, 6, 3]
*/
public static void removeKth(ListWithCursors list, Object x, int k) {
|
Solution: Crucial to coming up with a solution is to recognize the need for a cursor to traverse the given list in search of the k-th occurrence of x within that list (if such an occurrence exists). It follows that the method body should start by creating a cursor (using list.getCursor()) and positioning it at the front of the list (using the cursor's toFront() method).
Meanwhile, in order for the cursor to traverse the list in search of the k-th occurrence of x, it is necessary to have a loop in which the cursor moves forward (using its toNext() method) and in which a count is kept of how many occurrences of x have been encountered so far. Of course, to keep such a count requires a variable be used for that purpose. To determine whether the "current" list element (i.e., the one at which the cursor is positioned) is an occurrence of x (and thus should be counted), there is a need to compare x (using the equals() method) against the value stored in the current node (which can be obtained using the cursor's getItem() method).
If and when the k-th occurrence of x is encountered, the cursor's remove() method should be employed to remove that occurrence. We should also allow for the possibility that there are fewer than k occurrences of x in the list, in which case the search should end (with no elements having been removed) when the cursor has reached the rear of the list.
public static void removeKth(ListWithCursors list, Object x, int k) {
ListCursor cursor = list.getCursor();
cursor.toFront();
int count = 0;
// loop invariant: count == # of occurrences of 'x' preceding
// the cursor's position within 'list'
while (count != k && !cursor.atRear()) {
if (x.equals(cursor.getItem())) {
count++;
if (count == k) { cursor.remove(); }
}
cursor.toNext();
}
cursor.dispose();
}
|
In the following solution, we wait until after the loop has terminated before doing the removal (if appropriate).
public static void removeKth2(ListWithCursors list, Object x, int k) {
ListCursor cursor = list.getCursor();
cursor.toFront();
int count = 0;
// loop invariant: count == # of occurrences of 'x' preceding the cursor's
// position within 'list'
while (count != k && !cursor.atRear()) {
if (x.equals(cursor.getItem())) {
count++;
}
cursor.toNext();
}
// assertion: Either 'cursor' is at the rear of 'list' or
// at the successor of the k-th occurrence of 'x'.
if (count == k) {
cursor.toPrev().remove();
}
cursor.dispose();
}
|
2.
4 / \ / \ 2 7 | /|\ | / | \ 5 0 3 6 | / \ \ 1 8 10 11 |
The history of the queue is the following:
+----+----+----+----+----+----+----+----+----+----+----+----+
| 4 | 2 | 7 | 5 | 0 | 3 | 6 | 1 | 8 | 10 | 11 | |
+----+----+----+----+----+----+----+----+----+----+----+----+
Enqueued at 1 3 4 6 8 9 10 12 15 16 18
Dequeued at 2 5 7 11 13 14 17 19 20 21 22
|
A number of students seemed to be confused by "Enqueued at" and "Dequeued at". What they are meant to convey is the order in which insertions (i.e., enqueues) and deletions (i.e., dequeues) occurred within the queue. Given that eleven items were inserted, and later removed, from the queue, 22 actions occurred. To show the order in which they occurred, each of the numbers 1 through 22 should appear.
As you will recall, the algorithm that is the focus of this problem follows this logic: Each loop iteration removes the vertex ID at the front of the queue and then "explores" from that vertex, placing onto the rear of the queue the ID of any "not-yet-discovered" vertex to which it (i.e., the vertex being "explored from") has an edge.
Regarding the example graph of this problem, the first action to occur on the queue (which happens prior to the loop) is the insertion of the ID of the source vertex, 4. During the first loop iteration, 4 is removed from the queue (making that the 2nd action to occur) and exploration from that vertex results in 2 and 7 being inserted into the queue, making those the 3rd and 4th actions. During the second loop iteration, 2 is removed from the queue, making that the 5th action to occur, and 5 is placed onto the queue, making that the 6th action. The third loop iteration sees the removal of 7 from the queue (the seventh action), followed by the insertions of 0, 3, and 6, making those the 8th, 9th, and 10-th actions, respectively. And so on and so forth.
Final contents of array returned:
0 1 2 3 4 5 6 7 8 9 10 11
+----+----+----+----+----+----+----+----+----+----+----+----+
dist | 2 | 3 | 1 | 2 | 0 | 2 | 2 | 1 | 3 | -1 | 3 | 3 |
+----+----+----+----+----+----+----+----+----+----+----+----+
|
3.
public interface RBC<T> {
boolean isRed(T elem);
boolean isBlue(T elem);
}
| |||
public class GoodChar implements RBC<Character> {
private String redChars; // instance variable
/* Establishes that the characters occurring in the given String are to be
** classified as RED while all other characters are to be classified as BLUE.
*/
public GoodChar(String s) { this.redChars = s; } // constructor
/* Returns true iff the given character occurs in 'redChars', which
** (by the comments preceding the constructor) makes it a RED character.
*/
public boolean isRed(Character ch)
{ return redChars.indexOf(ch) != -1; }
/* Returns true iff the given character is non-RED, which makes it BLUE.
*/
public boolean isBlue(Character ch)
{ return !isRed(ch); }
|
/* Returns the string obtained from s by omitting (i.e., filtering out) all ** occurrences of those characters that the given RBC object classifies as ** being non-RED. Example: Suppose that only vowels are classified as being ** RED. Then if s were "The cat in the hat", the string returned would be ** "eaiea". */ public static String onlyRed(String s, RBC |
4.
public static int blorp(int k, int m) {
if (k == 1) { return m; }
else if (k % 2 == 0) // k is even
{ return blorp(k/2, m+m); }
else // k is odd and > 1
{ return blorp(k-1, m) + m; }
}
| ||
| k | m | value returned |
|---|---|---|
| 19 | 3 | 57 (54+3) |
| 18 | 3 | 54 |
| 9 | 6 | 54 (48+6) |
| 8 | 6 | 48 |
| 4 | 12 | 48 |
| 2 | 24 | 48 |
| 1 | 48 | 48 |
There are two recursive cases, one applying when k is even and the other applying when k is odd but not equal to one. In the former case, the values passed in the recursive call are k/2 and m+m. That explains, for example, why the instance of the method that received k:18 and m:3 passed k':9 and m':6 in making a recursive call.
In the latter case (when k is odd), the parameters passed in the recursive call are k-1 and m. This explains, for example, why the instance of the method that received k:19 and m:3 sent values k':18 and m':3 in making a recursive call.
Understanding that much makes it possible to fill in the first two columns of the table, all the way to the bottom row, which describes the instance of the method that receives k:1 and m:48. That is where the base case of k=1 has been reached, and so (in accord with the Java code) the value of m, 48 is returned.
To fill in the third column in all the rows above, we have to work from bottom to top. Observing the Java code, it is clear that any instance of the method that received an even-valued k returns whatever value was produced by the call that it made to itself. That explains why, for example, 48 is returned by the intances of the method that received k values of 2, 4, and 8.
As for the instance that received k:9 and m:6, its call to itself produced 48, so it produces 48 + m, which is 48 + 6, or 54.
Taking a mathematician's point of view, observation of the blorp() method's code makes it clear that it computes a function with this (recursive) definition:
| blorp(k,m) = { | m | if m=1 | (1) |
| blorp(k/2,m+m) | if k is even | (2) | |
| blorp(k-1,m) + m | if k>1 and k is odd | (3) |
An astute observer might recognize this to be a recursive definition of multiplication (where k is restricted to be positive)! To evaluate blorp(), we can simply apply this definition. Here is an example:
blorp(19,3) = blorp(18,3) + 3 (by (3)) = blorp(9,6) + 3 (by (2)) = blorp(8,6) + 6 + 3 (by (3)) = blorp(4,12) + 6 + 3 (by (2)) = blorp(2,24) + 6 + 3 (by (2)) = blorp(1,48) + 6 + 3 (by (2)) = 48 + 6 + 3 (by (1)) = 57 (by arithmetic) |
5. The problem was to supply the missing body of the sizeOfIntersection() method, which computes the number of elements in the intersection of the two given sets of persons.
/* Returns the number of elements in the intersection of sets A and B.
*/
public static int sizeOfIntersection(SetOfPerson A, SetOfPerson B) {
Iterator<Person> iter = A.iterator();
int count = 0;
while (iter.hasNext()) {
Person p = iter.next();
String name = p.nameOf();
if (B.isMemberOf(name)) { count++; }
}
return count;
|
The instructor finds it puzzling that several students who submitted versions of SetOfPerson in which the intersectionWith() method was perfect were unable to produce a reasonable solution to this problem, even though the logic to solve it is virtually the same.