Java Book

CS 61B: Data Structures (Spring 2002) Midterm I Solutions Problem 1. (6 points) Quickies. a. Another name for static fields is class variables. b. Advantages of a linked list over an array (any one will suffice): • •

An item can be inserted at the beginning of a linked list without the need to move all the other items. The size of a linked list can always be increased by one quickly (specifically, in O(1) time) without ever taking the time to allocate and copy a whole array (which takes O(n) time).

c. Advantages of an array over a linked list (any one will suffice): • •

Any single item can be read or changed quickly (specifically, in O(1) time) simply by knowing its position in the array. An array takes less memory (by a constant factor) than a linked list to store the same number of items.

d. Yes. myMethod can be overloaded by a second implementation of myMethod in MyClass that has a different signature. myMethod can be overrided by a third implementation of myMethod in a subclass of MyClass that has the same signature. Problem 2. (8 points) Inheritance. a. m returns 5 b. int i = ((XPlus) x).r(); c. return super.m(); d. The very last line of code causes a compile-time error. All the other lines compile and run without incident. Problem 3. (5 points) Lists made of cons cells. public static void main(String[] args) { Cons v = new Cons(); v.cdr = new Cons();

}

v.cdr.cdr = new Cons(); v.cdr.cdr.cdr = v.cdr; v.car = 2; v.cdr.car = 3; v.cdr.cdr.car = 9;

Problem 4. (6 points) Loops made of cons cells. public void breakLoop() { if (cdr != null) { if (cdr.car == -1) { cdr = null; } else { int i = car; car = -1; cdr.breakLoop(); car = i; } } }

Extra credit bonus point: Create a special Cons cell named dummyCons, which is not part of any list. Instead of marking Cons cells by setting car to -1, mark them by setting cdr to dummyCons. Mail inquiries to [email protected]

CS 61B: Data Structures (Spring 2002) Midterm II Solutions Problem 1. (6 points) Quickies. a. Theta(1) best-case time. b. Theta(n) worst-case time. c. Nodes J and P are pruned. d.

Problem 2. (7 points) Binary Search Trees. a. 3, 4, 5, and 6. b. Advantages of a binary search tree over a hash table (any one will suffice): • • • • • •

Finding the smallest key greater than or equal to x is often faster. So is finding the smallest key, period. So is finding the largest key. So is finding the largest key less than or equal to x. Binary search trees don't need to be resized. A binary search tree allows you to print its contents in sorted order in linear time. A hash table doesn't really. (You can sort the contents of a hash table with a lineartime sort, but that's obviously a lot more trouble.)

c. Do an inorder traversal of the tree. Return the kth node visited. (Note: we won't give full marks for a correct algorithm that isn't as asymptotically fast as this one.) d. Theta(k + h) time. (Your answer may differ if you gave a slower algorithm for 2c. In that case, you may lose points on 2c for slowness but get full points here if you analyze your algorithm correctly.)

e. Do a standard BST findElement() operation, but use position fields in place of keys. (P.S. note that the position fields satisfy the binary search tree invariant.) Problem 3. (7 points) Converting Directed Graphs to Undirected Graphs. a. public static void directedToUndirected(boolean[][] adjMatrix) { for (i = 0; i < adjMatrix.length; i++) { for (j = 0; j < adjMatrix.length; j++) { if (adjMatrix[i][j]) { adjMatrix[j][i] = true; } } } }

b. Theta(v2) time. c. There are many possibilities. Here's the simplest one.

Problem 4. (5 points) Asymptotic Analysis. Because f(n) is in Theta(j(n)), f(n) is in Omega(j(n)), so there exist positive constants c1, N1 such that f(n) >= c1 j(n) for all n >= N1. Similarly, because g(n) is in Theta(j(n)), g(n) is in O(j(n)), so there exist positive constants c2, N2 such that g(n) <= c2 j(n) for all n >= N2. Putting the two facts together, we find that alpha f(n) - beta g(n) >= (alpha c1 - beta c2) j(n) for all n >= max{N1, N2}. If you choose alpha and beta so that alpha c1 - beta c2 > 0, it follows by the definition of big-Omega that alpha f(n) - beta g(n) is in Omega(j(n)). For example, you could choose alpha = 2/c1 and beta = 1/c2.

Mail inquiries to [email protected]

CS 61B: Data Structures (Spring 2000) Midterm I Solutions Problem 1. (6 points) Quickies. a. The class with no superclass is Object. b. An immutable object cannot be modified. c.

d. The class MyHouse will compile if implementations are provided for both prototypes of throughTheRoof (each of which takes a different parameter). e. Binary search begins by inspecting the middle element of a list or sublist thereof. If the list is linked, you will have to traverse half the nodes in the list/sublist to reach the middle one. Assuming you start traversing from the left end, it will take binary search just as long to reach any given node as it would take a naive search. Problem 2. (12 points) Bug Hunt. The compile-time errors and their fixes are as follows. •

•

The field List.size is private, but the methods DList.copyList and DList.toDList change its value. size should be declared protected, or at least public or package. In the abstract List class, the method toDList should be declared abstract. Alternatively, you could provide an implementation (which will always be overridden anyway).

•

•

The static method copyList attempts to use this, but this isn't defined in a static method. The line ``this.size = dbl.length();'' should read ``dbl.size = sngl.length();''. (The dbl-sngl mixup is my mistake, and we'll go easy on grading your correction to this line.) The method DList.toDList tries to reference newList.head, but the static type of newList is List, and there's no head field in the class List. Here are two fixes. o Change the declaration of newList: ``DList newList = new DList();''. o Cast newList: ``((DList) newList).head = head;''.

The logical errors are both in DList.copyList. •

The line of code that creates the sentinel doesn't create a sentinel that points to itself. The line is ``dbl.head = new DListNode(null, dbl.head, dbl.head);''. When the DListNode constructor is called, the value of dbl.head is still null; dbl.head isn't assigned an object until after the constructor finishes executing. Hence, the prev and next fields of the sentinel are still null. (Many of you encountered this bug during Homework 4, and it was also discussed on the newsgroup. Lesson: read the newsgroup.) One solution is to follow the dysfunctional line with the lines ``dbl.head.prev = dbl.head; dbl.head.next = dbl.head;''.

•

When a new node is inserted at the end of the doubly-linked list, the sentinel's prev pointer is not adjusted. The line ``oldTail.next = newNode;'' should be accompanied by the line ``dbl.head.prev = newNode;''.

Problem 3. (7 points) Condensing Alternate Pairs of Strings in a Singly-Linked List. public void condense() { SListNode n = head; while (n != null) { if (n.next != null) { n.item = (String) n.item + (String) n.next.item; n.next = n.next.next; size--; } n = n.next; } }

Mail inquiries to [email protected]

CS 61B: Data Structures (Spring 2000) Midterm I Solutions Problem 1. (6 points) Quickies. a. The class with no superclass is Object. b. An immutable object cannot be modified. c.

d. The class MyHouse will compile if implementations are provided for both prototypes of throughTheRoof (each of which takes a different parameter). e. Binary search begins by inspecting the middle element of a list or sublist thereof. If the list is linked, you will have to traverse half the nodes in the list/sublist to reach the middle one. Assuming you start traversing from the left end, it will take binary search just as long to reach any given node as it would take a naive search. Problem 2. (12 points) Bug Hunt. The compile-time errors and their fixes are as follows. •

•

The field List.size is private, but the methods DList.copyList and DList.toDList change its value. size should be declared protected, or at least public or package. In the abstract List class, the method toDList should be declared abstract. Alternatively, you could provide an implementation (which will always be overridden anyway).

•

•

The static method copyList attempts to use this, but this isn't defined in a static method. The line ``this.size = dbl.length();'' should read ``dbl.size = sngl.length();''. (The dbl-sngl mixup is my mistake, and we'll go easy on grading your correction to this line.) The method DList.toDList tries to reference newList.head, but the static type of newList is List, and there's no head field in the class List. Here are two fixes. o Change the declaration of newList: ``DList newList = new DList();''. o Cast newList: ``((DList) newList).head = head;''.

The logical errors are both in DList.copyList. •

The line of code that creates the sentinel doesn't create a sentinel that points to itself. The line is ``dbl.head = new DListNode(null, dbl.head, dbl.head);''. When the DListNode constructor is called, the value of dbl.head is still null; dbl.head isn't assigned an object until after the constructor finishes executing. Hence, the prev and next fields of the sentinel are still null. (Many of you encountered this bug during Homework 4, and it was also discussed on the newsgroup. Lesson: read the newsgroup.) One solution is to follow the dysfunctional line with the lines ``dbl.head.prev = dbl.head; dbl.head.next = dbl.head;''.

•

When a new node is inserted at the end of the doubly-linked list, the sentinel's prev pointer is not adjusted. The line ``oldTail.next = newNode;'' should be accompanied by the line ``dbl.head.prev = newNode;''.

Problem 3. (7 points) Condensing Alternate Pairs of Strings in a Singly-Linked List. public void condense() { SListNode n = head; while (n != null) { if (n.next != null) { n.item = (String) n.item + (String) n.next.item; n.next = n.next.next; size--; } n = n.next; } }

Mail inquiries to [email protected]

CS 61B: Data Structures (Spring 2000) Midterm II Solutions Problem 1. (7 points) Quickies. a. The minimax algorithm could be said to be using either a preorder or a postorder tree traversal. (Either answer was accepted as correct.) b. The maximum height of an n-node binary search tree is n - 1. c. Pruning does not affect the answer produced by minimax. d. x2z + xy. e. Use two hash tables; one for authors and one for publishers. f. None. Because of the finally clause, the only exception that can be thrown is a NullPointerException, which is unchecked. Problem 2. (6 points) Data Structures. a.

b.

c.

Problem 3. (4 points) Merging Trees. Set T's root to be the root of R. Find the node in R with maximum key. Set that node's right child to be the root of S. Problem 4. (8 points) Inserting a Key into a Binary Heap. public void insertItem(int key) { int i = size + 1; while ((i > 1) && (key < heapArray[i / 2])) { heapArray[i] = heapArray[i / 2]; i = i / 2; } heapArray[i] = key; size++; }

Mail inquiries to [email protected]

CS 61B Fall 1998 Final Exam Solutions Problem 1: b. 7

/

\

3

/ 12 / \

/ \ 1

=>

6 9 15 / \ / 5 11 14

6

/ 3

/ \ 1

6

/ 5

\ 12 / \ 11 15 / 14

OR

\ 12 / \

/ \ 1

3

9

5

9 15 \ / 11 14

c. Theta(n), Omega(n), or 0(n) d. Wf Xg e. insert() may cause the array to run out of space. f. Any sequence of operations that 1) Ends with the right keys in the tree and 2) Ends with insert(2) or find(2) is correct g. Worse: 19 bytes Only in the latter case can the memory formerly occupied by W objects be reused for X objects. Problem 2: a. X 3 4 5 5 12 8 9 7 b.

7 / \

5 / \

2

9 \

6

10

/ \

1

3

c. a b d c f g E

--->A<--------D<--------^ | | G | / | / | / | B<--------C F | | |

Problem a. 5 8 1 0 3 8 1 0 3 0 1 8 3 0 1 5 0 3 1 5 0 1 3 5 0 1 3 5 0 1 3 5

3: 7 7 7 7 7 7 7 5

3 5 5 5 5 5 5 7

9 9 9 9 9 9 8 8

5 5 5 8 8 8 9 9

b. One portion might get all the keys, the other portion none. c. (i) Insertion sort: 2 (ii) Selection sort: k (iii) Quicksort (array-based): k (iv) Radix sort: p Problem 5: a. Walk through both lists in same order as merge step in mergesort. Write common elements to output list. O(s + t) = O(max{s, t}) b. For each item in T, check if it's in S (by binary search). Write common items to output array. O(t log s) c. For each item in SMALLER set, check if it's in larger set using hash

table. Write common item to output list & output hash table. O(min{s, t}) Problem 6: a. The nodes are stored on the stack. b. Two possible answers: 1. Put all red nodes (or green nodes, but not both) in the queue with a depth of zero. Mark them visited. Then continue running BFS as usual. 2. Augment the graph with an extra vertex u, which has edges to every red vertex (or every green vertex, but not both). Run BFS starting from u. Problem 7: a. Possible answers: 1. Tree has extra field for minimum item. The end of every insert() or delete() calls the log-n version of findMin and stores the minimum item in the field. 2. Tree has extra field for minimum item. Update on insert() is obvious. delete() takes us to the lower left leaf if we delete the minimum, so we can just look up the new minimum. 3. Maintain pointer to leftmost leaf. b. - Lists are doubly-linked - Objects have references to their locations in lists c. Lazy deletion list can grow very long, so find() is not O(log n). Problem 8: public DSElement find() { if (parent == null) { return this; } parent = parent.find(); return parent; } public void union(DSElement other) { DSElement thisRoot = this.find(); DSElement otherRoot = other.find(); if (thisRoot != otherRoot) { if (thisRoot.rank > otherRoot.rank) { otherRoot.parent = thisRoot;

} else { thisRoot.parent = otherRoot; if (thisRoot.rank == otherRoot.rank) { otherRoot.rank++; } } }

}

CS 61B Spring 2000 Final Exam Solutions Problem 1: b. 3 /

3

\

4 / \

/ \

5 6 4 / \ / \ 5 9 8 7

8

c. Omega(log n) d. Theta(1) e. y is in x's left subtree. f. Theta(n) time, because of roving pointer. g. If data you're still using is deallocated, new data may be written over it. h. False Problem 2: a. 9 / \ 2

OR 10

/ \ 1

\

2

10

/ \

6 / \

1

3

9

/ 3

\

7

7 / \

\ 8

6

8

b. Yes. 3 / \ 2

1 \ 4

findElement(1)

2

/

\

1

5

------------->

\

3

\

4 \

5

c.

(log n) k * ------(log k) or k log n (where log is base k) problem a. 7 4 2 8 4 7 2 8 4 7 2 8 4 7 2 8 2 4 7 8 0 1 2 3

3: 1 1 0 0 0 4

0 0 1 1 1 6

6 6 6 3 3 7

3 3 3 6 6 8

0 7 7 7 6

6 6 6 6 7

3 3 3 8 8

mergesort b. 7 4 0 4 0 1 0 1 0 1

2 2 2 2 2

8 8 8 3 3

1 1 4 4 4

selection sort c. 7 4 4 2 4 8 8 0 0 1

2 8 0 1 2

8 0 1 2 3

1 6 2 3 4

0 7 6 4 6

6 1 7 6 7

3 3 3 7 8

6 6 6 6 6 8 7

3 3 3 3 3 3 8

radix sort d. 7 4 4 7 2 4 1 2 0 1 0 1 0 1

2 2 7 4 2 2 2

8 8 8 7 4 4 3

1 1 1 8 7 6 4

0 0 0 0 8 7 6

insertion sort e. -Do not rotate the list to find a pivot; or if you do, rotate it back to its original state. -Do not remove pivot from list before partitioning. -Partition into 3 lists: less than pivot, equal to pivot (including pivot), greater than pivot. Sort first & last recursively. Problem 4: | | | ____________ | | | | | | | ___ |<---------------------------------------\ | |value | 7 | | | | | | |___| | | | | | ___ | | | | |next |_--+-+--------\ | | |____________| | | | | | | | | ____________ | | | | | |<-------/ ______________ | | | ___ | | | ____ | | | |value | 3 | | | | value |_?__| | | | | |___| | | | ____ | | | | ___ | | | next | | | | | |next | | | | | |_---+-+----/ | | |_--+-|------------------->|______________| | |____________| | | ^ ^ | | | | | HEAP |-----------|--|---| | main() | | | | __ | | | | x | -+--/ | | | |__| | | | __ | | | y | -+-----/ | | |__| | |__________________| STACK

Problem 5: a. 2 / | \ 0 6 7 /

1

5 / \

3 / \

9

4

8

b. find(4) union(2, 5) find(8) Final: -----2------/ | \ \ \ 0 6 7 5 3 8 | / \ 9 1 4 /

c. Scan through array, find all children of ITEM. If ITEM is not root, make ITEM's children point to its parent. If ITEM is a root, choose arbitrary child to be new root; make other children point to it. d. One possibility: Use a general sibling-based tree data structure, but make siblings be doubly-linked so path compression is fast. Another possibility: Each set's root references a linked list of all the items in the set (which does NOT need to be doubly linked). When sets are unioned, these lists are concatenated. isolate() walks through the list to find all children of item (and also removes item from the list). Problem 6: a. No. x is passed by value, cannot be changed. Strings are immutable. b. Yes. x may be a class variable (static) or object field accessible to foo(), so x can be changed by foo(). c. Yes. x may be passed by reference.

Problem 7: a. O(log x + log y + x/y) b. f(n) is in O(n sqrt(n)): n Sum (sqrt(i)) <= choosing i=1

n Sum (sqrt(n)) = n sqrt(n) is in O(n sqrt(n)) by i=1

c = 1 and N = any constant. f(n) is in Omega(n sqrt(n)): n n n Sum (sqrt(i)) >= Sum (sqrt(i)) >= Sum (sqrt(ceil(n/2))) >= i=1 i=ceil(n/2) i=ceil(n/2) ceil(n/2) sqrt(ceil(n/2)) >= (n/2) sqrt(n/2) = [n sqrt(n)] / [2 sqrt(2)].

[n sqrt(n)] / [2 sqrt(2)] is in Omega(n sqrt(n)) by choosing d = 1 / [2 sqrt(2)] or smaller and N = any constant. OR by showing n sqrt(n) is in O([n sqrt(n)] / [2 sqrt(2)]) by choosing c = 2 sqrt(2) or larger and N = any constant. Problem 8: int[] counts = new int[range]; for (int i = 0; i < sortMe.length; i++) { counts[sortMe[i]]++; } int index = 0; for (int i = 0; i < range; i++) { for (int j = 0; j < counts[i]; j++) { sorted[index] = i; index++; } }

CS 61B: Practice for the Final Exam

We will cover some of these questions for review, but please attempt these questions before that comes to pass. Starred problems are particularly difficult. Warning: final.

Midterm 1 topics are absent here, but will reappear on the

[1] Given an array containing the digits 71808294, show how the order of the digits changes during each step of [a] insertion sort, [b] selection sort, [c] mergesort, [d] quicksort (using the array-based quicksort of Lecture 31, and always choosing the last element of any subarray to be the pivot), and [e] heapsort (using the backward min-heap version discussed in Lecture 30). Show the array after each swap, except in insertion sort. For insertion sort, show the array after each insertion. [2] not

Some sorting methods, like heapsort and array-based quicksort, are

naturally stable. Suggest a way to make _any_ sorting algorithm stable by extending the keys (making them longer and adding extra information). [3] f

Consider the graph at right.

17 |15 [a] |

e |

In what order are the vertices visited using DFS starting from vertex a?

Where a choice exists, use

9 | 1

alphabetical order. What if you use BFS? c---g---h [b] A vertex x is "finished" when the recursive call | / DFS(x) terminates. In what order are the vertices 11| /5 finished? (This is different from the order in |/ which they are visited, when DFS(x) is called.) d---i [c] In what order are edges added to the minimum 14 spanning tree by Kruskal's algorithm? List the edges by giving their endpoints. [4] [a] contains use an

| 3 | a--|

|

|7 9| |

|

b--12

How long does it take to determine if an undirected graph a vertex that is connected to no other vertices [i] if you adjacency matrix; [ii] if you use adjacency lists.

[b]

root.

to the [c] are two tell if [d] path

Suppose we use DFS on a binary search tree, starting from the The edge to a left child is always traversed before an edge right child. In what order are the nodes visited? Finished? An undirected graph contains a "cycle" (i.e., loop) if there different simple paths by which we can get from one vertex to another. Using breadth-first search (not DFS), how can we an undirected graph contains a cycle? Recall that an undirected graph is "connected" if there is a from any vertex to any other vertex.

is not

that

If an undirected graph

connected, it has multiple connected components. A "connected component" consists of all the vertices reachable from a given vertex, and the edges incident on those vertices. Suggest an algorithm based on DFS (possibly multiple invocations of DFS) counts the number of connected components in a graph.

[5] 3

What does the splay tree at right look like after: /

\ [a]

5

maxElement()

1 /\

/\ 4

[b]

11

insertItem(4.5)

\

2

| Start from the _original_ tree,

/ \ 7

0

[c] 12

findElement(10)

| not the tree resulting from the | previous operation.

/ \ [d]

9

remove(9)

/

6

/ \ 8

10

[6] Consider the quick-union algorithm for disjoint sets. We know that a sequence of n operations (unions and finds) can take asymptotically slightly more than linear time in the worst case. [a] [b] * -----

Explain why sequence of Explain why sequence of

if all the finds are done before all the unions, a n operations is guaranteed to take O(n) time. if all the unions are done before all the finds, a n operations is guaranteed to take O(n) time.

[7] [a] |3 5| ----[b]

/ | \

--- --|4| |6|

Suggest a sequence of insertion operations

4

that would create the binary tree at right.

/ \

Suggest a sequence of operations that would create the 2-3-4 tree at right.

You are

allowed to use removal as well as insertion.

Suppose an application uses only three operations: findElement(), and remove().

[a] Under what circumstances of a hash table? [b] Under what circumstances of a splay tree? [c] Under what circumstances instead of a 2-3-4 tree? [d] Under what circumstances of an unordered array?

6

/ \ 1

----3

|1 2| -----

--- --[8]

2

insertItem(),

would you use a splay tree instead would you use a 2-3-4 tree instead would you use an unordered array would you use a binary heap instead

[9] [a] Suppose we are implementing a binary heap, based on reference-based * binary trees (_not_ arrays). We want to implement a deleteRef() operation which, given a _reference_ to a node in the tree, can delete that node (and the item it contains) from the heap while maintaining the heap-order property--even if the node isn't the root and its item isn't the minimum. deleteRef() should run in O(log n) time. How do we do it? [b] Building on your answer to the previous question, explain how to combine a min-heap and max-heap (both using reference-based binary trees) to yield a data structure that implements insertItem(), deleteMin(), and deleteMax() in O(log n) time. Hint: You will need inter-heap pointers. Think of how you deleted edges in Project 3, for example. [c] How can we accomplish the same thing if we use array-based heaps? Hint: Add an extra field to the items stored in each array.

[10] Recall that the linked-list version of quicksort() puts all items whose * keys are equal to the pivot's key into a third queue, which doesn't need to be sorted. This can save much time if there are many repeated keys. The array-based version of quicksort() does not treat items with equal keys specially, so those items are sorted in the recursive calls. Is it possible to modify array-based quicksort() so that the array is partitioned into three parts (keys less than pivot, keys equal to pivot, keys greater than pivot) while still being in-place? (The only memory you may use is the array plus a constant amount of additional memory.) Why or why not? [11]

Suppose we wish to create a binary heap containing the keys D A T A S T R U C T U R E. (All comparisons use alphabetical order.) [a]

Show the resulting min-heap if we build it using successive insertItem() operations (starting from D).

[b] Show the resulting min-heap if we build it using bottomUpHeap(). [12] the

Suppose we modify the array-based quicksort() implementation in Lecture 31 notes to yield an array-based quickselect() algorithm,

as

described in Lecture 35.

median

letter in D A T A S the 7th letter, which would letters.) As in Question [1], the pivot, and show the

Show the steps it would use to find the

T R U C T U R E.

(The median in this case is

appear at array index 6 if we sorted the choose the last element of any subarray to be array after each swap.

[13] C++ objects can be declared on the stack, on the heap, or in static storage, just like structures. Consider the following C++ code. class ListNode { public: int number; ListNode *next; }; class List { public: ListNode *head;

| | | | | | | | |

void dumbRoutine(int i, int j) { List myList; ListNode node2; myList.head = new ListNode(); myList.head->number = i; myList.head->next = &node2; myList.head->next->number = j;

} [a] certain [b] thereby

|

}

If a program calls dumbRoutine() frequently, is the program to suffer from a memory leak? If a program calls dumbRoutine() frequently, is the program

susceptible to having some of its data inadvertently corrupted? [c] If the declaration "List myList;" is moved outside of dumbRoutine(), so that myList is a global variable, the answers to both [a] and [b] change. Explain why. [14] What's wrong with this heap allocation strategy? We keep all allocated chunks on the heap contiguous. Whenever a free() or delete operation occurs, we find the position of the newly freed chunk, then we move all the chunks to the right of it leftward to fill the gap. That way, no fragmentation occurs at all! Allocation requests are satisfied using the first free memory, to the right of all the allocated chunks. ----------------------------------------------------------------|&&***&&*******&&**&&****&&...... &&***&&**&&****&&............... ----------------------------------------------------------------^free() [15]

=>

|

What are the values of the four elements of the array x after the following C code is executed? int x[4]; int *p; p = &x[1]; p[2] = 20; p = &p[1]; *p = 8; *x = 33;

[16] Suppose our radix-sort algorithm takes exactly n+r seconds per pass, where n is the number of keys to sort, and r is the radix (number of queues). To sort 493 keys, what radix r will give us the best running time? With this radix, how many passes will it take to sort 420bit keys? To answer this question, you'll need to use calculus (and a calculator), and you'll need to remember that log2 r = (ln r) / (ln 2).

[17] its

Suppose that while your computer is sorting an array of objects, memory is struck by a cosmic ray that changes exactly one of the

keys

to something completely different. For each of the following sorting algorithms, what is the _worst-case_ possibility? For each, answer [x] the final array won't even be close to sorted, [y] the final array will have just one or two keys out of place, or [z] the final array will consist of two separate sorted subsets, one following the other, plus perhaps one or two additional keys out of place. [a] [b] [c] [d]

Insertion sort Selection sort Mergesort Radix sort

Programming questions. [18] The

Rewrite the quicksort() method from the Lecture 31 notes in C++. signature should appear as follows. void quicksort(Comparable *a, int length) { Note one big change from the Java version:

array,

instead of passing an

a low index, and a high index, we pass only an array and its length (the number of items to be sorted). The call above should sort the elements a[0] through a[length - 1]. The reason only two parameters are needed for the recursion is because the Java call quicksort(a, x, y) can be replaced by the C++ call quicksort(&a[x], y-x+1). Be careful to make sure that your array indices are correct in your C++ version. [19] Implement tree sort (as described in the sorting video) in Java. Assume your treeSort() method's only input parameters are the number of items and a complete (perfectly balanced) BinaryTree of depth d in which each leaf has an item; hence, there are 2^d items to sort. All internal nodes begin with their item field set to null. Use the data structures below (in which each node knows its left and right child), not a general tree.

Your algorithm should never change a node reference; only the items move. The centerpiece of your algorithm will be a method that fills an empty node by (i) recursively filling its left and right children if they're empty, and (ii) choosing the smaller of its children's items, which is moved up into the empty node. treeSort() will repeatedly: (i) apply this method to the root node to find the smallest item remaining in the tree, (ii) pluck that item out of the root node, leaving the root empty again, and (iii) put the item into an array. Your treeSort() should allocate and return that array. {

class BinaryTreeNode {

root;

|

class BinaryTree

Comparable item;

|

BinaryTreeNode

BinaryNode leftChild; BinaryNode rightChild;

| | |

}

/* OpenCommercial.java */ import java.net.*; import java.io.*;

}

/** A class that provides a main function to read five lines of a commercial * Web page and print them in reverse order, given the name of a company. */ class OpenCommercial { /** Prompts the user for the name X of a company (a single string), opens * the Web site corresponding to www.X.com, and prints the first five lines * of the Web page in reverse order. * @param arg is not used. * @exception Exception thrown if there are any problems parsing the * user's input or opening the connection. */ public static void main(String[] arg) throws Exception { BufferedReader keyboard; String inputLine; keyboard = new BufferedReader(new InputStreamReader(System.in)); System.out.print("Please enter the name of a company (without spaces): "); System.out.flush(); /* Make sure the line is printed immediately. */ inputLine = keyboard.readLine(); /* Replace this comment with your solution to Problem 1 on page 81. */ }

}

/* Date.java */ import java.io.*; class Date {

/* Put your private data fields here. */ /** Constructs a date with the given month, day and year. If the date is * not valid, the entire program will halt with an error message. * @param month is a month, numbered in the range 1...12. * @param day is between 1 and the number of days in the given month. * @param year is the year in question, with no digits omitted. */ public Date(int month, int day, int year) { } /** Constructs a Date object corresponding to the given string. * @param s should be a string of the form "month/day/year" where month must * be one or two digits, day must be one or two digits, and year must be * between 1 and 4 digits. If s does not match these requirements or is not * a valid date, the program halts with an error message. */ public Date (String s) { } /** Checks whether the given year is a leap year. * @returns true if and only if the input year is a leap year. */ public static boolean isLeapYear(int year) { return true; // replace this line with your solution } /** Returns the number of days in a given month. * @param month is a month, numbered in the range 1...12. * @param year is the year in question, with no digits omitted. * @return the number of days in the given month. */ public static int daysInMonth(int month, int year) { return 0; // replace this line with your solution } /** Checks whether the given date is valid. * @return true if and only if month/day/year constitute a valid date. */ public static boolean isValidDate(int month, int day, int year) { return true; // replace this line with your solution } /** Returns a string representation of a date in the form month/day/year. * The month, day, and year are printed in full as integers; for example,

* 12/7/1998 or 3/21/407. * @return a String representation of the date. */ public String toString() { return "stuff"; // replace this line with your solution } /** Determines whether this Date is before the Date d. * @return true if and only if this Date is before d. */ public boolean isBefore(Date d) { return true; // replace this line with your solution } /** Determines whether this Date is after the Date d. * @return true if and only if this Date is after d. */ public boolean isAfter(Date d) { return true; // replace this line with your solution } /** Returns the number of this Date in the year. * @return a number n in the range 1...366, inclusive, such that this Date * is the nth day of its year. (366 is only used for December 31 in a leap * year.) */ public int dayInYear() { return 0; // replace this line with your solution } /** Determines the difference in days between d and this Date. For example, * if this Date is 12/15/1997 and d is 12/14/1997, the difference is 1. * If this Date occurs before d, the result is negative. * @return the difference in days between d and this date. */ public int difference(Date d) { return 0; // replace this line with your solution } public static void main (String[] argv) { System.out.println("\nTesting constructors."); Date d1 = new Date(1, 1, 1); System.out.println("Date should be 1/1/1: " + d1); d1 = new Date("2/4/2"); System.out.println("Date should be 2/4/2: " + d1); d1 = new Date("2/29/2000"); System.out.println("Date should be 2/29/2000: " + d1); d1 = new Date("2/29/1904");

System.out.println("Date should be 2/29/1904: " + d1); d1 = new Date(12, 31, 1975); System.out.println("Date should be 12/31/1975: " + d1); Date d2 = new Date("1/1/1976"); System.out.println("Date should be 1/1/1976: " + d2); Date d3 = new Date("1/2/1976"); System.out.println("Date should be 1/2/1976: " + d3); Date d4 = new Date("2/27/1977"); Date d5 = new Date("8/31/2110"); /* I recommend you write code to test the isLeapYear function! */ System.out.println("\nTesting before and System.out.println(d2 + " after " + d1 + d2.isAfter(d1)); System.out.println(d3 + " after " + d2 + d3.isAfter(d2)); System.out.println(d1 + " after " + d1 + d1.isAfter(d1)); System.out.println(d1 + " after " + d2 + d1.isAfter(d2)); System.out.println(d2 + " after " + d3 + d2.isAfter(d3)); System.out.println(d1 + " before " + d1.isBefore(d2)); System.out.println(d2 + " before " + d2.isBefore(d3)); System.out.println(d1 + " before " + d1.isBefore(d1)); System.out.println(d2 + " before " + d2.isBefore(d1)); System.out.println(d3 + " before " + d3.isBefore(d2));

after."); " should be true: " + " should be true: " + " should be false: " + " should be false: " + " should be false: " +

d2 + " should be true: " + d3 + " should be true: " + d1 + " should be false: " + d1 + " should be false: " + d2 + " should be false: " +

System.out.println("\nTesting difference."); System.out.println(d1 + " - " + d1 + " should d1.difference(d1)); System.out.println(d2 + " - " + d1 + " should d2.difference(d1)); System.out.println(d3 + " - " + d1 + " should d3.difference(d1)); System.out.println(d3 + " - " + d4 + " should d3.difference(d4)); System.out.println(d5 + " - " + d4 + " should d5.difference(d4)); }

}

be 0: " + be 1: " + be 2: " + be -422: " + be 48762: " +

/* Date.java */ import java.io.*; class Date { /* Put your private data fields here. */ /** Constructs a date with the given month, day and year. If the date is * not valid, the entire program will halt with an error message. * @param month is a month, numbered in the range 1...12. * @param day is between 1 and the number of days in the given month. * @param year is the year in question, with no digits omitted. */ public Date(int month, int day, int year) { } /** Constructs a Date object corresponding to the given string. * @param s should be a string of the form "month/day/year" where month must * be one or two digits, day must be one or two digits, and year must be * between 1 and 4 digits. If s does not match these requirements or is not * a valid date, the program halts with an error message. */ public Date (String s) { } /** Checks whether the given year is a leap year. * @returns true if and only if the input year is a leap year. */ public static boolean isLeapYear(int year) { return true; // replace this line with your solution } /** Returns the number of days in a given month. * @param month is a month, numbered in the range 1...12. * @param year is the year in question, with no digits omitted. * @return the number of days in the given month. */ public static int daysInMonth(int month, int year) { return 0; // replace this line with your solution } /** Checks whether the given date is valid. * @return true if and only if month/day/year constitute a valid date.

*/ public static boolean isValidDate(int month, int day, int year) { return true; // replace this line with your solution } /** Returns a string representation of a date in the form month/day/year. * The month, day, and year are printed in full as integers; for example, * 12/7/1998 or 3/21/407. * @return a String representation of the date. */ public String toString() { return "stuff"; // replace this line with your solution } /** Determines whether this Date is before the Date d. * @return true if and only if this Date is before d. */ public boolean isBefore(Date d) { return true; // replace this line with your solution } /** Determines whether this Date is after the Date d. * @return true if and only if this Date is after d. */ public boolean isAfter(Date d) { return true; // replace this line with your solution } /** Returns the number of this Date in the year. * @return a number n in the range 1...366, inclusive, such that this Date * is the nth day of its year. (366 is only used for December 31 in a leap * year.) */ public int dayInYear() { return 0; // replace this line with your solution } /** Determines the difference in days between d and this Date. For example, * if this Date is 12/15/1997 and d is 12/14/1997, the difference is 1. * If this Date occurs before d, the result is negative. * @return the difference in days between d and this date. */ public int difference(Date d) { return 0; // replace this line with your solution }

public static void main (String[] argv) { System.out.println("\nTesting constructors."); Date d1 = new Date(1, 1, 1); System.out.println("Date should be 1/1/1: " + d1); d1 = new Date("2/4/2"); System.out.println("Date should be 2/4/2: " + d1); d1 = new Date("2/29/2000"); System.out.println("Date should be 2/29/2000: " + d1); d1 = new Date("2/29/1904"); System.out.println("Date should be 2/29/1904: " + d1); d1 = new Date(12, 31, 1975); System.out.println("Date should be 12/31/1975: " + d1); Date d2 = new Date("1/1/1976"); System.out.println("Date should be 1/1/1976: " + d2); Date d3 = new Date("1/2/1976"); System.out.println("Date should be 1/2/1976: " + d3); Date d4 = new Date("2/27/1977"); Date d5 = new Date("8/31/2110"); /* I recommend you write code to test the isLeapYear function! */ System.out.println("\nTesting before and System.out.println(d2 + " after " + d1 + d2.isAfter(d1)); System.out.println(d3 + " after " + d2 + d3.isAfter(d2)); System.out.println(d1 + " after " + d1 + d1.isAfter(d1)); System.out.println(d1 + " after " + d2 + d1.isAfter(d2)); System.out.println(d2 + " after " + d3 + d2.isAfter(d3)); System.out.println(d1 + " before " + d1.isBefore(d2)); System.out.println(d2 + " before " + d2.isBefore(d3)); System.out.println(d1 + " before " + d1.isBefore(d1)); System.out.println(d2 + " before " + d2.isBefore(d1)); System.out.println(d3 + " before " + d3.isBefore(d2));

after."); " should be true: " + " should be true: " + " should be false: " + " should be false: " + " should be false: " +

d2 + " should be true: " + d3 + " should be true: " + d1 + " should be false: " + d1 + " should be false: " + d2 + " should be false: " +

System.out.println("\nTesting difference."); System.out.println(d1 + " - " + d1 + " should d1.difference(d1)); System.out.println(d2 + " - " + d1 + " should d2.difference(d1)); System.out.println(d3 + " - " + d1 + " should d3.difference(d1)); System.out.println(d3 + " - " + d4 + " should d3.difference(d4)); System.out.println(d5 + " - " + d4 + " should

be 0: " + be 1: " + be 2: " + be -422: " + be 48762: " +

d5.difference(d4));

} }

/* SList.java */ /** * The SList class is a singly-linked implementation of the linked list * abstraction. SLists are mutable data structures, which can grow at either * end. * * @author Kathy Yelick and Jonathan Shewchuk **/ public class SList { private SListNode head; private int size; /** * SList() constructs an empty list. **/ public SList() { size = 0; head = null; } /** * isEmpty() indicates whether the list is empty. * @return true if the list is empty, false otherwise. **/ public boolean isEmpty() { return size == 0; } /** * length() returns the length of this list. * @return the length of this list. **/ public int length() { return size; } /** * insertFront() inserts item "obj" at the beginning of this list. * @param obj the item to be inserted. **/

public void insertFront(Object obj) { head = new SListNode(obj, head); size++; } /** * insertEnd() inserts item "obj" at the end of this list. * @param obj the item to be inserted. **/ public void insertEnd(Object obj) { if (head == null) { head = new SListNode(obj); } else { SListNode node = head; while (node.next != null) { node = node.next; } node.next = new SListNode(obj); } size++; } /** * nth() returns the item at the specified position. If position < 1 or * position > this.length(), null is returned. Otherwise, the item at * position "position" is returned. The list does not change. * @param position the desired position, from 1 to length(), in the list. * @return the item at the given position in the list. **/ public Object nth(int position) { SListNode currentNode; if ((position < 1) || (head == null)) { return null; } else { currentNode = head; while (position > 1) { currentNode = currentNode.next; if (currentNode == null) { return null; } position--; } return currentNode.item; } } /** * squish() takes this list and, wherever two or more consecutive items are * equal(), it removes duplicate nodes so that only one consecutive copy

* remains. Hence, no two consecutive items in this list are equal() upon * completion of the procedure. * * After squish() executes, the list may well be shorter than when squish() * began. No extra items are added to make up for those removed. * * For example, if the input list is [ 0 0 0 0 1 1 0 0 0 3 3 3 1 1 0 ], the * output list is [ 0 1 0 3 1 0 ]. * * Unlike with "smoosh()", "this" list is modified. * * IMPORTANT: Be sure you use the equals() method, and not the "==" * operator, to compare items. **/ public void squish() { // Fill in your solution here. }

(Ours is eleven lines long.)

/** * twin() takes this list and doubles its length by replacing each node * with two consecutive nodes referencing the same item. * * For example, if the input list is [ 3 7 4 2 2 ], the * output list is [ 3 3 7 7 4 4 2 2 2 2 ]. * * IMPORTANT: Do not try to make new copies of the items themselves. * Just copy the references to the items. **/ public void twin() { // Fill in your solution here. }

(Ours is seven lines long.)

/** * toString() converts the list to a String. * @return a String representation of the list. **/ public String toString() { int i; Object obj; String result = "[ "; SListNode cur = head; while (cur != null) { obj = cur.item; result = result + obj.toString() + " cur = cur.next; } result = result + "]"; return result;

";

} /** * main() runs test cases on the SList class. Prints summary * information on basic operations and halts with an error (and a stack * trace) if any of the tests fail. **/ public static void main (String[] args) { testEmpty(); testAfterInsertFront(); testAfterInsertEnd(); } /** * testEmpty() tests toString(), isEmpty(), length(), insertFront(), and * insertEnd() on an empty list. Prints summary information of the tests * and halts the program if errors are detected. **/ private static void testEmpty() { SList lst1 = new SList(); SList lst2 = new SList(); System.out.println(); System.out.println("Here is a list after construction: " + lst1.toString()); TestHelper.verify(lst1.toString().equals("[ ]"), "toString on newly constructed list failed"); System.out.println("isEmpty() should be true. It is: " + lst1.isEmpty()); TestHelper.verify(lst1.isEmpty() == true, "isEmpty() on newly constructed list failed"); System.out.println("length() should be 0. It is: " + lst1.length()); TestHelper.verify(lst1.length() == 0, "length on newly constructed list failed"); lst1.insertFront(new Integer(3)); System.out.println("Here is a list after insertFront(3) to an empty list: " + lst1.toString()); TestHelper.verify(lst1.toString().equals("[ 3 ]"), "InsertFront on empty list failed"); lst2.insertEnd(new Integer(5)); System.out.println("Here is a list after insertEnd(5) on an empty list: " + lst2.toString()); TestHelper.verify(lst2.toString().equals("[ 5 ]"), "insertEnd on empty list failed"); }

/** * testAfterInsertFront() tests toString(), isEmpty(), length(), * insertFront(), and insertEnd() after insertFront(). Prints summary * information of the tests and halts the program if errors are detected. **/ private static void testAfterInsertFront() { SList lst1 = new SList(); lst1.insertFront(new Integer(3)); lst1.insertFront(new Integer(2)); lst1.insertFront(new Integer(1)); System.out.println(); System.out.println("Here is a list after insertFront 3, 2, 1: " + lst1.toString()); TestHelper.verify(lst1.toString().equals("[ 1 2 3 ]"), "InsertFronts on non-empty list failed"); System.out.println("isEmpty() should be false. It is: " + lst1.isEmpty()); TestHelper.verify(lst1.isEmpty() == false, "isEmpty() after insertFront failed"); System.out.println("length() should be 3. It is: " + lst1.length()); TestHelper.verify(lst1.length() == 3, "length() after insertFront failed"); lst1.insertEnd(new Integer(4)); System.out.println("Here is the same list after insertEnd(4): " + lst1.toString()); TestHelper.verify(lst1.toString().equals("[ 1 2 3 4 ]"), "insertEnd on non-empty list failed"); } /** * testAfterInsertEnd() tests toString(), isEmpty(), length(), * insertFront(), and insertEnd() after insertEnd(). Prints summary * information of the tests and halts the program if errors are detected. **/ private static void testAfterInsertEnd() { SList lst1 = new SList(); lst1.insertEnd(new Integer(6)); lst1.insertEnd(new Integer(7)); System.out.println(); System.out.println("Here is a list after insertEnd 6, 7: " + lst1.toString()); System.out.println("isEmpty() should be false. It is: " + lst1.isEmpty()); TestHelper.verify(lst1.isEmpty() == false, "isEmpty() after insertEnd failed"); System.out.println("length() should be 2. It is: " + lst1.length()); TestHelper.verify(lst1.length() == 2, "length() after insertEndfailed"); lst1.insertFront(new Integer(5)); System.out.println("Here is the same list after insertFront(5): "

}

+ lst1.toString()); TestHelper.verify(lst1.toString().equals("[ 5 6 7 ]"), "insertFront after insertEnd failed");

}

/* SListNode.java */ /** * SListNode is a class used internally by the SList class. An SList object * is a singly-linked list, and an SListNode is a node of a singlylinked * list. Each SListNode has two references: one to an object, and one to * the next node in the list. * * @author Kathy Yelick and Jonathan Shewchuk */ class SListNode { Object item; SListNode next; /** * SListNode() (with one parameter) constructs a list node referencing the * item "obj". */ SListNode(Object obj) { item = obj; next = null; } /** * SListNode() (with two parameters) constructs a list node referencing the * item "obj", whose next list node is to be "next". */ SListNode(Object obj, SListNode next) { item = obj; this.next = next; } }

/* TestHelper.java */ /** * This class is based on code from Arnow and Weiss. Its verify() method * exits with an error message if an invariant fails to hold true. * * The purpose of this class is to provide a shorthand for writing and testing * invariants in any program. **/ public class TestHelper { /** * verify() checks an invariant and prints an error message if it fails. * If invariant is true, this method does nothing. If invariant is false, * the message is printed, followed by a dump of the program call stack. * @param invariant the condition to be verified * @param message the error message to be printed if the invariant fails to * hold true. **/ static void verify(boolean invariant, String message) { if (!invariant) { System.out.println("*** ERROR: " + message); Thread.dumpStack(); } } }

/* Ocean.java */ /** * The Ocean class defines an object that models an ocean full of sharks and * fish. Descriptions of the methods you must implement appear below. They * include a constructor of the form * * public Ocean(int i, int j, int starveTime); * * that creates an empty ocean having width i and height j, and the specified * shark starveTime. * * See the README file accompanying this project for additional details. */ public class Ocean { /* You may renumber these constants if you wish, but don't rename them. */ public final static int EMPTY = 0; public final static int SHARK = 1; public final static int FISH = 2; /** * Define any variables associated with an Ocean object here. * variables MUST be private. */

These

/** * The following methods are required for Part I. */ /** * Ocean() is a constructor that creates an empty ocean having width

i,

* height j, and the specified shark starveTime. */ public Ocean(int i, int j, int starveTime) { // Your solution here.

} /** * width() returns the width of an Ocean object. * @return the width of the ocean. */ public int width() { // Replace the following line with your solution. return 1; } /** * height() returns the height of an Ocean object. * @return the height of the ocean. */ public int height() { // Replace the following line with your solution. return 1; } /** * starveTime() returns the shark starveTime of an Ocean object. * @return the shark starveTime. */ public int starveTime() { // Replace the following line with your solution. return 1; } /** * the * * * */

addFish() places a fish in cell (x, y) if the cell is empty.

If

cell is already occupied, leave the cell as it is. @param x is the x-coordinate of the cell to place a fish in. @param y is the y-coordinate of the cell to place a fish in.

public void addFish(int x, int y) { // Your solution here. } /** * addShark() (with two parameters) places a newborn shark in cell (x, y) if * the cell is empty. A "newborn" shark is equivalent to a shark that has * just eaten. If the cell is already occupied, leave the cell as it is. * @param x is the x-coordinate of the cell to place a shark in. * @param y is the y-coordinate of the cell to place a shark in. */ public void addShark(int x, int y) { // Your solution here.

} /** * cellContents() returns EMPTY if cell (x, y) is empty, FISH if it contains * a fish, and SHARK if it contains a shark. * @param x is the x-coordinate of the cell whose contents are queried. * @param y is the y-coordinate of the cell whose contents are queried. */ public int cellContents(int x, int y) { // Replace the following line with your solution. return EMPTY; } /** * timeStep() performs a simulation timestep as described in README. * @return an ocean representing the elapse of one timestep. */ public Ocean timeStep() { // Replace the following line with your solution. return new Ocean(1, 1, 1); } /** * The following method is required for Part II. */ /** * addShark() (with three parameters) places a shark in cell (x, y) if the * cell is empty. The shark's hunger is represented by the third parameter. * If the cell is already occupied, leave the cell as it is. You will need * this method to help convert run-length encodings to Oceans. * @param x is the x-coordinate of the cell to place a shark in. * @param y is the y-coordinate of the cell to place a shark in. * @param feeding is an integer that indicates the shark's hunger. You may * encode it any way you want; for instance, "feeding" may be the * last timestep the shark was fed, or the amount of time that has * passed since the shark was last fed, or the amount of time left * before the shark will starve. It's up to you, but be consistent. */ public void addShark(int x, int y, int feeding) { // Your solution here. }

/** * The following method is required for Part III. */ /** * sharkFeeding() returns an integer that indicates the hunger of the shark * in cell (x, y), using the same "feeding" representation as the parameter * to addShark() described above. If cell (x, y) does not contain a shark, * then its return value is undefined--that is, anything you want. * Normally, this method should not be called if cell (x, y) does not * contain a shark. You will need this method to help convert Oceans to * run-length encodings. * @param x is the x-coordinate of the cell whose contents are queried. * @param y is the y-coordinate of the cell whose contents are queried. */ public int sharkFeeding(int x, int y) { // Replace the following line with your solution. return 0; } }

/* Ocean.java */ /** * The Ocean class defines an object that models an ocean full of sharks and * fish. Descriptions of the methods you must implement appear below. They * include a constructor of the form * * public Ocean(int i, int j, int starveTime); * * that creates an empty ocean having width i and height j, and the specified * shark starveTime. * * See the README file accompanying this project for additional details. */ public class Ocean {

/* You may renumber these constants if you wish, but don't rename them. */ public final static int EMPTY = 0; public final static int SHARK = 1; public final static int FISH = 2; /** * Define any variables associated with an Ocean object here. * variables MUST be private. */

These

/** * The following methods are required for Part I. */ /** * Ocean() is a constructor that creates an empty ocean having width i,

* height j, and the specified shark starveTime. */ public Ocean(int i, int j, int starveTime) { // Your solution here. } /** * width() returns the width of an Ocean object. * @return the width of the ocean. */ public int width() { // Replace the following line with your solution. return 1; } /** * height() returns the height of an Ocean object. * @return the height of the ocean. */ public int height() { // Replace the following line with your solution. return 1; } /** * starveTime() returns the shark starveTime of an Ocean object. * @return the shark starveTime. */ public int starveTime() { // Replace the following line with your solution. return 1; }

/** * the * * * */

addFish() places a fish in cell (x, y) if the cell is empty.

If

cell is already occupied, leave the cell as it is. @param x is the x-coordinate of the cell to place a fish in. @param y is the y-coordinate of the cell to place a fish in.

public void addFish(int x, int y) { // Your solution here. } /** * addShark() (with two parameters) places a newborn shark in cell (x, y) if * the cell is empty. A "newborn" shark is equivalent to a shark that has * just eaten. If the cell is already occupied, leave the cell as it is. * @param x is the x-coordinate of the cell to place a shark in. * @param y is the y-coordinate of the cell to place a shark in. */ public void addShark(int x, int y) { // Your solution here. } /** * cellContents() returns EMPTY if cell (x, y) is empty, FISH if it contains * a fish, and SHARK if it contains a shark. * @param x is the x-coordinate of the cell whose contents are queried. * @param y is the y-coordinate of the cell whose contents are queried. */ public int cellContents(int x, int y) { // Replace the following line with your solution. return EMPTY; } /** * timeStep() performs a simulation timestep as described in README. * @return an ocean representing the elapse of one timestep. */ public Ocean timeStep() { // Replace the following line with your solution. return new Ocean(1, 1, 1); } /** * The following method is required for Part II. */

/** * addShark() (with three parameters) places a shark in cell (x, y) if the * cell is empty. The shark's hunger is represented by the third parameter. * If the cell is already occupied, leave the cell as it is. You will need * this method to help convert run-length encodings to Oceans. * @param x is the x-coordinate of the cell to place a shark in. * @param y is the y-coordinate of the cell to place a shark in. * @param feeding is an integer that indicates the shark's hunger. You may * encode it any way you want; for instance, "feeding" may be the * last timestep the shark was fed, or the amount of time that has * passed since the shark was last fed, or the amount of time left * before the shark will starve. It's up to you, but be consistent. */ public void addShark(int x, int y, int feeding) { // Your solution here. } /** * The following method is required for Part III. */ /** * sharkFeeding() returns an integer that indicates the hunger of the shark * in cell (x, y), using the same "feeding" representation as the parameter * to addShark() described above. If cell (x, y) does not contain a shark, * then its return value is undefined--that is, anything you want. * Normally, this method should not be called if cell (x, y) does not * contain a shark. You will need this method to help convert Oceans to * run-length encodings. * @param x is the x-coordinate of the cell whose contents are queried. * @param y is the y-coordinate of the cell whose contents are queried. */ public int sharkFeeding(int x, int y) { // Replace the following line with your solution. return 0; } }

/* RunLengthEncoding.java */ /** * The RunLengthEncoding class defines an object that run-length encodes an * Ocean object. Descriptions of the methods you must implement appear below. * They include constructors of the form * * public RunLengthEncoding(int i, int j, int starveTime); * public RunLengthEncoding(int i, int j, int starveTime, * int[] runTypes, int[] runLengths) { * public RunLengthEncoding(Ocean ocean) { * * that create a run-length encoding of an Ocean having width i and height j, * and the specified shark starveTime. The first constructor creates a * run-length encoding of an Ocean in which every cell is empty. The second * constructor creates a run-length encoding for which the runs are provided * as parameters. The third constructor converts an Ocean object into a * run-length encoding of that object. * * See the README file accompanying this project for additional details. */ public class RunLengthEncoding { /** * Define any variables associated with a RunLengthEncoding object here. * These variables MUST be private. */

/** * The following methods are required for Part II. */ /** * RunLengthEncoding() (with three parameters) is a constructor that creates * a run-length encoding of an empty ocean having width i and height j, * and the specified starveTime. * @param i is the width of the ocean. * @param j is the height of the ocean. * @param starveTime is the number of timesteps for shark starvation. */ public RunLengthEncoding(int i, int j, int starveTime) { // Your solution here. } /** * RunLengthEncoding() (with five parameters) is a constructor that creates * a run-length encoding of an ocean having width i and height j, and the * specified starveTime. The runs of the run-length encoding are taken from * two input arrays. Run i has length runLengths[i] and species * runTypes[i]. * @param i is the width of the ocean. * @param j is the height of the ocean. * @param starveTime is the number of timesteps for shark starvation. * @param runTypes is an array that represents the species represented by * each run. Each element of runTypes is Ocean.EMPTY, Ocean.FISH, * or Ocean.SHARK. Any run of sharks is treated as a run of newborn * sharks (which are equivalent to sharks that have just eaten). * @param runLengths is an array that represents the length of each run. * The sum of all elements of the runLengths array should be i * j. */ public RunLengthEncoding(int i, int j, int starveTime, int[] runTypes, int[] runLengths) { // Your solution here. } /** * restartRuns() and nextRun() are two methods that work together to return * all the runs in the run-length encoding, one by one. Each time * nextRun() is invoked, it returns a different run (represented as a

* TypeAndSize object), until every run has been returned. The first time * nextRun() is invoked, it returns the first run in the encoding, which * contains cell (0, 0). After every run has been returned, nextRun() * returns null, which lets the calling program know that there are no more * runs in the encoding. * * The restartRuns() method resets the enumeration, so that nextRun() will * once again enumerate all the runs as if nextRun() were being invoked for * the first time. * * (Note: Don't worry about what might happen if nextRun() is interleaved * with addFish() or addShark(); it won't happen.) */ /** * restartRuns() resets the enumeration as described above, so that * nextRun() will enumerate all the runs from the beginning. */ public void restartRuns() { // Your solution here. } /** * nextRun() returns the next run in the enumeration, as described above. * If the runs have been exhausted, it returns null. The return value is * a TypeAndSize object, which is nothing more than a way to return two * integers at once. * @return the next run in the enumeration, represented by a TypeAndSize * object. */ public TypeAndSize nextRun() { // Replace the following line with your solution. return new TypeAndSize(Ocean.EMPTY, 1); } /** * toOcean() converts a run-length encoding of an ocean into an Ocean * object. You will need to implement the three-parameter addShark method * in the Ocean class for this method's use. * @return the Ocean represented by a run-length encoding. */ public Ocean toOcean() {

// Replace the following line with your solution. return new Ocean(1, 1); } /** * The following method is required for Part III. */ /** * RunLengthEncoding() (with one parameter) is a constructor that creates * a run-length encoding of an input Ocean. You will need to implement * the sharkFeeding method in the Ocean class for this constructor's use. * @param sea is the ocean to encode. */ public RunLengthEncoding(Ocean sea) { // Your solution here, but you should probably leave the following line // at the end. check(); } /** * The following methods are required for Part IV. */ /** * addFish() places a fish in cell (x, y) if the cell is empty. If the * cell is already occupied, leave the cell as it is. The final run-length * encoding should be compressed as much as possible; there should not be * two consecutive runs of sharks with the same degree of hunger. * @param x is the x-coordinate of the cell to place a fish in. * @param y is the y-coordinate of the cell to place a fish in. */ public void addFish(int x, int y) { // Your solution here, but you should probably leave the following line // at the end. check(); } /** * addShark() (with two parameters) places a newborn shark in cell (x, y) if * the cell is empty. A "newborn" shark is equivalent to a shark that has * just eaten. If the cell is already occupied, leave the cell as it is. * The final run-length encoding should be compressed as much as possible;

* there should not be two consecutive runs of sharks with the same degree * of hunger. * @param x is the x-coordinate of the cell to place a shark in. * @param y is the y-coordinate of the cell to place a shark in. */ public void addShark(int x, int y) { // Your solution here, but you should probably leave the following line // at the end. check(); } /** * check() walks through the run-length encoding and prints an error message * if two consecutive runs have the same contents, or if the sum of all run * lengths does not equal the number of cells in the ocean. */ public void check() { } }

/* SimText.java */ /* DO NOT CHANGE THIS FILE (except as noted). */ /* YOUR SUBMISSION MUST WORK CORRECTLY WITH _OUR_ COPY OF THIS FILE. */ /* (You may wish to make temporary changes or insert println() statements */ /* while testing your code. When you're finished testing and debugging, */ /* though, make sure your code works with the original version of this file. */ import java.util.*; /** * The SimText class is a program that runs and animates a simulation of * Sharks and Fish. *

* The SimText program takes up to four parameters. The first two specify * the width and height of the ocean. The third parameter specifies the value * of starveTime. For example, if you run * * java SimText 25 25 1 * * then SimText will animate a 25x25 ocean with a starveTime of 1. If you run * "java SimText" with no parameters, by default SimText will animate a 50x25 * ocean with a starveTime of 3. With some choices of parameters, the ocean * quickly dies out; with others, it teems forever. * * @author Jonathan Shewchuk */ public class SimText { /** * Default parameters. */

(You may change these if you wish.)

private static int i = 50; ocean width private static int j = 25; ocean height private static int starveTime = 3; starvation time

// Default // Default // Default shark

/** * paint() prints an Ocean. */ public static void paint(Ocean sea) { if (sea != null) { int width = sea.width(); int height = sea.height(); /* Draw the ocean. */ for (int x = 0; x < width + 2; x++) { System.out.print("-"); } System.out.println(); for (int y = 0; y < height; y++) { System.out.print("|"); for (int x = 0; x < width; x++) { int contents = sea.cellContents(x, y); if (contents == Ocean.SHARK) { System.out.print('S'); } else if (contents == Ocean.FISH) { System.out.print('~'); } else { System.out.print(' '); }

} System.out.println("|");

}

} for (int x = 0; x < width + 2; x++) { System.out.print("-"); } System.out.println();

} /** * main() reads the parameters and performs the simulation and animation. */ public static void main(String[] argv) throws InterruptedException { Ocean sea; /** * Read the input parameters. */ if (argv.length > 0) { try { i = Integer.parseInt(argv[0]); } catch (NumberFormatException e) { System.out.println("First argument to SimText is not an number."); } } if (argv.length > 1) { try { j = Integer.parseInt(argv[1]); } catch (NumberFormatException e) { System.out.println("Second argument to SimText is not an number."); } } if (argv.length > 2) { try { starveTime = Integer.parseInt(argv[2]); } catch (NumberFormatException e) { System.out.println("Third argument to SimText is not an number."); } } /** * Create the initial ocean. */ sea = new Ocean(i, j, starveTime);

/** * Visit each cell (in a roundabout order); randomly place a fish, shark, * or nothing in each. */ Random random = new Random(0); // Create a "Random" object with seed 0 int x = 0; int y = 0; for (int xx = 0; xx < i; xx++) { x = (x + 78887) % i; // This will visit every xcoordinate once if ((x < 25) || (x >= i - 25)) { for (int yy = 0; yy < j; yy++) { y = (y + 78887) % j; // This will visit every ycoordinate once if ((y < 25) || (y >= j - 25)) { int r = random.nextInt(); // Between -2147483648 and 2147483647 if (r < 0) { // 50% of cells start with fish sea.addFish(x, y); } else if (r > 1500000000) { // ~15% of cells start with sharks sea.addShark(x, y); } } } } } /** * Perform timesteps forever. */ while (true) { // Loop forever paint(sea); // For fun, you might wish to change the delay in the next line. Thread.sleep(1000); // Wait one second (1000 milliseconds) sea = sea.timeStep(); // Simulate a timestep } } }

/* Simulation.java */ /* DO NOT CHANGE THIS FILE (except as noted). */ /* YOUR SUBMISSION MUST WORK CORRECTLY WITH _OUR_ COPY OF THIS FILE. */ /* (You may wish to make temporary changes or insert println() statements */ /* while testing your code. When you're finished testing and debugging, */ /* though, make sure your code works with the original version of this file. */ import java.awt.*; import java.util.*; /** * The Simulation class is a program that runs and animates a simulation of * Sharks and Fish. * * The Simulation program takes up to four parameters. The first two specify * the width and height of the ocean. The third parameter specifies the value * of starveTime. For example, if you run * * java SimText 25 25 1 * * then Simulation will animate a 25x25 ocean with a starveTime of 1. If you * run "java SimText" with no parameters, by default Simulation will animate * a 50x25 ocean with a starveTime of 3. With some choices of parameters, * the ocean quickly dies out; with others, it teems forever. * * @author Jonathan Shewchuk */ public class Simulation { /** * The constant cellSize determines the size of each cell on the screen * during animation. (You may change this if you wish.) */ private static final int cellSize = 4; /** * Default parameters. */

(You may change these if you wish.)

private static int i = 50; ocean width private static int j = 25; ocean height private static int starveTime = 3; starvation time

// Default // Default // Default shark

private static void drawOcean(Graphics graphics, Ocean ocean) { if (ocean != null) { int width = ocean.width(); int height = ocean.height(); for (int y = 0; y < height; y++) { for (int x = 0; x < width; x++) { int contents = ocean.cellContents(x, y); if (contents == Ocean.SHARK) { graphics.setColor(Color.red); // Draw a red shark graphics.fillRect(x * cellSize, y * cellSize, cellSize, cellSize); } else if (contents == Ocean.FISH) { graphics.setColor(Color.green); // Draw a green fish graphics.fillRect(x * cellSize, y * cellSize, cellSize, cellSize); } else { graphics.clearRect(x * cellSize, y * cellSize, cellSize, cellSize); } } } } } /** * main() reads the parameters and performs the simulation and animation. */ public static void main(String[] argv) throws InterruptedException { Ocean sea; /** * Read the input parameters. /* DList.java */ package list; /** * * * * * */

A DList is a mutable doubly-linked list ADT. Its implementation is circularly-linked and employs a sentinel (dummy) node at the head of the list. DO NOT CHANGE ANY METHOD PROTOTYPES IN THIS FILE.

public class DList { /** * head references the sentinel node. * size is the number of items in the list. (The sentinel node does not * store an item.) * * DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS. */ protected DListNode head; protected int size; /* DList invariants: * 1) head != null. * 2) For any DListNode x in a DList, x.next != null and x.prev != null. * 3) For any DListNode x in a DList, if x.next == y, then y.prev == x. * 4) For any DListNode x in a DList, if x.prev == y, then y.next == x. * 5) The "size" field is the number of DListNodes, excepting the sentinel, * that can be accessed from the sentinel by a sequence of "next" * references. */ /** * newNode() calls the DListNode constructor. Use this class to allocate * new DListNodes rather than calling the DListNode constructor directly. * That way, only this method need be overridden if a subclass of DList * wants to use a different kind of node. * @param item the item to store in the node. * @param prev the node previous to this node. * @param next the node following this node. */ public DListNode newNode(Object item, DListNode prev, DListNode next) { return new DListNode(item, prev, next); } /** * DList() constructor for an empty DList. */ public DList() { // Your solution here. } /** * isEmpty() returns true if this DList is empty, false otherwise. * @return true if this DList is empty, false otherwise. * Performance: runs in O(1) time.

*/ public boolean isEmpty() { return size == 0; } /** * length() returns the length of this DList. * @return the length of this DList. * Performance: runs in O(1) time. */ public int length() { return size; } /** * insertFront() inserts an item at the front of this DList. * @param item is the item to be inserted. * Performance: runs in O(1) time. */ public void insertFront(Object item) { // Your solution here. } /** * insertBack() inserts an item at the back of this DList. * @param item is the item to be inserted. * Performance: runs in O(1) time. */ public void insertBack(Object item) { // Your solution here. } /** * front() returns the node at the front of this DList. DList is * empty, return null. * * Do NOT return the sentinel under any circumstances! * * @return the node at the front of this DList. * Performance: runs in O(1) time. */ public DListNode front() { // Your solution here. } /** * back() returns the node at the back of this DList. is

* empty, return null. * * Do NOT return the sentinel under any circumstances! * * @return the node at the back of this DList. * Performance: runs in O(1) time. */ public DListNode back() {

If the

If the DList

}

// Your solution here.

/** * next() returns the node following "node" in this DList. If "node" is * null, or "node" is the last node in this DList, return null. * * Do NOT return the sentinel under any circumstances! * * @param node the node whose successor is sought. * @return the node following "node". * Performance: runs in O(1) time. */ public DListNode next(DListNode node) { // Your solution here. } /** * prev() returns the node prior to "node" in this DList.

If "node"

is

* null, or "node" is the first node in this DList, return null. * * Do NOT return the sentinel under any circumstances! * * @param node the node whose predecessor is sought. * @return the node prior to "node". * Performance: runs in O(1) time. */ public DListNode prev(DListNode node) { // Your solution here. }

/** * insertAfter() inserts an item in this DList immediately following "node". * If "node" is null, do nothing. * @param item the item to be inserted. * @param node the node to insert the item after. * Performance: runs in O(1) time. */ public void insertAfter(Object item, DListNode node) { // Your solution here. } /** * insertBefore() inserts an item in this DList immediately before "node". * If "node" is null, do nothing. * @param item the item to be inserted. * @param node the node to insert the item before. * Performance: runs in O(1) time. */ public void insertBefore(Object item, DListNode node) { // Your solution here. }

/** * remove() removes "node" from this DList. nothing. * Performance: runs in O(1) time. */ public void remove(DListNode node) { // Your solution here. }

If "node" is null, do

/** * toString() returns a String representation of this DList. * * DO NOT CHANGE THIS METHOD. * * @return a String representation of this DList. * Performance: runs in O(n) time, where n is the length of the list. */ public String toString() { String result = "[ "; DListNode current = head.next; while (current != head) { result = result + current.item + " "; current = current.next; } return result + "]"; } public static void main(String[] args) { // You may put test code here. It will not be graded. // But if you don't test your code, it's not likely to pass our tests. } }

/* DListNode.java */ package list;

/** * A DListNode is a node in a DList (doubly-linked list). */ public class DListNode { /** * * * * * */

item references the item stored in the current node. prev references the previous node in the DList. next references the next node in the DList. DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS.

public Object item; protected DListNode prev; protected DListNode next; /** * DListNode() constructor. * @param i the item to store in the node. * @param p the node previous to this node. * @param n the node following this node. */ DListNode(Object i, DListNode p, DListNode n) { item = i; prev = p; next = n; } }

/* Set.java */ import list.*; /** * A Set is a collection of Comparable elements stored in sorted order. * Duplicate elements are not permitted in a Set. **/ public class Set { /* Fill in the data fields here. */ /** * Set invariants: * 1) The Set's elements must be precisely the elements of the List. * 2) The List must always contain Comparable elements, and those elements * must always be sorted in ascending order. * 3) No two elements in the List may be equals(). **/

/** * Constructs an empty Set. * * Performance: runs in O(1) time. **/ public Set() { // Your solution here. } /** * cardinality() returns the number of elements in this Set. * * Performance: runs in O(1) time. **/ public int cardinality() { // Replace the following line with your solution. return 0; } /** * insert() inserts a Comparable element into this Set. * * Sets are maintained in sorted order. The ordering is specified by the * compareTo() method of the java.lang.Comparable interface. * * Performance: runs in O(this.cardinality()) time. **/ public void insert(Comparable c) { // Your solution here. } /** * union() modifies this Set so that it contains all the elements it * started with, plus all the elements of s. The Set s is NOT modified. * Make sure that duplicate elements are not created. * * Performance: Must run in O(this.cardinality() + s.cardinality()) time. * * Your implementation should NOT copy elements of s or "this", though it * will copy references to the elements of s. Your implementation will * create new nodes for the elements of s that are added to "this", but you * should reuse the nodes that are alread part of "this". * * DO NOT MODIFY THE SET s. * DO NOT ATTEMPT TO COPY ELEMENTS; just copy references to them. **/ public void union(Set s) { // Your solution here. } /**

* intersect() modifies this Set so that it contains the intersection of * its own elements and the elements of s. The Set s is NOT modified. * * Performance: Must run in O(this.cardinality() + s.cardinality()) time. * * Do not construct any new ListNodes during the execution of intersect. * Reuse the nodes of "this" that will be in the intersection result. * * DO NOT MODIFY THE SET s. * DO NOT CONSTRUCT ANY NEW NODES. * DO NOT ATTEMPT TO COPY ELEMENTS. **/ public void intersect(Set s) { // Your solution here. } /** * toString() returns a String representation of this Set. The String must * have the following format: * { } for an empty Set. No spaces before "{" or after "}"; two spaces * between them. * { 1 2 3 } for a Set of three Integer elements. No spaces before * "{" or after "}"; two spaces before and after each element. * Elements are printed with their own toString method, whatever * that may be. The elements must appear in sorted order, from * lowest to highest according to the compareTo() method. * * WARNING: THE AUTOGRADER EXPECTS YOU TO PRINT SETS IN _EXACTLY_ THIS * FORMAT, RIGHT UP TO THE TWO SPACES BETWEEN ELEMENTS. ANY * DEVIATIONS WILL LOSE POINTS. **/ public String toString() { // Replace the following line with your solution. return ""; } public static void main(String[] argv) { Set s = new Set(); s.insert(new Integer(3)); s.insert(new Integer(4)); s.insert(new Integer(3)); System.out.println("Set s = " + s); Set s2 = new Set(); s2.insert(new Integer(4));

s2.insert(new Integer(5)); s2.insert(new Integer(5)); System.out.println("Set s2 = " + s2); Set s3 = new Set(); s3.insert(new Integer(5)); s3.insert(new Integer(3)); s3.insert(new Integer(8)); System.out.println("Set s3 = " + s3); s.union(s2); System.out.println("After s.union(s2), s = " + s); s.intersect(s3); System.out.println("After s.intersect(s3), s = " + s); System.out.println("s.cardinality() = " + s.cardinality()); // You may want to add more (ungraded) test code here. }

}

/* DList.java */ package list; /** * A DList is a mutable doubly-linked list ADT. Its implementation is * circularly-linked and employs a sentinel (dummy) node at the head of the * list. * * DO NOT CHANGE ANY METHOD PROTOTYPES IN THIS FILE. **/ public class DList extends List { /** * (inherited) size is the number of items in the list. * head references the sentinel node. * Note that the sentinel node does not store an item, and is not included * in the count stored by the "size" field. * * DO NOT CHANGE THE FOLLOWING FIELD DECLARATION. **/ protected DListNode head; /* DList invariants: * 1) head != null. * 2) For any DListNode x in a DList, x.next != null and x.prev != null. * 3) For any DListNode x in a DList, if x.next == y, then y.prev == x.

* 4) == x. * 5) sentinel, * * **/

For any DListNode x in a DList, if x.prev == y, then y.next The "size" field is the number of DListNodes, excepting the that can be accessed from the sentinel by a sequence of "next" references.

/** * newNode() calls the DListNode constructor. Use this method to allocate * new DListNodes rather than calling the DListNode constructor directly. * That way, only this method need be overridden if a subclass of DList * wants to use a different kind of node. * * @param item the item to store in the node. * @param prev the node previous to this node. * @param next the node following this node. **/ protected DListNode newNode(Object item, DListNode prev, DListNode next) { return new DListNode(item, this, prev, next); } /** * DList() constructs for an empty DList. **/ public DList() { // Your solution (from Homework 4) here. } /** * insertFront() inserts an item at the front of this DList. * * @param item is the item to be inserted. * * Performance: runs in O(1) time. **/ public void insertFront(Object item) { // Your solution (from Homework 4) here. } /** * insertBack() inserts an item at the back of this DList. * * @param item is the item to be inserted. * * Performance: runs in O(1) time. **/ public void insertBack(Object item) { // Your solution (from Homework 4) here. } /**

* front() returns the node at the front of this DList. If the DList is * empty, return an "invalid" node--a node with the property that any * attempt to use it will cause an exception. (The sentinel is "invalid".) * * DO NOT CHANGE THIS METHOD. * * @return a ListNode at the front of this DList. * * Performance: runs in O(1) time. */ public ListNode front() { return head.next; } /** * back() returns the node at the back of this DList.

If the DList

is

* empty, return an "invalid" node--a node with the property that any * attempt to use it will cause an exception. (The sentinel is "invalid".) * * DO NOT CHANGE THIS METHOD. * * @return a ListNode at the back of this DList. * * Performance: runs in O(1) time. */ public ListNode back() { return head.prev; } /** * toString() returns a String representation of this DList. * * DO NOT CHANGE THIS METHOD. * * @return a String representation of this DList. * * Performance: runs in O(n) time, where n is the length of the list. */ public String toString() { String result = "[ "; DListNode current = head.next; while (current != head) { result = result + current.item + " "; current = current.next; } return result + "]"; } private static void testInvalidNode(ListNode p) { System.out.println("p.isValidNode() should be false: " + p.isValidNode()); try {

p.item(); System.out.println("p.item() should throw an exception, but didn't."); } catch (InvalidNodeException lbe) { System.out.println("p.item() should throw an exception, and did."); } try { p.setItem(new Integer(0)); System.out.println("p.setItem() should throw an exception, but didn't."); } catch (InvalidNodeException lbe) { System.out.println("p.setItem() should throw an exception, and did."); } try { p.next(); System.out.println("p.next() should throw an exception, but didn't."); } catch (InvalidNodeException lbe) { System.out.println("p.next() should throw an exception, and did."); } try { p.prev(); System.out.println("p.prev() should throw an exception, but didn't."); } catch (InvalidNodeException lbe) { System.out.println("p.prev() should throw an exception, and did."); } try { p.insertBefore(new Integer(1)); System.out.println("p.insertBefore() should throw an exception, but " + "didn't."); } catch (InvalidNodeException lbe) { System.out.println("p.insertBefore() should throw an exception, and did." ); } try { p.insertAfter(new Integer(1)); System.out.println("p.insertAfter() should throw an exception, but " + "didn't."); } catch (InvalidNodeException lbe) { System.out.println("p.insertAfter() should throw an exception, and did." ); } try { p.remove(); System.out.println("p.remove() should throw an exception, but didn't."); } catch (InvalidNodeException lbe) {

System.out.println("p.remove() should throw an exception, and did."); } } private static void testEmpty() { List l = new DList(); System.out.println("An empty list should be [ ]: " + l); System.out.println("l.isEmpty() should be true: " + l.isEmpty()); System.out.println("l.length() should be 0: " + l.length()); System.out.println("Finding front node p of l."); ListNode p = l.front(); testInvalidNode(p); System.out.println("Finding back node p of l."); p = l.back(); testInvalidNode(p); l.insertFront(new Integer(10)); System.out.println("l after insertFront(10) should be [ 10 ]: " + l); } public static void main(String[] argv) { testEmpty(); List l = new DList(); l.insertFront(new Integer(3)); l.insertFront(new Integer(2)); l.insertFront(new Integer(1)); System.out.println("l is a list of 3 elements: " + l); try { ListNode n; int i = 1; for (n = l.front(); n.isValidNode(); n = n.next()) { System.out.println("n.item() should be " + i + ": " + n.setItem(new Integer(((Integer) n.item()).intValue() System.out.println("n.item() should be " + 2 * i + ": n.item()); i++; } System.out.println("After doubling all elements of l: " testInvalidNode(n);

n.item()); * 2)); " +

+ l);

i = 6; for (n = l.back(); n.isValidNode(); n = n.prev()) { System.out.println("n.item() should be " + i + ": " + n.item()); n.setItem(new Integer(((Integer) n.item()).intValue() * 2)); System.out.println("n.item() should be " + 2 * i + ": " + n.item()); i = i - 2; } System.out.println("After doubling all elements of l again: " + l); testInvalidNode(n); n = l.front().next(); System.out.println("Removing middle element (8) of l: " + n.item()); n.remove();

System.out.println("l is now: " + l); testInvalidNode(n); n = l.back(); System.out.println("Removing end element (12) of l: " + n.item()); n.remove(); System.out.println("l is now: " + l); testInvalidNode(n); n = l.front(); System.out.println("Removing first element (4) of l: " + n.item()); n.remove(); System.out.println("l is now: " + l); testInvalidNode(n); } catch (InvalidNodeException lbe) { System.err.println ("Caught InvalidNodeException that should not happen." ); System.err.println ("Aborting the testing code."); } } } /* DListNode.java */ package list; /** * A DListNode is a mutable node in a DList (doubly-linked list). **/ public class DListNode extends ListNode { /** * (inherited) item references the item stored in the current node. * (inherited) myList references the List that contains this node. * prev references the previous node in the DList. * next references the next node in the DList. * * DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS. **/ protected DListNode prev; protected DListNode next; /** * DListNode() constructor. * @param i the item to store in the node. * @param l the list this node is in. * @param p the node previous to this node. * @param n the node following this node. */ DListNode(Object i, DList l, DListNode p, DListNode n) { item = i; myList = l; prev = p;

}

next = n;

/** * isValidNode returns true if this node is valid; false otherwise. * For convenience, an invalid node may be represented in one of two ways: * as a node that doesn't belong to a list (myList is null), or as the * sentinel node of its DList. * * @return true if this node is valid; false otherwise. * * Performance: runs in O(1) time. */ public boolean isValidNode() { return (myList != null) && (((DList) myList).head != this); } /** * next() returns the node following this node. If this node is invalid, * throws an exception. * * @return the node following this node. * @exception InvalidNodeException if this node is not valid. * * Performance: runs in O(1) time. */ public ListNode next() throws InvalidNodeException { if (!isValidNode()) { throw new InvalidNodeException("next() called on invalid node"); } return next; } /** * prev() returns the node preceding this node. If this node is invalid, * throws an exception. * * @param node the node whose predecessor is sought. * @return the node preceding this node. * @exception InvalidNodeException if this node is not valid. * * Performance: runs in O(1) time. */ public ListNode prev() throws InvalidNodeException { if (!isValidNode()) { throw new InvalidNodeException("prev() called on invalid node"); } return prev; } /** * insertAfter() inserts an item immediately following this node. If this

* node is invalid, throws an exception. * * @param item the item to be inserted. * @exception InvalidNodeException if this node is not valid. * * Performance: runs in O(1) time. */ public void insertAfter(Object item) throws InvalidNodeException { if (!isValidNode()) { throw new InvalidNodeException("insertAfter() called on invalid node"); } // Your solution here. Will look something like your Homework 4 solution, // but changes are necessary. For instance, there is no need to check if // "this" is null. Remember that this node's "myList" fields tells you // what DList it's in. You should use myList.newNode() to create the // new node. } /** * insertBefore() inserts an item immediately preceding this node. If this * node is invalid, throws an exception. * * @param item the item to be inserted. * @exception InvalidNodeException if this node is not valid. * * Performance: runs in O(1) time. */ public void insertBefore(Object item) throws InvalidNodeException { if (!isValidNode()) { throw new InvalidNodeException("insertBefore() called on invalid node"); } // Your solution here. Will look something like your Homework 4 solution, // but changes are necessary. For instance, there is no need to check if // "this" is null. Remember that this node's "myList" fields tells you // what DList it's in. You should use myList.newNode() to create the // new node. } /** * remove() removes this node from its DList. If this node is invalid, * throws an exception. * * @exception InvalidNodeException if this node is not valid. * * Performance: runs in O(1) time.

*/ public void remove() throws InvalidNodeException { if (!isValidNode()) { throw new InvalidNodeException("remove() called on invalid node"); } // Your solution here. Will look something like your Homework 4 solution, // but changes are necessary. For instance, there is no need to check if // "this" is null. Remember that this node's "myList" fields tells you // what DList it's in.

// Make this node an invalid node, so it cannot be used to corrupt myList. myList = null; // Set other references to null to improve garbage collection. next = null; prev = null; } }

/* InvalidNodeException.java */ package list; /** * Implements an Exception that signals an attempt to use an invalid ListNode. */ public class InvalidNodeException extends Exception { protected InvalidNodeException() { super(); }

}

protected InvalidNodeException(String s) { super(s); }

/* List.java */

package list; /** * A List is a mutable list ADT. * * DO NOT CHANGE THIS FILE. **/

No implementation is provided.

public abstract class List { /** * size is the number of items in the list. **/ protected int size; /** * isEmpty() returns true if this List is empty, false otherwise. * * @return true if this List is empty, false otherwise. * * Performance: runs in O(1) time. **/ public boolean isEmpty() { return size == 0; } /** * length() returns the length of this List. * * @return the length of this List. * * Performance: runs in O(1) time. **/ public int length() { return size; } /** * insertFront() inserts an item at the front of this List. * * @param item is the item to be inserted. **/ public abstract void insertFront(Object item); /** * insertBack() inserts an item at the back of this List. * * @param item is the item to be inserted. **/ public abstract void insertBack(Object item); /** * front() returns the node at the front of this List. is

* *

If the List

empty, return an "invalid" node--a node with the property that any attempt to use it will cause an exception.

* * @return a ListNode at the front of this List. */ public abstract ListNode front(); /** * back() returns the node at the back of this List. If the List is * empty, return an "invalid" node--a node with the property that any * attempt to use it will cause an exception. * * @return a ListNode at the back of this List. */ public abstract ListNode back(); /** * toString() returns a String representation of this List. * * @return a String representation of this List. */ public abstract String toString(); }

/* ListNode.java */ package list; /** * A ListNode is a mutable node in a list. provided. * * DO NOT CHANGE THIS FILE. **/

No implementation is

public abstract class ListNode { /** * item references the item stored in the current node. * myList references the List that contains this node. * * DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS. */ protected Object item; protected List myList; /** * isValidNode returns true if this node is valid; false otherwise. * By default, an invalid node is one that doesn't belong to a list (myList * is null), but subclasses can override this definition. *

* @return true if this node is valid; false otherwise. * * Performance: runs in O(1) time. */ public boolean isValidNode() { return myList != null; } /** * item() returns this node's item. If this node is invalid, * throws an exception. * * @return the item stored in this node. * * Performance: runs in O(1) time. */ public Object item() throws InvalidNodeException { if (!isValidNode()) { throw new InvalidNodeException(); } return item; } /** * setItem() sets this node's item to "item". If this node is invalid, * throws an exception. * * Performance: runs in O(1) time. */ public void setItem(Object item) throws InvalidNodeException { if (!isValidNode()) { throw new InvalidNodeException(); } this.item = item; } /** * next() returns the node following this node. If this node is invalid, * throws an exception. * * @return the node following this node. * @exception InvalidNodeException if this node is not valid. */ public abstract ListNode next() throws InvalidNodeException; /** * prev() returns the node preceding this node. If this node is invalid, * throws an exception. * * @param node the node whose predecessor is sought. * @return the node preceding this node. * @exception InvalidNodeException if this node is not valid. */ public abstract ListNode prev() throws InvalidNodeException;

/** * insertAfter() inserts an item immediately following this node. If this * node is invalid, throws an exception. * * @param item the item to be inserted. * @exception InvalidNodeException if this node is not valid. */ public abstract void insertAfter(Object item) throws InvalidNodeException; /** * insertBefore() inserts an item immediately preceding this node. If this * node is invalid, throws an exception. * * @param item the item to be inserted. * @exception InvalidNodeException if this node is not valid. */ public abstract void insertBefore(Object item) throws InvalidNodeException; /** * remove() removes this node from its List. If this node is invalid, * throws an exception. * * @exception InvalidNodeException if this node is not valid. */ public abstract void remove() throws InvalidNodeException; } /* SList.java */ package list; /** * A SList is a mutable singly-linked list ADT. employs * a tail reference. * * DO NOT CHANGE THIS FILE. **/

Its implementation

public class SList extends List { /** * (inherited) size is the number of items in the list. * head references the first node. * tail references the last node. **/ protected SListNode head; protected SListNode tail; /* SList invariants:

* 1) Either head == null and tail == null, or tail.next == null and the * SListNode referenced by tail can be reached from the head by a * sequence of zero or more "next" references. This implies that the * list is not circularly linked. * 2) The "size" field is the number of SListNodes that can be accessed * from head (including head itself) by a sequence of "next" references. **/ /** * newNode() calls the SListNode constructor. Use this method to allocate * new SListNodes rather than calling the SListNode constructor directly. * That way, only this method need be overridden if a subclass of SList * wants to use a different kind of node. * * @param item the item to store in the node. * @param next the node following this node. **/ protected SListNode newNode(Object item, SListNode next) { return new SListNode(item, this, next); } /** * SList() constructs for an empty SList. **/ public SList() { head = null; tail = null; size = 0; } /** * insertFront() inserts an item at the front of this SList. * * @param item is the item to be inserted. * * Performance: runs in O(1) time. **/ public void insertFront(Object item) { head = newNode(item, head); if (size == 0) { tail = head; } size++; } /** * insertBack() inserts an item at the back of this SList. * * @param item is the item to be inserted. *

* Performance: runs in O(1) time. **/ public void insertBack(Object item) { if (head == null) { head = newNode(item, null); tail = head; } else { tail.next = newNode(item, null); tail = tail.next; } size++; } /** * front() returns the node at the front of this SList. If the SList is * empty, return an "invalid" node--a node with the property that any * attempt to use it will cause an exception. * * @return a ListNode at the front of this SList. * * Performance: runs in O(1) time. */ public ListNode front() { if (head == null) { // Create an invalid node. SListNode node = newNode(null, null); node.myList = null; return node; } else { return head; } } /** * back() returns the node at the back of this SList.

If the SList

is

* empty, return an "invalid" node--a node with the property that any * attempt to use it will cause an exception. * * @return a ListNode at the back of this SList. * * Performance: runs in O(1) time. */ public ListNode back() { if (tail == null) { // Create an invalid node. SListNode node = newNode(null, null); node.myList = null; return node; } else { return tail; } } /** * toString() returns a String representation of this SList.

* * @return a String representation of this SList. * * Performance: runs in O(n) time, where n is the length of the list. */ public String toString() { String result = "[ "; SListNode current = head; while (current != null) { result = result + current.item + " "; current = current.next; } return result + "]"; } private static void testInvalidNode(ListNode p) { System.out.println("p.isValidNode() should be false: " + p.isValidNode()); try { p.item(); System.out.println("p.item() should throw an exception, but didn't."); } catch (InvalidNodeException lbe) { System.out.println("p.item() should throw an exception, and did."); } try { p.setItem(new Integer(0)); System.out.println("p.setItem() should throw an exception, but didn't."); } catch (InvalidNodeException lbe) { System.out.println("p.setItem() should throw an exception, and did."); } try { p.next(); System.out.println("p.next() should throw an exception, but didn't."); } catch (InvalidNodeException lbe) { System.out.println("p.next() should throw an exception, and did."); } try { p.prev(); System.out.println("p.prev() should throw an exception, but didn't."); } catch (InvalidNodeException lbe) { System.out.println("p.prev() should throw an exception, and did."); } try { p.insertBefore(new Integer(1)); System.out.println("p.insertBefore() should throw an exception, but " + "didn't."); } catch (InvalidNodeException lbe) {

System.out.println("p.insertBefore() should throw an exception, and did." ); } try { p.insertAfter(new Integer(1)); System.out.println("p.insertAfter() should throw an exception, but " + "didn't."); } catch (InvalidNodeException lbe) { System.out.println("p.insertAfter() should throw an exception, and did." ); } try { p.remove(); System.out.println("p.remove() should throw an exception, but didn't."); } catch (InvalidNodeException lbe) { System.out.println("p.remove() should throw an exception, and did."); } } private static void testEmpty() { List l = new SList(); System.out.println("An empty list should be [ ]: " + l); System.out.println("l.isEmpty() should be true: " + l.isEmpty()); System.out.println("l.length() should be 0: " + l.length()); System.out.println("Finding front node p of l."); ListNode p = l.front(); testInvalidNode(p); System.out.println("Finding back node p of l."); p = l.back(); testInvalidNode(p); l.insertFront(new Integer(10)); System.out.println("l after insertFront(10) should be [ 10 ]: " + l); } public static void main(String[] argv) { testEmpty(); List l = new SList(); l.insertFront(new Integer(3)); l.insertFront(new Integer(2)); l.insertFront(new Integer(1)); System.out.println("l is a list of 3 elements: " + l); try { ListNode n; int i = 1; for (n = l.front(); n.isValidNode(); n = n.next()) { System.out.println("n.item() should be " + i + ": " + n.item()); n.setItem(new Integer(((Integer) n.item()).intValue() * 2)); System.out.println("n.item() should be " + 2 * i + ": " + n.item()); i++; }

System.out.println("After doubling all elements of l: " + l); testInvalidNode(n); i = 6; for (n = l.back(); n.isValidNode(); n = n.prev()) { System.out.println("n.item() should be " + i + ": " + n.item()); n.setItem(new Integer(((Integer) n.item()).intValue() * 2)); System.out.println("n.item() should be " + 2 * i + ": " + n.item()); i = i - 2; } System.out.println("After doubling all elements of l again: " + l); testInvalidNode(n); n = l.front().next(); System.out.println("Removing middle element (8) of l: " + n.item()); n.remove(); System.out.println("l is now: " + l); testInvalidNode(n); n = l.back(); System.out.println("Removing end element (12) of l: " + n.item()); n.remove(); System.out.println("l is now: " + l); testInvalidNode(n); n = l.front(); System.out.println("Removing first element (4) of l: " + n.item()); n.remove(); System.out.println("l is now: " + l); testInvalidNode(n); } catch (InvalidNodeException lbe) { System.err.println ("Caught InvalidNodeException that should not happen." ); System.err.println ("Aborting the testing code."); } } }

/* SListNode.java */ package list; /** * An SListNode is a mutable node in an SList (singly-linked list). **/ public class SListNode extends ListNode { /** * (inherited)

item references the item stored in the current node.

* (inherited) myList references the List that contains this node. * next references the next node in the SList. * * DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS. **/ protected SListNode next; /** * SListNode() constructor. * @param i the item to store in the node. * @param l the list this node is in. * @param n the node following this node. */ SListNode(Object i, SList l, SListNode n) { item = i; myList = l; next = n; } /** * next() returns the node following this node. If this node is invalid, * throws an exception. * * @return the node following this node. * @exception InvalidNodeException if this node is not valid. * * Performance: runs in O(1) time. */ public ListNode next() throws InvalidNodeException { if (!isValidNode()) { throw new InvalidNodeException("next() called on invalid node"); } if (next == null) { // Create an invalid node. SListNode node = ((SList) myList).newNode(null, null); node.myList = null; return node; } else { return next; } } /** * prev() returns the node preceding this node. If this node is invalid, * throws an exception. * * @param node the node whose predecessor is sought. * @return the node preceding this node. * @exception InvalidNodeException if this node is not valid. * * Performance: runs in O(this.size) time. */ public ListNode prev() throws InvalidNodeException { if (!isValidNode()) {

}

throw new InvalidNodeException("prev() called on invalid node"); } SListNode prev = ((SList) myList).head; if (prev == this) { // Create an invalid node. prev = ((SList) myList).newNode(null, null); prev.myList = null; } else { while (prev.next != this) { prev = prev.next; } } return prev;

/** * insertAfter() inserts an item immediately following this node. If this * node is invalid, throws an exception. * * @param item the item to be inserted. * @exception InvalidNodeException if this node is not valid. * * Performance: runs in O(1) time. */ public void insertAfter(Object item) throws InvalidNodeException { if (!isValidNode()) { throw new InvalidNodeException("insertAfter() called on invalid node"); } SListNode newNode = ((SList) myList).newNode(item, next); if (next == null) { ((SList) myList).tail = newNode; } next = newNode; myList.size++; } /** * insertBefore() inserts an item immediately preceding this node. If this * node is invalid, throws an exception. * * @param item the item to be inserted. * @exception InvalidNodeException if this node is not valid. * * Performance: runs in O(this.size) time. */ public void insertBefore(Object item) throws InvalidNodeException { if (!isValidNode()) { throw new InvalidNodeException("insertBefore() called on invalid node"); } SListNode newNode = ((SList) myList).newNode(item, this); if (this == ((SList) myList).head) { ((SList) myList).head = newNode; } else {

SListNode prev = (SListNode) prev(); prev.next = newNode; } myList.size++; } /** * remove() removes this node from its SList. If this node is invalid, * throws an exception. * * @exception InvalidNodeException if this node is not valid. * * Performance: runs in O(this.size) time. */ public void remove() throws InvalidNodeException { if (!isValidNode()) { throw new InvalidNodeException("remove() called on invalid node"); } if (this == ((SList) myList).head) { ((SList) myList).head = next; if (next == null) { ((SList) myList).tail = null; } } else { SListNode prev = (SListNode) prev(); prev.next = next; if (next == null) { ((SList) myList).tail = prev; } } myList.size--; // Make this node an invalid node, so it cannot be used to corrupt myList. myList = null; // Set other reference to null to improve garbage collection. next = null; } }

/* Homework6Test.java */ import dict.*; /** * Initializes a hash table, then stocks it with random SimpleBoards. * @author Daniel C. Silverstein **/

public class Homework6Test { /** * Generates a random 8 x 8 SimpleBoard. **/ private static SimpleBoard randomBoard() { SimpleBoard board = new SimpleBoard(); for (int y = 0; y < 8; y++) { for (int x = 0; x < 8; x++) { double fval = Math.random() * 12; int value = (int) fval; board.setElementAt(x, y, value); } } return board; } /** * Empties the given table, then inserts the given number of boards * into the table. * @param table is the hash table to be initialized. * @param numBoards is the number of random boards to place in the table. **/ public static void initTable(HashTableChained table, int numBoards) { table.makeEmpty(); for (int i = 0; i < numBoards; i++) { table.insertItem(randomBoard(), new Integer(i)); } } public static void main(String[] args) { int numBoards; if (args.length == 0) { numBoards = 100; } else { numBoards = Integer.parseInt(args[0]); } HashTableChained table = new HashTableChained(numBoards); initTable(table, numBoards); // To test your hash function, add a method to your HashTableChained class // that counts the number of collisions. Call this method from here. } }

/* SimpleBoard.java */ /**

* Simple class that implements an 8x8 game board with three possible values * for each cell: 0, 1 or 2. * * DO NOT CHANGE ANY PROTOTYPES IN THIS FILE. **/ public class SimpleBoard { private final static int DIMENSION = 8; private int[][] grid; /** * Invariants: * (1) grid.length == DIMENSION. * (2) for all 0 <= i < DIMENSION, grid[i].length == DIMENSION. * (3) for all 0 <= i, j < DIMENSION, grid[i][j] >= 0 and grid[i][j] <= 2. **/ /** * Construct a new board in which all cells are empty. */ public SimpleBoard() { grid = new int[DIMENSION][DIMENSION]; } /** * Set the cell (x, y) in the board to the given value % 3. * @param value to which the element should be set (normally 0, 1, or 2). * @param x is the x-index. * @param y is the y-index. * @exception ArrayIndexOutOfBoundsException is thrown if an invalid index * is given. **/ public void setElementAt(int x, int y, int value) { grid[x][y] = value % 3; } /** * Get the valued stored in cell (x, y). * @param x is the x-index. * @param y is the y-index. * @return the stored value (between 0 and 2). * @exception ArrayIndexOutOfBoundsException is thrown if an invalid index * is given. */ public int elementAt(int x, int y) { return grid[x][y]; } /** * * * *

Returns true if two boards have identical values in each cell. @param board is the second SimpleBoard. @return true if the boards are equal, false otherwise. @exception ClassCastException if board is not a SimpleBoard.

*/ public boolean equals(Object board) { // Replace the following line with your solution. return false; } /** * Returns a hash code for this SimpleBoard. * @return a number between Integer.MIN_VALUE and Integer.MAX_VALUE. */ public int hashCode() { // Replace the following line with your solution. return 99; } }

/* Dictionary.java */ package dict; /** * An interface for (unordered) dictionary ADTs. * * DO NOT CHANGE THIS FILE. **/ public interface Dictionary { /** * Special element returned by the search and remove methods when * no item with the specified key is stored in the dictionary. **/ public static final Object NO_SUCH_KEY = new String("Dictionary.NO_SUCH_KEY"); /** * Returns the number of items stored in the dictionary, where each item * is counted according to its multiplicity. * @return number of items in the dictionary. **/ public int size(); /** * Tests if the dictionary is empty. * * @return true if the dictionary has no items, false otherwise. **/ public boolean isEmpty(); /** * Insert an item (a key and an associated element). with * the same key can coexist in the dictionary.

Multiple items

* * @param key the key by which the item can be retrieved. * @param element an arbitrary object. **/ public void insertItem(Object key, Object element); /** * Search for an item with the specified key. If such an item is found, * return its element; otherwise return the special element NO_SUCH_KEY. * If several items have the specified key, one is chosen arbitrarily and * returned. * * @param key the search key. * @return element an element associated with the key, or NO_SUCH_KEY if no * item is associated with the specified key. **/ public Object findElement(Object key); /** * Remove an item with the specified key. If such an item is found, return * its element and remove it from the table; otherwise else return the * special element NO_SUCH_KEY. If several items have the specified key, * one is chosen arbitrarily, removed, and returned. * * @param key the search key. * @return element an element associated with the key, or NO_SUCH_KEY if no * item is associated with the specified key. */ public Object remove(Object key); /** * Remove all items from the dictionary. */ public void makeEmpty(); } /* HashTableChained.java */ package dict; /** * HashTableChained implements a Dictionary as a hash table with chaining. * All objects used as keys must have a valid hashCode() method, which is * used to determine which bucket of the hash table an item is stored in.

* Each object's hashCode() is presumed to return an int between * Integer.MIN_VLAUE and Integer.MAX_VALUE; the code herein hashes the hash * code to select a bucket within the table's range. * * DO NOT CHANGE ANY PROTOTYPES IN THIS FILE. **/ public class HashTableChained implements Dictionary { /** * Place any data fields here. **/ /** * Construct a new hash table intended to hold roughly sizeEstimate items. * (The precise number of buckets is up to you, but we recommend you use * a prime number, and shoot for a load factor between 0.5 and 1.) **/ public HashTableChained(int sizeEstimate) { // Your solution here. } /** * Construct a new hash table with a default size. **/ public HashTableChained() { // Your solution here. } /** * Converts a hash code in the range Integer.MIN_VALUE...Integer.MAX_VALUE * to a value in the range 0...size of hash table - 1. * * This function should have package protection (so we can test it), and * should be used by insertItem, findElement, and remove. **/ int hashFunction(int code) { // Replace the following line with your solution. return 88; } /** * Returns the number of items stored in the dictionary, where each item * is counted according to its multiplicity. * @return number of items in the dictionary. **/ public int size() { // Replace the following line with your solution. return 0; } /** * Tests if the dictionary is empty.

* * @return true if the dictionary has no items, false otherwise. **/ public boolean isEmpty() { // Replace the following line with your solution. return true; } /** * Insert an item (a key and an associated element). Multiple items with * the same key can coexist in the dictionary. * * @param key the key by which the item can be retrieved. * @param element an arbitrary object. **/ public void insertItem(Object key, Object element) { // Your solution here. } /** * Search for an item with the specified key. If such an item is found, * return its element; otherwise return the special element NO_SUCH_KEY. * If several items have the specified key, one is chosen arbitrarily and * returned. * * @param key the search key. * @return element an element associated with the key, or NO_SUCH_KEY if no * item is associated with the specified key. **/ public Object findElement(Object key) { // Replace the following line with your solution. return null; } /** * Remove an item with the specified key. If such an item is found, return * its element and remove it from the table; otherwise else return the * special element NO_SUCH_KEY. If several items have the specified key, * one is chosen arbitrarily, removed, and returned. * * @param key the search key. * @return element an element associated with the key, or NO_SUCH_KEY if no * item is associated with the specified key. */ public Object remove(Object key) { // Replace the following line with your solution. return null; }

/** * Remove all items from the dictionary. */ public void makeEmpty() { // Your solution here. } }

player

/* MachinePlayer.java */ package player; /** * An implementation of an automatic Network player. Keeps track of moves * made by both players. Can select a move for itself. */ public class MachinePlayer extends Player {

// Creates a machine player with the given color. (black) // or 1 (white).

Color is either 0

public MachinePlayer(int color) { } // Creates a machine player with the given color and search depth. Color is // either 0 (black) or 1 (white). public MachinePlayer(int color, int searchDepth) { } // Returns a new move by this player. a move // by this player. public Move chooseMove() { return new Move(); }

Internally records the move as

// If the Move m is legal, records the move as a move by the opponent and // returns true. If the move is illegal, returns false without modifying // the internal state of this player. This method allows your opponents to // inform you of their moves. public boolean opponentMove(Move m) { return false; } // If the Move m is legal, records the move as a move by this player and // returns true. If the move is illegal, returns false without modifying // the internal state of this player. This method is used to help set up // "Network problems" for your player to solve. public boolean forceMove(Move m) { return false; } }

/* Move.java

*/

package player;

/** * A public class for holding all the fields in a move. This class is a * container for data, not an ADT; hence, all fields are public. * * The moveKind field stores the type of move. The x-coordinates index the * horizontal direction (left to right) and the y-coordinates index the * vertical direction (top to bottom). x- and y-coordinates start at zero. * * DO NOT CHANGE THIS FILE. */ public class Move { public final static int QUIT = 0; public final static int ADD = 1; public final static int STEP = 2; public int moveKind;

// ADD, STEP, or QUIT.

public public public public

// If moveKind == ADD, then x1, y1 are the new // position in which a chip is being added; // x2, y2 are unused. // If moveKind == STEP, then x1, y1 are the new // position, and x2, y2 are the old position // of the chip. // If moveKind == QUIT, then x1, x2, y1, y2 are

unused.

int int int int

x1; y1; x2; y2;

// Construct a step move. public Move(int xx1, int yy1, int xx2, int yy2) { moveKind = STEP; x1 = xx1; x2 = xx2; y1 = yy1; y2 = yy2; } // Construct an add move. public Move(int x, int y) { moveKind = ADD; x1 = x; y1 = y; } // Construct a quit move. public Move() { moveKind = QUIT; } // toString() converts the move to a String. public String toString() { switch (moveKind) { case QUIT: return "[quit]";

}

case ADD: return "[add to " + x1 + "" + y1 + "]"; default: return "[step from " + x2 + "" + y2 + " to " + x1 + "" + y1 + "]"; }

}

/* Player.java */ package player; /** * A class that is extended by all Network players (human and machine). * * DO NOT CHANGE THIS FILE. */ public abstract class Player { // This player's name as recognized by the game Network. public String myName; // Returns a new move by this player. a move // by this player. public abstract Move chooseMove();

Internally records the move as

// If the Move m is legal, records the move as a move by the opponent and // returns true. If the move is illegal, returns false without modifying // the internal state of this player. This method allows your opponents to // inform you of their moves. public abstract boolean opponentMove(Move m); // If the Move m is legal, records the move as a move by this player and // returns true. If the move is illegal, returns false without modifying // the internal state of this player. This method is used to help set up // "Network problems" for your player to solve. public abstract boolean forceMove(Move m); }

/* IntDictionary.java */ package dict; /** * An IntDictionary is a mutable ordered dictionary ADT. Each item is an int * key; there are no additional objects associated with the key. * * DO NOT CHANGE THIS FILE. * * @author Jonathan Shewchuk */ public abstract class IntDictionary { /** * size is the number of items in the dictionary. **/ protected int size; /** * isEmpty() returns true if this IntDictionary is empty, false otherwise. * * @return true if this IntDictionary is empty, false otherwise. * * Performance: runs in O(1) time. **/ public boolean isEmpty() { return size == 0; } /** * size() returns the size of this IntDictionary. * * @return the size of this IntDictionary. * * Performance: runs in O(1) time. **/ public int size() { return size; } }

/* Tree234.java */ package dict; /** * A Tree234 implements an ordered integer dictionary ADT using a 2-34 tree. * Only int keys are stored; no object is associated with each key. Duplicate * keys are not stored in the tree. * * @author Jonathan Shewchuk **/ public class Tree234 extends IntDictionary { /** * (inherited) size is the number of keys in the dictionary. * root is the root of the 2-3-4 tree. * * You may add fields if you wish, but don't change anything that * would prevent toString or findKey from working correctly. **/ Tree234Node root; public Tree234() { root = null; size = 0; } /** * toString() prints this Tree234 as a String. Each node is printed * in the form such as (for a 3-key node) * * (child1)key1(child2)key2(child3)key3(child4) * * where each child is a recursive call to toString, and null children * are printed as a space with no parentheses. Here's an example. * ((1)7(11 16)22(23)28(37 49))50((60)84(86 95 100)) * * DO NOT CHANGE THIS METHOD. * * @return a String representation of the 2-3-4 tree. **/ public String toString() { if (root == null) { return "";

}

} else { return root.toString(); }

/** * findKey() prints true if "key" is in this 2-3-4 tree; false otherwise. * * @param key is the key sought. * @return true if "key" is in the tree; false otherwise. **/ public boolean findKey(int key) { Tree234Node node = root; while (node != null) { if (key < node.key1) { node = node.child1; } else if (key == node.key1) { return true; } else if ((node.keys == 1) || (key < node.key2)) { node = node.child2; } else if (key == node.key2) { return true; } else if ((node.keys == 2) || (key < node.key3)) { node = node.child3; } else if (key == node.key3) { return true; } else { node = node.child4; } } return false; } /** * insertKey() inserts the key "key" into this 2-3-4 tree.

If "key"

is

* already present, a duplicate copy is NOT inserted. * * @param key is the key sought. **/ public void insertKey(int key) { // Fill in your solution here. } /** * testHelper() prints the String representation of this tree, then * compares it with the expected String, and prints an error message

if

* the two are not equal. * * @param correctString is what the tree should look like. **/ public void testHelper(String correctString) { String treeString = toString(); System.out.println(treeString); if (!treeString.equals(correctString)) {

}

System.out.println("ERROR:

Should be " + correctString);

} /** * main() is your own; * this code **/ public static Tree234 t =

a bunch of test code.

Feel free to add test code of

won't be tested or graded. void main(String[] args) { new Tree234();

System.out.println("\nInserting 84."); t.insertKey(84); t.testHelper("84"); System.out.println("\nInserting 7."); t.insertKey(7); t.testHelper("7 84"); System.out.println("\nInserting 22."); t.insertKey(22); t.testHelper("7 22 84"); System.out.println("\nInserting 95."); t.insertKey(95); t.testHelper("(7)22(84 95)"); System.out.println("\nInserting 50."); t.insertKey(50); t.testHelper("(7)22(50 84 95)"); System.out.println("\nInserting 11."); t.insertKey(11); t.testHelper("(7 11)22(50 84 95)"); System.out.println("\nInserting 37."); t.insertKey(37); t.testHelper("(7 11)22(37 50)84(95)"); System.out.println("\nInserting 60."); t.insertKey(60); t.testHelper("(7 11)22(37 50 60)84(95)"); System.out.println("\nInserting 1."); t.insertKey(1); t.testHelper("(1 7 11)22(37 50 60)84(95)"); System.out.println("\nInserting 23."); t.insertKey(23); t.testHelper("(1 7 11)22(23 37)50(60)84(95)"); System.out.println("\nInserting 16."); t.insertKey(16); t.testHelper("((1)7(11 16)22(23 37))50((60)84(95))"); System.out.println("\nInserting 100.");

t.insertKey(100); t.testHelper("((1)7(11 16)22(23 37))50((60)84(95 100))"); System.out.println("\nInserting 28."); t.insertKey(28); t.testHelper("((1)7(11 16)22(23 28 37))50((60)84(95 100))"); System.out.println("\nInserting 86."); t.insertKey(86); t.testHelper("((1)7(11 16)22(23 28 37))50((60)84(86 95 100))"); System.out.println("\nInserting 49."); t.insertKey(49); t.testHelper("((1)7(11 16)22(23)28(37 49))50((60)84(86 95 100))"); System.out.println("\nInserting 81."); t.insertKey(81); t.testHelper("((1)7(11 16)22(23)28(37 49))50((60 81)84(86 95 100))"); System.out.println("\nInserting 51."); t.insertKey(51); t.testHelper("((1)7(11 16)22(23)28(37 49))50((51 60 81)84(86 95 100))"); System.out.println("\nInserting 99."); t.insertKey(99); t.testHelper("((1)7(11 16)22(23)28(37 49))50((51 60 81)84(86)95(99 100))"); System.out.println("\nInserting 75."); t.insertKey(75); t.testHelper("((1)7(11 16)22(23)28(37 49))50((51)60(75 81)84(86)95"

+

"(99 100))"); System.out.println("\nInserting 66."); t.insertKey(66); t.testHelper("((1)7(11 16)22(23)28(37 49))50((51)60(66 75 81))84((86)95" + "(99 100))"); System.out.println("\nInserting 4."); t.insertKey(4); t.testHelper("((1 4)7(11 16))22((23)28(37 49))50((51)60(66 75 81))84" + "((86)95(99 100))"); System.out.println("\nInserting 80."); t.insertKey(80); t.testHelper("(((1 4)7(11 16))22((23)28(37 49)))50(((51)60(66)75" + "(80 81))84((86)95(99 100)))"); } } /* Tree234Node.java */

package dict; /** * A Tree234Node is a node in a 2-3-4 tree (Tree234 class). * * DO NOT CHANGE ANYTHING IN THIS FILE. * You may add helper methods and additional constructors, though. **/ class Tree234Node { /** * keys is the number of keys in this node. Always 1, 2, or 3. * key1 through key3 are the keys of this node. If keys == 1, the value * of key2 doesn't matter. If keys < 3, the value of key3 doesn't matter. * parent is this node's parent; null if this is the root. * child1 through child4 are the children of this node. If this is a leaf * node, they must all be set to null. If this node has no third and/or * fourth child, child3 and/or child4 must be set to null. **/ int keys; int key1; int key2; int key3; Tree234Node parent; Tree234Node child1; Tree234Node child2; Tree234Node child3; Tree234Node child4; Tree234Node(Tree234Node p, int key) { keys = 1; key1 = key; parent = p; child1 = null; child2 = null; child3 = null; child4 = null; } /** * toString() recursively prints this Tree234Node and its descendants as * a String. Each node is printed in the form such as (for a 3-key node) * * (child1)key1(child2)key2(child3)key3(child4) * * where each child is a recursive call to toString, and null children * are printed as a space with no parentheses. Here's an example. * ((1)7(11 16)22(23)28(37 49))50((60)84(86 95 100)) * * DO NOT CHANGE THIS METHOD.

**/ public String toString() { String s = ""; if (child1 != null) { s = "(" + child1.toString() + ")"; } s = s + key1; if (child2 != null) { s = s + "(" + child2.toString() + ")"; } else if (keys > 1) { s = s + " "; } if (keys > 1) { s = s + key2; if (child3 != null) { s = s + "(" + child3.toString() + ")"; } else if (keys > 2) { s = s + " "; } } if (keys > 2) { s = s + key3; if (child4 != null) { s = s + "(" + child4.toString() + ")"; } } return s; } }

/* Timer.java */ /** * Implements a simple stopwatch/timer class based on wall-clock time. **/ /** * RUNNING() == true <==> start() called with no corresponding * call to stop() * * All times are given in units of msec. **/ public class Timer { private boolean running; private long tStart;

private long tFinish; private long tAccum; /** * Initializes Timer to 0 msec **/ public Timer() { reset(); } /** * Starts the timer. Accumulates time across multiple calls to start. **/ public void start() { running = true; tStart = System.currentTimeMillis(); tFinish = tStart; } /** * Stops the timer. returns the time elapsed since the last matching call * to start(), or zero if no such matching call was made. **/ public long stop() { tFinish = System.currentTimeMillis(); if (running) { running = false; long diff = tFinish - tStart; tAccum += diff; return diff;

}

} return 0;

/** * if RUNNING() ==> returns the time since last call to start() * if !RUNNING() ==> returns total elapsed time **/ public long elapsed() { if (running) { return System.currentTimeMillis() - tStart; } }

return tAccum;

/** * Stops timing, if currently RUNNING(); resets * accumulated time to 0. */ public void reset() { running = false; tStart = 0; tFinish = 0;

}

tAccum = 0;

} /* ListSorts.java */ import list.*; public class ListSorts { private final static int SORTSIZE = 1000; /** * makeQueueOfQueues() makes a queue of queues, each containing one element * of q. Upon completion of this method, q is empty. * @param q is a LinkedQueue of objects. * @return a LinkedQueue containing LinkedQueue objects, each of which * contains one object from q. **/ public static LinkedQueue makeQueueOfQueues(LinkedQueue q) { // Replace the following line with your solution. return null; } /** * mergeSortedQueues() merges two sorted queues into a third. On completion * of this method, q1 and q2 are empty, and their elements have been merged * into the returned queue. * @param q1 is LinkedQueue of Comparable objects, sorted from smallest * to largest. * @param q2 is LinkedQueue of Comparable objects, sorted from smallest * to largest. * @return a LinkedQueue containing all the Comparable objects from q1 * and q2 (and nothing else), sorted from smallest to largest. **/ public static LinkedQueue mergeSortedQueues(LinkedQueue q1, LinkedQueue q2) { // Replace the following line with your solution. return null; } /** * circularShift performs a circular shift consituting shiftAmount dequeues * and enqueues. For example, if q is [ 3 9 6 2 ] and shiftAmount is 2, * q becomes [ 6 2 3 9 ]. If q is empty, it is not changed. * @param q is a LinkedQueue. * @param shiftAmount is an int representing the number of shifts to be

* performed. **/ public static void circularShift(LinkedQueue q, int shiftAmount) { // Your solution here. } /** * partition() partitions qIn using the pivot element. On completion of * this method, qIn is empty, and its elements have been moved to qSmall, * qEquals, and qLarge, according to their relationship to the pivot. * @param qIn is a LinkedQueue of Comparable objects. * @param pivot is a Comparable element used for partitioning. * @param qSmall is a LinkedQueue, in which all elements less than pivot * will be enqueued. * @param qEquals is a LinkedQueue, in which all elements equal to the pivot * will be enqueued. * @param qLarge is a LinkedQueue, in which all elements greater than pivot * will be enqueued. **/ public static void partition(LinkedQueue qIn, Comparable pivot, LinkedQueue qSmall, LinkedQueue qEquals, LinkedQueue qLarge) { // Your solution here. } /** * mergeSort() sorts q from smallest to largest using merge sort. * @param q is a LinkedQueue of Comparable objects. **/ public static void mergeSort(LinkedQueue q) { // Your solution here. } /** * quickSort() sorts q from smallest to largest using quicksort. * @param q is a LinkedQueue of Comparable objects. **/ public static void quickSort(LinkedQueue q) { // Your solution here. } /** * makeRandom() builds a LinkedQueue of the indicated size containing * Integer elements. The elements are randomly chosen between 0 and size. * @param size is the size of the resulting LinkedQueue. **/ public static LinkedQueue makeRandom(int size) { LinkedQueue q = new LinkedQueue(); for (int i = 0; i < size; i++) { q.enqueue(new Integer((int) (size * Math.random()))); }

}

return q;

/** * printQueue() prints the queue q on the standard output. * @param q is a LinkedQueue. q's elements are printed using their toString * method. **/ public static void printQueue(LinkedQueue q) { System.out.print("[ "); try { for (int i = 0; i < q.size(); i++) { System.out.print(q.front() + " "); q.enqueue(q.dequeue()); } } catch (QueueEmptyException uf) { System.err.println("Error: attempt to dequeue from empty queue."); } System.out.println("]"); } /** * main() performs some tests on merge sort and quicksort. Feel free to add * more tests of your own to make sure your algorithms works on boundary * cases. Your test code will not be graded. **/ public static void main(String [] args) { LinkedQueue q = makeRandom(10); printQueue(q); mergeSort(q); printQueue(q); q = makeRandom(10); printQueue(q); quickSort(q); printQueue(q); /* Remove these comments for Part III. Timer stopWatch = new Timer(); q = makeRandom(SORTSIZE); stopWatch.start(); mergeSort(q); stopWatch.stop(); System.out.println("Merge sort time, " + SORTSIZE + " Integers: stopWatch.elapsed() + " msec."); stopWatch.reset(); q = makeRandom(SORTSIZE); stopWatch.start(); quickSort(q); stopWatch.stop(); System.out.println("Quick sort time, " + SORTSIZE + " Integers:

" +

" +

*/

stopWatch.elapsed() + " msec.");

} }

/* LinkedQueue.java */ package list; public class LinkedQueue implements Queue { private SListNode head; private SListNode tail; private int size; /** * LinkedQueue() constructs an empty queue. **/ public LinkedQueue() { size = 0; head = null; tail = null; } /** * size() returns the size of this Queue. * @return the size of this Queue. * Performance: runs in O(1) time. **/ public int size() { return size; } /** * isEmpty() returns true if this Queue is empty, false otherwise. * @return true if this Queue is empty, false otherwise. * Performance: runs in O(1) time. **/ public boolean isEmpty() { return size == 0; } /** * enqueue() inserts an object at the end of the Queue. * @param element the element to be enqueued. **/ public void enqueue(Object element) { if (head == null) { head = new SListNode(element); tail = head; } else { tail.next = new SListNode(element);

}

tail = tail.next; } size++;

/** * dequeue() removes and returns the object at the front of the Queue. * @return the element dequeued. * @throws a QueueEmptyException if the Queue is empty. **/ public Object dequeue() throws QueueEmptyException { if (head == null) { throw new QueueEmptyException(); } else { Object o = head.item; head = head.next; size--; if (size == 0) { tail = null; } return o; } } /** * dequeue() returns the object at the front of the Queue. * @return the element at the front of the Queue. * @throws a QueueEmptyException if the Queue is empty. **/ public Object front() throws QueueEmptyException { if (head == null) { throw new QueueEmptyException(); } else { return head.item; } } /** * append() appends the contents of q onto the end of this LinkedQueue. * On completion, q is empty. * @param q the LinkedQueue whose contents should be appended onto this * LinkedQueue. **/ public void append(LinkedQueue q) { if (head == null) { head = q.head; } else { tail.next = q.head; } if (q.head != null) { tail = q.tail; } size = size + q.size; q.head = null;

q.tail = null; q.size = 0; } }

/* Queue.java */ package list; public interface Queue { /** * size() returns the size of this Queue. * @return the size of this Queue. * Performance: runs in O(1) time. **/ public int size(); /** * isEmpty() returns true if this Queue is empty, false otherwise. * @return true if this Queue is empty, false otherwise. * Performance: runs in O(1) time. **/ public boolean isEmpty(); /** * enqueue() inserts an object at the end of the Queue. * @param element the element to be enqueued. **/ public void enqueue(Object element); /** * dequeue() removes and returns the object at the front of the Queue. * @return the element dequeued. * @throws a QueueEmptyException if the Queue is empty. **/ public Object dequeue() throws QueueEmptyException; /** * dequeue() returns the object at the front of the Queue. * @return the element at the front of the Queue. * @throws a QueueEmptyException if the Queue is empty. **/ public Object front() throws QueueEmptyException; }

/* QueueEmptyException.java */ package list; public class QueueEmptyException extends Exception { public QueueEmptyException() { super(); } public QueueEmptyException(String s) { super(s); } }

/* SListNode.java */ package list; /** * SListNode is a class used internally by the SList class. object

An SList

* is a singly-linked list, and an SListNode is a node of a singlylinked * list. Each SListNode has two references: one to an object, and one to * the next node in the list. * * @author Kathy Yelick and Jonathan Shewchuk */ class SListNode { Object item; SListNode next; /** * SListNode() (with one parameter) constructs a list node referencing the * item "obj". */ SListNode(Object obj) { item = obj; next = null; } /** * SListNode() (with two parameters) constructs a list node referencing the * item "obj", whose next list node is to be "next". */ SListNode(Object obj, SListNode next) { item = obj; this.next = next; } }

/* Maze.java */ import java.util.*; import set.*; /**

* The Maze class represents a maze in a rectangular grid. exactly * one path between any two points. **/

There is

public class Maze { // Horizontal and vertical dimensions of the maze. protected int horiz; protected int vert; // Horizontal and vertical interior walls; each is true if the wall exists. protected boolean[][] hWalls; protected boolean[][] vWalls; // Object for generting random numbers. private static Random random; // Constants used in the // maze). private static final private static final private static final private static final private static final

depth-first search (which checks for cycles in int int int int int

STARTHERE = 0; FROMLEFT = 1; FROMRIGHT = 2; FROMABOVE = 3; FROMBELOW = 4;

/** * Maze() creates a rectangular maze having "horizontalSize" cells in the * horizontal direction, and "verticalSize" cells in the vertical direction. * There is a path between any two cells of the maze. A disjoint set data * structure is used to ensure that there is only one path between any two * cells. **/ public Maze(int horizontalSize, int verticalSize) { int i, j; horiz = horizontalSize; vert = verticalSize; if ((horiz < 1) || (vert < 1) || ((horiz == 1) && (vert == 1))) { return; // There are no interior walls } // // // if

Create all of the horizontal interior walls. Initially, every horizontal wall exists; they will be removed later by the maze generation algorithm. (vert > 1) { hWalls = new boolean[horiz][vert - 1]; for (j = 0; j < vert - 1; j++) { for (i = 0; i < horiz; i++) { hWalls[i][j] = true; }

} } // Create all of the vertical interior walls. if (horiz > 1) { vWalls = new boolean[horiz - 1][vert]; for (i = 0; i < horiz - 1; i++) { for (j = 0; j < vert; j++) { vWalls[i][j] = true; } } }

/** * Fill in the rest of this method. You should go through all the walls of * the maze in random order, and remove any wall whose removal will not * create a cycle. Use the implementation of disjoint sets provided in the * set package to avoid creating any cycles. * * Note the method randInt() further below, which generates a random * integer. randInt() generates different numbers every time the program * is run, so that you can make lots of different mazes. **/

} /** * toString() returns a string representation of the maze. **/ public String toString() { int i, j; String s = ""; // Print the top exterior wall. for (i = 0; i < horiz; i++) { s = s + "**"; } s = s + "*\n*"; // Print the maze interior. for (j = 0; j < vert; j++) { // Print a row of cells and vertical walls. for (i = 0; i < horiz - 1; i++) { if (vWalls[i][j]) { s = s + " *"; } else { s = s + " "; } } s = s + " *\n*";

}

if (j < vert - 1) { // Print a row of horizontal walls and wall corners. for (i = 0; i < horiz; i++) { if (hWalls[i][j]) { s = s + "**"; } else { s = s + " *"; } } s = s + "\n*"; }

// Print the bottom exterior wall. has

(Note that the first asterisk

// already been printed.) for (i = 0; i < horiz; i++) { s = s + "**"; } return s + "\n";

} /** * horizontalWall() determines whether the horizontal wall on the bottom * edge of cell (x, y) exists. If the coordinates (x, y) do not correspond * to an interior wall, true is returned. **/ public boolean horizontalWall(int x, int y) { if ((x < 0) || (y < 0) || (x > horiz - 1) || (y > vert - 2)) { return true; } return hWalls[x][y]; } /** * verticalWall() determines whether the vertical wall on the right edge of * cell (x, y) exists. If the coordinates (x, y) do not correspond to an * interior wall, true is returned. **/ public boolean verticalWall(int x, int y) { if ((x < 0) || (y < 0) || (x > horiz - 2) || (y > vert - 1)) { return true; } return vWalls[x][y]; } /** * randInt() returns a random integer from 0 to choices - 1. **/ private static int randInt(int choices) { if (random == null) { // Only executed first time randInt() is called

random = new Random(); // Create a "Random" object with random seed } int r = random.nextInt() % choices; // From 1 - choices to choices - 1 if (r < 0) { r = -r; // From 0 to choices - 1 } return r; } /** * diagnose() checks the maze and prints a warning if not every cell can be * reached from the upper left corner cell, or if there is a cycle reachable * from the upper left cell. * * DO NOT CHANGE THIS METHOD. Your code is expected to work with our copy * of this method. **/ protected void diagnose() { if ((horiz < 1) || (vert < 1) || ((horiz == 1) && (vert == 1))) { return; // There are no interior walls } boolean mazeFine = true; // Create an array that indicates whether each cell has been visited during // a depth-first traversal. boolean[][] cellVisited = new boolean[horiz][vert]; // Do a depth-first traversal. if (depthFirstSearch(0, 0, STARTHERE, cellVisited)) { System.out.println("Your maze has a cycle."); mazeFine = false; } // Check to be sure that every cell of the maze was visited. outerLoop: for (int j = 0; j < vert; j++) { for (int i = 0; i < horiz; i++) { if (!cellVisited[i][j]) { System.out.println("Not every cell in your maze is reachable from " + "every other cell."); mazeFine = false; break outerLoop; } } } if (mazeFine) { System.out.println("What a fine maze you've created!");

}

}

/** * depthFirstSearch() does a depth-first traversal of the maze, marking each * visited cell. Returns true if a cycle is found. * * DO NOT CHANGE THIS METHOD. Your code is expected to work with our copy * of this method. */ protected boolean depthFirstSearch(int x, int y, int fromWhere, boolean[][] cellVisited) { boolean cycleDetected = false; cellVisited[x][y] = true; // Visit the cell to the right? if ((fromWhere != FROMRIGHT) && !verticalWall(x, y)) { if (cellVisited[x + 1][y]) { cycleDetected = true; } else { cycleDetected = depthFirstSearch(x + 1, y, FROMLEFT, cellVisited) || cycleDetected; } } // Visit the cell below? if ((fromWhere != FROMBELOW) && !horizontalWall(x, y)) { if (cellVisited[x][y + 1]) { cycleDetected = true; } else { cycleDetected = depthFirstSearch(x, y + 1, FROMABOVE, cellVisited) || cycleDetected; } } // Visit the cell to the left? if ((fromWhere != FROMLEFT) && !verticalWall(x - 1, y)) { if (cellVisited[x - 1][y]) { cycleDetected = true; } else { cycleDetected = depthFirstSearch(x - 1, y, FROMRIGHT, cellVisited) || cycleDetected; } } // Visit the cell above? if ((fromWhere != FROMABOVE) && !horizontalWall(x, y - 1)) { if (cellVisited[x][y - 1]) { cycleDetected = true; } else { cycleDetected = depthFirstSearch(x, y - 1, FROMBELOW, cellVisited) ||

}

cycleDetected;

} }

return cycleDetected;

/** * main() creates a maze of dimensions specified on the command line, prints * the maze, and runs the diagnostic method to see if the maze is good. */ public static void main(String[] args) { int x = 39; int y = 15; /** * Read the input parameters. */ if (args.length > 0) { try { x = Integer.parseInt(args[0]); } catch (NumberFormatException e) { System.out.println("First argument to Simulation is not an number."); } } if (args.length > 1) { try { y = Integer.parseInt(args[1]); } catch (NumberFormatException e) { System.out.println("Second argument to Simulation is not an number."); } } Maze maze = new Maze(x, y); System.out.print(maze); maze.diagnose(); } }

/* DisjointSets.java */ package set; /** * A disjoint sets ADT. Performs union-by-rank and path compression. * Implemented using arrays. There is no error checking whatsoever. * By adding your own error-checking, you might save yourself a lot of time * finding bugs in your application code for Project 3 and Homework 9. * Without error-checking, expect bad things to happen if you try to unite * two elements that are not roots of their respective sets, or are not * distinct. * * Elements are represented by ints, numbered from zero. * * @author Mark Allen Weiss **/ public class DisjointSets { private int[] array; /** * Construct a disjoint sets object. * * @param numElements the initial number of elements--also the initial * number of disjoint sets, since every element is initially in its own set. **/ public DisjointSets(int numElements) { array = new int [numElements]; for (int i = 0; i < array.length; i++) { array[i] = -1; } } /** * union() unites two disjoint sets into a single set. A union-byrank * heuristic is used to choose the new root. This method will corrupt * the data structure if root1 and root2 are not roots of their respective * sets, or if they're identical. * * @param root1 the root of the first set. * @param root2 the root of the other set. **/ public void union(int root1, int root2) {

if (array[root2] < array[root1]) { array[root1] = root2; // root2 is taller; make root2 new root } else { if (array[root1] == array[root2]) { array[root1]--; // Both trees same height; new one is taller } array[root2] = root1; // root1 equal or taller; make root1 new root } } /** * find() finds the (int) name of the set containing a given element. * Performs path compression along the way. * * @param x the element sought. * @return the set containing x. **/ public int find(int x) { if (array[x] < 0) { return x; // x is the root of the tree; return it } else { // Find out who the root is; compress path by making the root x's parent. array[x] = find(array[x]); return array[x]; // Return the root } } /** * main() is test code. All the find()s on the same output line should be * identical. **/ public static void main(String[] args) { int NumElements = 128; int NumInSameSet = 16; DisjointSets s = new DisjointSets(NumElements); int set1, set2; for (int k = 1; k < NumInSameSet; k *= 2) { for (int j = 0; j + k < NumElements; j += 2 * k) { set1 = s.find(j); set2 = s.find(j + k); s.union(set1, set2); } } for (int i = 0; i < NumElements; i++) { System.out.print(s.find(i) + "*"); if (i % NumInSameSet == NumInSameSet - 1) { System.out.println();

} } System.out.println();

} } /* Sorts.java */ package sort;

public class Sorts { /** * Place any class (static) variables you would like to have here. **/ /** * countingSort() sorts an array of int keys according to the * values of _one_ of the base-16 digits of each key. "whichDigit" * indicates which digit is the sort key. A zero means sort on the least * significant (ones) digit; a one means sort on the second least * significant (sixteens) digit; and so on. * @param key is an array of ints. Assume no key is negative. * @param whichDigit is a number in 0...7 specifying which base-16 digit * is the sort key. * @return an array of type int, having the same length as "keys" * and containing the same keys sorted according to the chosen digit. * Note: This is a _newly_ created array. **/ public static int[] countingSort(int[] keys, int whichDigit) { // Replace the following line with your solution. return null; } /** * countingSort() sorts an array of int keys (using all 32 bits * of each key to determine the ordering). * @param key is an array of ints. Assume no key is negative. * @return an array of type int, having the same length as "keys" * and containing the same keys in sorted order. * Note: This is a _newly_ created array. **/ public static int[] radixSort(int[] keys) { // Replace the following line with your solution. return null; } /** * yell() prints an array of int keys. hexadecimal * (base 16). * @param key is an array of ints. **/ public static void yell(int[] keys) {

Each key is printed in

}

System.out.print("keys are [ "); for (int i = 0; i < keys.length; i++) { System.out.print(Integer.toString(keys[i], 16) + " "); } System.out.println("]");

/** * main() creates and sorts a sample array. * We recommend you add more tests of your own. * Your test code will not be graded. **/ public static void main(String[] args) { int[] keys = { Integer.parseInt("60013879", 16), Integer.parseInt("11111119", 16), Integer.parseInt("2c735010", 16), Integer.parseInt("2c732010", 16), Integer.parseInt("7fffffff", 16), Integer.parseInt("4001387c", 16), Integer.parseInt("10111119", 16), Integer.parseInt("529a7385", 16), Integer.parseInt("1e635010", 16), Integer.parseInt("28905879", 16), Integer.parseInt("00011119", 16), Integer.parseInt("00000000", 16), Integer.parseInt("7c725010", 16), Integer.parseInt("1e630010", 16), Integer.parseInt("111111e5", 16), Integer.parseInt("61feed0c", 16), Integer.parseInt("3bba7387", 16), Integer.parseInt("52953fdb", 16), Integer.parseInt("40013879", 16) }; yell(keys); keys = radixSort(keys); yell(keys); } }

/* Neighbors.java */ /* DO NOT CHANGE THIS FILE. */

/* YOUR SUBMISSION MUST WORK CORRECTLY WITH _OUR_ COPY OF THIS FILE. */ package graph; /** * The Neighbors class is provided solely as a way to allow the method * WUGraph.getNeighbors() to return two arrays at once. Do NOT use this class * for any other purpose. * * Since this class is NOT an abstract data type, but is merely a collection of * data, all fields are public. */ public class Neighbors { public Object[] neighborList; public int[] weightList; }

/* VertexPair.java */ package graph; /** * The VertexPair represents a pair of objects that act as vertices in a * WUGraph (weighted, undirected graph). The purpose of a VertexPair is to * act as a key in Java's built-in Hashtable class. The hashCode() and * equals() functions, which are called by Java's hash tables, are designed * so that the order of the two objects is immaterial; (u, v) is the same as * (v, u). */ class VertexPair { protected Object object1; protected Object object2; protected VertexPair(Object o1, Object o2) { object1 = o1; object2 = o2;

} /** * hashCode() returns a hashCode equal to the sum of the hashCodes of each * of the two objects of the pair, so that the order of the objects will * not affect the hashCode. Self-edges are treated differently: we don't * add an object's hashCode to itself, since the result would always be even. * We add one to the hashCode so that a self-edge will not collide with the * object itself if vertices and edges are stored in the same hash table. */ public int hashCode() { if (object1 == object2) { return object1.hashCode() + 1; } else { return object1.hashCode() + object2.hashCode(); } } /** * equals() returns true if this VertexPair represents the same unordered * pair of objects as the parameter "o". The order of the pair does not * affect the equality test, so (u, v) is found to be equal to (v, u). */ public boolean equals(Object o) { if (o instanceof VertexPair) { return ((object1 == ((VertexPair) o).object1) && (object2 == ((VertexPair) o).object2)) || ((object1 == ((VertexPair) o).object2) && (object2 == ((VertexPair) o).object1)); } else { return false; } } }

/* WUGraph.java */ package graph; import java.util.Hashtable; /** * The WUGraph class represents a weighted, undirected graph. edges are * permitted. */

Self-

public class WUGraph { /** * WUGraph() constructs a graph having no vertices or edges. */ public WUGraph(); /** * vertexCount() returns the number of vertices in the graph. */ public int vertexCount(); /** * edgeCount() returns the number of edges in the graph. */ public int edgeCount(); /** * getVertices() returns an array containing all the objects that serve * as vertices of the graph. The array's length is exactly equal to the * number of vertices. If the graph has no vertices, null is returned. * * (NOTE: Do not return any internal data structure you use to represent * vertices! Return only the same objects that were provided by the * calling application in calls to addVertex().) */ public Object[] getVertices(); /** * addVertex() adds a vertex (with no incident edges) to the graph. The * vertex's "name" is the object provided as the parameter "vertex". * If this object is already a vertex of the graph, the graph is unchanged. */ public void addVertex(Object vertex); /** * removeVertex() removes a vertex from the graph. incident on the

All edges

* deleted vertex are removed as well. If the parameter "vertex" does not * represent a vertex of the graph, the graph is unchanged. */ public void removeVertex(Object vertex); /** * isVertex() returns true if the parameter "vertex" represents a vertex of * the graph. */ public boolean isVertex(Object vertex); /** * degree() returns the degree of a vertex. Self-edges add only one to the * degree of a vertex. If the parameter "vertex" doesn't represent a vertex * of the graph, zero is returned. */ public int degree(Object vertex); /** * getNeighbors() returns a new Neighbors object referencing two arrays. The * Neighbors.neighborList array contains each object that is connected to the * input object by an edge. The Neighbors.weightList array contains the * weights of the corresponding edges. The length of both arrays is equal to * the number of edges incident on the input vertex. If the vertex has * degree zero, or if the parameter "vertex" does not represent a vertex of * the graph, null is returned (instead of a Neighbors object). * * The returned Neighbors object, and the two arrays, are both newly created. * No previously existing Neighbors object or array is changed. * * (NOTE: In the neighborList array, do not return any internal data * structure you use to represent vertices! Return only the same objects * that were provided by the calling application in calls to addVertex().) */ public Neighbors getNeighbors(Object vertex); /** * addEdge() adds an edge (u, v) to the graph. If either of the parameters * u and v does not represent a vertex of the graph, the graph is unchanged. * The edge is assigned a weight of "weight". If the edge is already * contained in the graph, the weight is updated to reflect the new value.

* Self-edges (where u == v) are allowed. */ public void addEdge(Object u, Object v, int weight); /** * removeEdge() removes an edge (u, v) from the graph. If either of the * parameters u and v does not represent a vertex of the graph, the graph * is unchanged. If (u, v) is not an edge of the graph, the graph is * unchanged. */ public void removeEdge(Object u, Object v); /** * isEdge() returns true if (u, v) is an edge of the graph. Returns false * if (u, v) is not an edge (including the case where either of the * parameters u and v does not represent a vertex of the graph). */ public boolean isEdge(Object u, Object v); /** * weight() returns the weight of (u, v). Returns zero if (u, v) is not * an edge (including the case where either of the parameters u and v does * not represent a vertex of the graph). * * (NOTE: A well-behaved application should try to avoid calling this * method for an edge that is not in the graph, and should certainly not * treat the result as if it actually represents an edge with weight zero. * However, some sort of default response is necessary for missing edges, * so we return zero. An exception would be more appropriate, but * also more annoying.) */ public int weight(Object u, Object v); }

/* DisjointSets.java */ package set; /**

* A disjoint sets ADT. Performs union-by-rank and path compression. * Implemented using arrays. There is no error checking whatsoever. * By adding your own error-checking, you might save yourself a lot of time * finding bugs in your application code for Project 3 and Homework 9. * Without error-checking, expect bad things to happen if you try to unite * two elements that are not roots of their respective sets, or are not * distinct. * * Elements are represented by ints, numbered from zero. * * @author Mark Allen Weiss **/ public class DisjointSets { private int[] array; /** * Construct a disjoint sets object. * * @param numElements the initial number of elements--also the initial * number of disjoint sets, since every element is initially in its own set. **/ public DisjointSets(int numElements) { array = new int [numElements]; for (int i = 0; i < array.length; i++) { array[i] = -1; } } /** * union() unites two disjoint sets into a single set. A union-byrank * heuristic is used to choose the new root. This method will corrupt * the data structure if root1 and root2 are not roots of their respective * sets, or if they're identical. * * @param root1 the root of the first set. * @param root2 the root of the other set. **/ public void union(int root1, int root2) { if (array[root2] < array[root1]) { array[root1] = root2; // root2 is taller; make root2 new root } else { if (array[root1] == array[root2]) { array[root1]--; // Both trees same height; new one is taller } array[root2] = root1; // root1 equal or taller; make root1 new root

}

}

/** * find() finds the (int) name of the set containing a given element. * Performs path compression along the way. * * @param x the element sought. * @return the set containing x. **/ public int find(int x) { if (array[x] < 0) { return x; // x is the root of the tree; return it } else { // Find out who the root is; compress path by making the root x's parent. array[x] = find(array[x]); return array[x]; // Return the root } } /** * main() is test code. All the find()s on the same output line should be * identical. **/ public static void main(String[] args) { int NumElements = 128; int NumInSameSet = 16; DisjointSets s = new DisjointSets(NumElements); int set1, set2; for (int k = 1; k < NumInSameSet; k *= 2) { for (int j = 0; j + k < NumElements; j += 2 * k) { set1 = s.find(j); set2 = s.find(j + k); s.union(set1, set2); } } for (int i = 0; i < NumElements; i++) { System.out.print(s.find(i) + "*"); if (i % NumInSameSet == NumInSameSet - 1) { System.out.println(); } } System.out.println(); }

}

/* Kruskal.java */ import java.util.Hashtable; import graph.*; import set.*; /** * The Kruskal class contains the method minSpanTree(), which implements * Kruskal's algorithm for computing a minimum spanning tree of a graph. */ public class Kruskal { /** * minSpanTree() returns a WUGraph that represents the minimum spanning tree * of the WUGraph g. The original WUGraph g is NOT changed. */ public static WUGraph minSpanTree(WUGraph g); }

/* KruskalTest.java */ /** * The KruskalTest class tests the Kruskal class. */ import graph.*; import java.util.*; public class KruskalTest { private static final int VERTICES = 10; private static final int MAXINT = 100; private static boolean tree = true; private static boolean minTree = true; public static void addRandomEdges(WUGraph g, Object[] vertArray) { int i, j; System.out.println("Adding random edges to graph.");

Random random = new Random(3); with seed 0

// Create a "Random" object

for (i = 0; i < vertArray.length; i++) { for (j = i; j < vertArray.length; j++) { int r = random.nextInt() % MAXINT; -99 and 99 if (r >= 0) { g.addEdge(vertArray[i], vertArray[j], r); } } } }

// Between

public static void DFS(WUGraph t, DFSVertex current, DFSVertex prev, int[] maxOnPath, int maxEdge) { Neighbors neigh; int i;

}

current.visited = true; maxOnPath[current.number] = maxEdge; neigh = t.getNeighbors(current); if (neigh != null) { for (i = 0; i < neigh.neighborList.length; i++) { DFSVertex next = (DFSVertex) neigh.neighborList[i]; if (next.visited) { if ((next != current) && (next != prev)) { tree = false; return; } } else if (neigh.weightList[i] > maxEdge) { DFS(t, next, current, maxOnPath, neigh.weightList[i]); } else { DFS(t, next, current, maxOnPath, maxEdge); } if (!tree) { return; } } }

public static void DFSTest(WUGraph g, WUGraph t, DFSVertex[] vertArray) { int[][] maxOnPath; Neighbors neigh; int i, j; System.out.println("Testing the tree."); maxOnPath = new int[VERTICES][VERTICES]; for (i = 0; i < VERTICES; i++) { for (j = 0; j < VERTICES; j++) { vertArray[j].visited = false; } DFS(t, vertArray[i], null, maxOnPath[i], -MAXINT);

for (j = 0; j < VERTICES; j++) { if (!vertArray[j].visited) { tree = false; } } if (!tree) { return; } } // // // // // //

for (i = 0; i < vertArray.length; i++) { for (j = 0; j < vertArray.length; j++) { System.out.print(" " + maxOnPath[i][j]); } System.out.println(); } for (i = 0; i < VERTICES; i++) { neigh = g.getNeighbors(vertArray[i]); if (neigh != null) { for (j = 0; j < neigh.neighborList.length; j++) { int v = ((DFSVertex) neigh.neighborList[j]).number; if (neigh.weightList[j] < maxOnPath[i][v]) { minTree = false; } } } } } public static void main(String[] args) { int i, j; int score; WUGraph g, t; DFSVertex[] vertArray; System.out.println("Running minimum spanning tree test."); System.out.println("Creating empty graph."); g = new WUGraph(); System.out.println("Adding " + VERTICES + " vertices."); vertArray = new DFSVertex[VERTICES]; for (i = 0; i < VERTICES; i++) { vertArray[i] = new DFSVertex(); vertArray[i].number = i; g.addVertex(vertArray[i]); } addRandomEdges(g, vertArray);

// // // // // //

for (i = 0; i < vertArray.length; i++) { for (j = 0; j < vertArray.length; j++) { System.out.print(" " + g.weight(vertArray[i], vertArray[j])); } System.out.println(); }

System.out.println("Finding the minimum spanning tree."); t = Kruskal.minSpanTree(g); // // // // // //

for (i = 0; i < vertArray.length; i++) { for (j = 0; j < vertArray.length; j++) { System.out.print(" " + t.weight(vertArray[i], vertArray[j])); } System.out.println(); } DFSTest(g, t, vertArray);

if (tree) { System.out.println("One point for creating a tree."); if (minTree) { System.out.println("Two points for creating a minimum spanning tree."); score = 3; } else { System.out.println("Not a minimum spanning tree."); score = 1; } } else { System.out.println("Not a tree."); score = 0; } System.out.println("Your Kruskal test score is " + score + " out of 3."); System.out.println(" (Be sure also to run WUGTest.java.)"); } } class DFSVertex { boolean visited; int number; }

/* WUGTest.java */ /** * The WUGTest class tests the WUGraph class. */ import graph.*; public class WUGTest {

private static int vertexTest(Object[] vertArray) { int result; int countDeduction = 0; int getDeduction = 0; int isVDeduction = 0; WUGraph g; Object[] wuVertArray; System.out.println("Running vertex test."); System.out.println("Creating empty graph."); g = new WUGraph(); result = g.vertexCount(); if (result != 0) { System.out.println("vertexCount() on empty graph returns " + result + " but should return 0."); countDeduction = 1; } result = g.edgeCount(); if (result != 0) { System.out.println("edgeCount() on empty graph returns " + result + " but should return 0."); countDeduction = 1; } if (g.getVertices() != null) { System.out.println("getVertices() on empty graph should return null" + " but doesn't."); getDeduction = 1; } if (g.isVertex(vertArray[0])) { System.out.println("isVertex() on vertex 0 should return false" + " but returns true."); isVDeduction = 1; } System.out.println("Adding vertex 0."); g.addVertex(vertArray[0]); result = g.vertexCount(); if (result != 1) { System.out.println("vertexCount() returns " + result + " but should return 1."); countDeduction = 1; } if (!g.isVertex(vertArray[0])) { System.out.println("isVertex() on vertex 0 should return true" + " but returns false."); isVDeduction = 1; } if (g.isVertex(vertArray[1])) { System.out.println("isVertex() on vertex 1 should return false" + " but returns true."); isVDeduction = 1; } wuVertArray = g.getVertices(); if (wuVertArray == null) {

System.out.println("getVertices() returns null but shouldn't."); getDeduction = 1; } else if (wuVertArray.length != 1) { System.out.println("getVertices() returns array of length " + wuVertArray.length + "; should have length 1."); getDeduction = 1; } else if (wuVertArray[0] != vertArray[0]) { System.out.println("getVertices() returns array containing" + " the wrong object."); getDeduction = 1; } System.out.println("Adding vertex 1."); g.addVertex(vertArray[1]); result = g.vertexCount(); if (result != 2) { System.out.println("vertexCount() returns " + result + " but should return 2."); countDeduction = 1; } if (!g.isVertex(vertArray[1])) { System.out.println("isVertex() on vertex 1 should return true" + " but returns false."); isVDeduction = 1; } System.out.println("Adding vertex 0."); g.addVertex(vertArray[0]); result = g.vertexCount(); if (result != 2) { System.out.println("vertexCount() returns " + result + " but should return 2."); countDeduction = 1; } if (!g.isVertex(vertArray[0])) { System.out.println("isVertex() on vertex 0 should return true " + " but returns false."); isVDeduction = 1; } wuVertArray = g.getVertices(); if (wuVertArray == null) { System.out.println("getVertices() returns null but shouldn't."); getDeduction = 1; } else if (wuVertArray.length != 2) { System.out.println("getVertices() returns array of length " + wuVertArray.length + "; should have length 2."); getDeduction = 1; } else if (((wuVertArray[0] != vertArray[0]) || (wuVertArray[1] != vertArray[1])) && ((wuVertArray[0] != vertArray[1]) || (wuVertArray[1] != vertArray[0]))) { System.out.println("getVertices() returns array containing" + " wrong objects."); getDeduction = 1; }

System.out.println("Adding vertex 2."); g.addVertex(vertArray[2]); System.out.println("Adding vertex 3."); g.addVertex(vertArray[3]); System.out.println("Adding vertex 4."); g.addVertex(vertArray[4]); result = g.vertexCount(); if (result != 5) { System.out.println("vertexCount() returns " + result + " but should return 5."); countDeduction = 1; } wuVertArray = g.getVertices(); if (wuVertArray == null) { System.out.println("getVertices() returns null but shouldn't."); getDeduction = 1; } else if (wuVertArray.length != 5) { System.out.println("getVertices() returns array of length " + wuVertArray.length + "; should have length 5."); getDeduction = 1; }

+

System.out.println("Removing vertex 0."); g.removeVertex(vertArray[0]); System.out.println("Removing vertex 3."); g.removeVertex(vertArray[3]); result = g.vertexCount(); if (result != 3) { System.out.println("vertexCount() returns " + result + " but should return 3."); countDeduction = 1; } System.out.println("Removing vertex 3."); g.removeVertex(vertArray[3]); result = g.vertexCount(); if (result != 3) { System.out.println("vertexCount() returns " + result + " but should return 3."); countDeduction = 1; } result = g.edgeCount(); if (result != 0) { System.out.println("edgeCount() on empty graph returns " + result " but should return 0.");

countDeduction = 1;

} if (g.isVertex(vertArray[0])) { System.out.println("isVertex() on vertex 0 should return false" + " but returns true."); isVDeduction = 1; } if (g.isVertex(vertArray[3])) { System.out.println("isVertex() on vertex 3 should return false" + " but returns true.");

isVDeduction = 1; } if (!g.isVertex(vertArray[4])) { System.out.println("isVertex() on vertex 4 should return true" + " but returns false."); isVDeduction = 1; } wuVertArray = g.getVertices(); if (wuVertArray == null) { System.out.println("getVertices() returns null but shouldn't."); getDeduction = 1; } else if (wuVertArray.length != 3) { System.out.println("getVertices() returns array of length " + wuVertArray.length + "; should have length 3."); getDeduction = 1; } else if (((wuVertArray[0] != vertArray[1]) && (wuVertArray[0] != vertArray[2]) && (wuVertArray[0] != vertArray[4])) || ((wuVertArray[1] != vertArray[1]) && (wuVertArray[1] != vertArray[2]) && (wuVertArray[1] != vertArray[4])) || ((wuVertArray[2] != vertArray[1]) && (wuVertArray[2] != vertArray[2]) && (wuVertArray[2] != vertArray[4]))) { System.out.println("getVertices() returns array containing " + "wrong objects."); getDeduction = 1; } else if ((wuVertArray[0] == wuVertArray[1]) || (wuVertArray[1] == wuVertArray[2]) || (wuVertArray[2] == wuVertArray[0])) { System.out.println("getVertices() returns array containing " + "duplicate objects."); getDeduction = 1; } System.out.println(); return countDeduction + 2 * getDeduction + isVDeduction; } private static int edgeTest(Object[] vertArray) { int result; int countDeduction = 0; int degreeDeduction = 0; int getDeduction = 0; int isDeduction = 0; int weightDeduction = 0; int remEDeduction = 0; int remVDeduction = 0; WUGraph g; Neighbors neigh; System.out.println("Running edge test."); System.out.println("Creating empty graph."); g = new WUGraph(); System.out.println("Adding vertex 0."); g.addVertex(vertArray[0]);

System.out.println("Adding g.addVertex(vertArray[1]); System.out.println("Adding g.addVertex(vertArray[2]); System.out.println("Adding g.addVertex(vertArray[3]); System.out.println("Adding g.addVertex(vertArray[4]); System.out.println("Adding g.addVertex(vertArray[5]); System.out.println("Adding g.addVertex(vertArray[6]); System.out.println("Adding g.addVertex(vertArray[7]); System.out.println("Adding g.addVertex(vertArray[8]); System.out.println("Adding g.addVertex(vertArray[9]);

vertex 1."); vertex 2."); vertex 3."); vertex 4."); vertex 5."); vertex 6."); vertex 7."); vertex 8."); vertex 9.");

result = g.degree(vertArray[3]); if (result != 0) { System.out.println("degree(vertex 3) returns " + result + " but should return 0."); degreeDeduction = 1; } if (g.getNeighbors(vertArray[3]) != null) { System.out.println("getNeighbors(vertex 3) should return null " + " but doesn't."); getDeduction = 1; } if (g.isEdge(vertArray[3], vertArray[7])) { System.out.println("isEdge(vertex 3, vertex 7) should return false " + " but returns true."); isDeduction = 1; } result = g.weight(vertArray[3], vertArray[7]); if (result != 0) { System.out.println("weight(vertex 3, vertex 7) returns " + result + " but should return 0."); weightDeduction = 1; } if (g.isEdge(vertArray[3], vertArray[3])) { System.out.println("isEdge(vertex 3, vertex 3) should return false " + " but returns true."); isDeduction = 1; } result = g.weight(vertArray[3], vertArray[3]); if (result != 0) { System.out.println("weight(vertex 3, vertex 3) returns " + result + " but should return 0."); weightDeduction = 1; }

System.out.println("Adding edge (3, 7) with weight 4."); g.addEdge(vertArray[3], vertArray[7], 4); result = g.vertexCount(); if (result != 10) { System.out.println("vertexCount() returns " + result + " but should return 10."); countDeduction = 1; } result = g.edgeCount(); if (result != 1) { System.out.println("edgeCount() returns " + result + " but should return 1."); countDeduction = 1; } if (!g.isEdge(vertArray[3], vertArray[7])) { System.out.println("isEdge(vertex 3, vertex 7) should return true " +

" but returns false."); isDeduction = 1;

+

} result = g.weight(vertArray[3], vertArray[7]); if (result != 4) { System.out.println("weight(vertex 3, vertex 7) returns " + result " but should return 4."); weightDeduction = 1;

" +

} if (!g.isEdge(vertArray[7], vertArray[3])) { System.out.println("isEdge(vertex 7, vertex 3) should return true isDeduction = 1;

" but returns false.");

} result = g.weight(vertArray[7], vertArray[3]); if (result != 4) { System.out.println("weight(vertex 7, vertex 3) returns " + result +

" but should return 4."); weightDeduction = 1;

} result = g.degree(vertArray[3]); if (result != 1) { System.out.println("degree(vertex 3) returns " + result + " but should return 1."); degreeDeduction = 1; } result = g.degree(vertArray[7]); if (result != 1) { System.out.println("degree(vertex 7) returns " + result + " but should return 1."); degreeDeduction = 1; } result = g.degree(vertArray[0]); if (result != 0) { System.out.println("degree(vertex 0) returns " + result + " but should return 0."); degreeDeduction = 1;

} System.out.println("Adding edge (3, 3) with weight 7."); g.addEdge(vertArray[3], vertArray[3], 7); result = g.edgeCount(); if (result != 2) { System.out.println("edgeCount() returns " + result + " but should return 2."); countDeduction = 1; } if (!g.isEdge(vertArray[3], vertArray[3])) { System.out.println("isEdge(vertex 3, vertex 3) should return true " +

" but returns false."); isDeduction = 1;

+

} result = g.weight(vertArray[3], vertArray[3]); if (result != 7) { System.out.println("weight(vertex 3, vertex 3) returns " + result " but should return 7."); weightDeduction = 1; } result = g.degree(vertArray[3]); if (result != 2) { System.out.println("degree(vertex 3) returns " + result + " but should return 2."); degreeDeduction = 1; } result = g.degree(vertArray[7]); if (result != 1) { System.out.println("degree(vertex 7) returns " + result + " but should return 1."); degreeDeduction = 1; } System.out.println("Adding edge (7, 3) with weight 9."); g.addEdge(vertArray[7], vertArray[3], 9); result = g.edgeCount(); if (result != 2) { System.out.println("edgeCount() returns " + result + " but should return 2."); countDeduction = 1; } if (!g.isEdge(vertArray[3], vertArray[7])) { System.out.println("isEdge(vertex 3, vertex 7) should return true

" +

" but returns false."); isDeduction = 1;

+

} result = g.weight(vertArray[3], vertArray[7]); if (result != 9) { System.out.println("weight(vertex 3, vertex 7) returns " + result " but should return 9."); weightDeduction = 1; }

if (!g.isEdge(vertArray[7], vertArray[3])) { System.out.println("isEdge(vertex 7, vertex 3) should return true " +

" but returns false."); isDeduction = 1;

+

} result = g.weight(vertArray[7], vertArray[3]); if (result != 9) { System.out.println("weight(vertex 7, vertex 3) returns " + result " but should return 9."); weightDeduction = 1;

} result = g.degree(vertArray[3]); if (result != 2) { System.out.println("degree(vertex 3) returns " + result + " but should return 2."); degreeDeduction = 1; } result = g.degree(vertArray[7]); if (result != 1) { System.out.println("degree(vertex 7) returns " + result + " but should return 1."); degreeDeduction = 1; } neigh = g.getNeighbors(vertArray[3]); if (neigh == null) { System.out.println("getNeighbors(vertex 3) improperly returns null."); getDeduction = 1; } else if (neigh.neighborList == null) { System.out.println("getNeighbors(vertex 3) improperly returns null" + " neighborList."); getDeduction = 1; } else if (neigh.weightList == null) { System.out.println("getNeighbors(vertex 3) improperly returns null" + " weightList."); getDeduction = 1; } else if (neigh.neighborList.length != 2) { System.out.println("getNeighbors(vertex 3) returns neighborList of" + " length " + neigh.neighborList.length + "; should have length 2."); getDeduction = 1; } else if (neigh.weightList.length != 2) { System.out.println("getNeighbors(vertex 3) returns weightList of" + " length " + neigh.weightList.length + "; should have length 2."); getDeduction = 1; } else if (((neigh.neighborList[0] != vertArray[3]) || (neigh.neighborList[1] != vertArray[7])) && ((neigh.neighborList[0] != vertArray[7]) || (neigh.neighborList[1] != vertArray[3]))) {

System.out.println("getNeighbors(vertex containing" + " wrong objects."); getDeduction = 1; } else if (((neigh.weightList[0] != 7) || 9)) && ((neigh.weightList[0] != 9) || 7))) { System.out.println("getNeighbors(vertex containing" + " wrong weights."); getDeduction = 1; }

3) returns array

(neigh.weightList[1] != (neigh.weightList[1] != 3) returns array

System.out.println("Adding edge (9, 0) with weight -2."); g.addEdge(vertArray[9], vertArray[0], -2); System.out.println("Adding edge (9, 3) with weight 2."); g.addEdge(vertArray[9], vertArray[3], 2); System.out.println("Adding edge (1, 6) with weight 8."); g.addEdge(vertArray[1], vertArray[6], 8); System.out.println("Adding edge (9, 7) with weight 5."); g.addEdge(vertArray[9], vertArray[7], 5); System.out.println("Adding edge (3, 1) with weight 1."); g.addEdge(vertArray[3], vertArray[1], 1); System.out.println("Adding edge (1, 1) with weight 3."); g.addEdge(vertArray[1], vertArray[1], 3); result = g.edgeCount(); if (result != 8) { System.out.println("edgeCount() returns " + result + " but should return 8."); countDeduction = 1; } if (!g.isEdge(vertArray[1], vertArray[3])) { System.out.println("isEdge(vertex 1, vertex 3) should return true " +

" but returns false."); isDeduction = 1;

+

} result = g.weight(vertArray[1], vertArray[3]); if (result != 1) { System.out.println("weight(vertex 1, vertex 3) returns " + result " but should return 1."); weightDeduction = 1;

" +

} if (!g.isEdge(vertArray[1], vertArray[1])) { System.out.println("isEdge(vertex 1, vertex 1) should return true isDeduction = 1;

" but returns false.");

} result = g.weight(vertArray[1], vertArray[1]); if (result != 3) { System.out.println("weight(vertex 1, vertex 1) returns " + result +

" but should return 3."); weightDeduction = 1;

} result = g.degree(vertArray[3]); if (result != 4) { System.out.println("degree(vertex 3) returns " + result + " but should return 4."); degreeDeduction = 1; } result = g.degree(vertArray[1]); if (result != 3) { System.out.println("degree(vertex 1) returns " + result + " but should return 3."); degreeDeduction = 1; } System.out.println("Removing edge (1, 6)."); g.removeEdge(vertArray[1], vertArray[6]); result = g.edgeCount(); if (result != 7) { System.out.println("edgeCount() returns " + result + " but should return 7."); remEDeduction = 1; } if (g.isEdge(vertArray[1], vertArray[6])) { System.out.println("isEdge(vertex 1, vertex 6) should return false " + " but returns true."); remEDeduction = 1; } if (g.isEdge(vertArray[6], vertArray[1])) { System.out.println("isEdge(vertex 6, vertex 1) should return false " + " but returns true."); remEDeduction = 1; } result = g.degree(vertArray[6]); if (result != 0) { System.out.println("degree(vertex 6) returns " + result + " but should return 0."); remEDeduction = 1; } result = g.degree(vertArray[1]); if (result != 2) { System.out.println("degree(vertex 1) returns " + result + " but should return 2."); remEDeduction = 1; } System.out.println("Removing vertex 3."); g.removeVertex(vertArray[3]); result = g.vertexCount(); if (result != 9) { System.out.println("vertexCount() returns " + result + " but should return 9."); remVDeduction = 1; } result = g.edgeCount(); if (result != 3) {

System.out.println("edgeCount() returns " + result + " but should return 3."); remVDeduction = 1;

} if (g.isVertex(vertArray[3])) { System.out.println("isVertex() on vertex 3 should return false" + " but returns true."); remVDeduction = 1; } result = g.degree(vertArray[3]); if (result != 0) { System.out.println("degree(vertex 3) returns " + result + " but should return 0."); remVDeduction = 1; } if (g.isEdge(vertArray[3], vertArray[3])) { System.out.println("isEdge(vertex 3, vertex 3) should return false " + " but returns true."); remVDeduction = 1; } if (g.isEdge(vertArray[3], vertArray[7])) { System.out.println("isEdge(vertex 3, vertex 7) should return false " + " but returns true."); remVDeduction = 1; } if (g.isEdge(vertArray[7], vertArray[3])) { System.out.println("isEdge(vertex 7, vertex 3) should return false " + " but returns true."); remVDeduction = 1; } if (g.isEdge(vertArray[3], vertArray[9])) { System.out.println("isEdge(vertex 3, vertex 9) should return false " + " but returns true."); remVDeduction = 1; } if (g.isEdge(vertArray[9], vertArray[3])) { System.out.println("isEdge(vertex 9, vertex 3) should return false " + " but returns true."); remVDeduction = 1; } if (g.isEdge(vertArray[3], vertArray[1])) { System.out.println("isEdge(vertex 3, vertex 1) should return false " + " but returns true."); remVDeduction = 1; } if (g.isEdge(vertArray[1], vertArray[3])) { System.out.println("isEdge(vertex 1, vertex 3) should return false " + " but returns true."); remVDeduction = 1; }

result = g.degree(vertArray[1]); if (result != 1) { System.out.println("degree(vertex 1) returns " + result + " but should return 1."); remVDeduction = 1; } result = g.degree(vertArray[7]); if (result != 1) { System.out.println("degree(vertex 7) returns " + result + " but should return 1."); remVDeduction = 1; } result = g.degree(vertArray[9]); if (result != 2) { System.out.println("degree(vertex 9) returns " + result + " but should return 2."); remVDeduction = 1; } neigh = g.getNeighbors(vertArray[7]); if (neigh == null) { System.out.println("getNeighbors(vertex 7) improperly returns null."); getDeduction = 1; } else if (neigh.neighborList == null) { System.out.println("getNeighbors(vertex 7) improperly returns null" + " neighborList."); getDeduction = 1; } else if (neigh.weightList == null) { System.out.println("getNeighbors(vertex 7) improperly returns null" + " weightList."); getDeduction = 1; } else if (neigh.neighborList.length != 1) { System.out.println("getNeighbors(vertex 7) returns neighborList of" + " length " + neigh.neighborList.length + "; should have length 1."); getDeduction = 1; } else if (neigh.weightList.length != 1) { System.out.println("getNeighbors(vertex 7) returns weightList of" + " length " + neigh.weightList.length + "; should have length 1."); getDeduction = 1; } else if (neigh.neighborList[0] != vertArray[9]) { System.out.println("getNeighbors(vertex 7) returns array containing" + " wrong object."); getDeduction = 1; } else if (neigh.weightList[0] != 5) { System.out.println("getNeighbors(vertex 7) returns array containing" + " wrong weight."); getDeduction = 1; }

System.out.println("Removing edge (1, 1)."); g.removeEdge(vertArray[1], vertArray[1]); result = g.edgeCount(); if (result != 2) { System.out.println("edgeCount() returns " + result + " but should return 2."); remVDeduction = 1; } if (g.isEdge(vertArray[1], vertArray[1])) { System.out.println("isEdge(vertex 1, vertex 1) should return false " + " but returns true."); remVDeduction = 1; } result = g.degree(vertArray[1]); if (result != 0) { System.out.println("degree(vertex 1) returns " + result + " but should return 0."); remVDeduction = 1; } System.out.println("Removing edge (7, 6)."); g.removeEdge(vertArray[7], vertArray[6]); System.out.println("Removing edge (3, 1)."); g.removeEdge(vertArray[3], vertArray[1]); System.out.println("Removing edge (1, 1)."); g.removeEdge(vertArray[1], vertArray[1]); result = g.edgeCount(); if (result != 2) { System.out.println("edgeCount() returns " + result + " but should return 2."); remVDeduction = 1; } if (g.isEdge(vertArray[1], vertArray[1])) { System.out.println("isEdge(vertex 1, vertex 1) should return false " + " but returns true."); remVDeduction = 1; } System.out.println("Removing edge (9, 7)."); g.removeEdge(vertArray[9], vertArray[7]); result = g.edgeCount(); if (result != 1) { System.out.println("edgeCount() returns " + result + " but should return 1."); remVDeduction = 1; } if (g.isEdge(vertArray[9], vertArray[7])) { System.out.println("isEdge(vertex 9, vertex 7) should return false " + " but returns true."); remVDeduction = 1; } if (g.isEdge(vertArray[7], vertArray[9])) { System.out.println("isEdge(vertex 7, vertex 9) should return false " +

remVDeduction = 1;

" but returns true.");

} System.out.println("Removing vertex 9."); g.removeVertex(vertArray[9]); result = g.vertexCount(); if (result != 8) { System.out.println("vertexCount() returns " + result + " but should return 8."); remVDeduction = 1; } result = g.edgeCount(); if (result != 0) { System.out.println("edgeCount() returns " + result + " but should return 0."); remVDeduction = 1; } if (g.isEdge(vertArray[9], vertArray[0])) { System.out.println("isEdge(vertex 9, vertex 0) should return false " + " but returns true."); remVDeduction = 1; } if (g.isEdge(vertArray[0], vertArray[9])) { System.out.println("isEdge(vertex 0, vertex 9) should return false " + " but returns true."); remVDeduction = 1; } result = g.degree(vertArray[9]); if (result != 0) { System.out.println("degree(vertex 9) returns " + result + " but should return 0."); remVDeduction = 1; } result = g.degree(vertArray[0]); if (result != 0) { System.out.println("degree(vertex 0) returns " + result + " but should return 0."); remVDeduction = 1; } System.out.println(); return countDeduction + degreeDeduction + 2 * getDeduction + isDeduction + weightDeduction + 2 * remEDeduction + 2 * remVDeduction; } public static final int VERTICES = 20; public static void main(String[] args) { int i; Object vertArray[] = new Object[VERTICES]; for (i = 0; i < VERTICES; i++) {

}

vertArray[i] = new Nothing();

int score = 14 - vertexTest(vertArray) - edgeTest(vertArray); if (score < 0) { score = 0; } System.out.println("Your WUGraph test score is " + (0.5 * (double) score) + " out of 7.0."); System.out.println(" (Be sure also to run KruskalTest.java.)"); } } class Nothing { }