University of Washington, Tacoma

University of Washington, Tacoma: TCSS 342, Winter 2005 (Stepp)Midterm Exam: Tuesday, February 8, 2005

Student Name: ______

Signature: ______

· You have 135 minutes, from 4:15pm – 6:30pm, to complete this exam.
You will lose credit if you keep working after 6:30pm when the instructor calls for your papers.

· This test is open-book/notes. You must work alone and may not use any computing devices of any kind.
If you violate the University Code of Conduct, you may receive a 0% for this exam and possibly further punishment.

· Write legibly and case-sensitively. Do not abbreviate Java code. You don't need to write any imports.

· You do not need to comment or worry about style, except when the question says to do so (for example, if it asks you to obey a certain Big-Oh limit or to avoid using a certain data structure in your solution).

· Please be quiet during the exam. If you have a question or need, please raise your hand.

· Corrections or clarifications to the exam will be written at the front of the room.

· When you have finished the exam, please turn in your exam quietly and leave the room.

Please note that there are 6 questions, and one extra credit question on the last page.

Good luck!

Score summary: (for grader use only)

Problem / Description / Max / Earned
1 / Big-Oh Analysis / 14
2 / Linked Node Manipulation / 16
3 / Linked List Implementation / 20
4 / Binary Search / 12
5 / Stack and Queue Programming / 20
6 / Sorting / 18
X / Extra Credit / 0
TOTAL / Total Points / 100

1. (14 points): Big-Oh Analysis

Calculate the exact value of the variable sum after each of the following code fragments, in terms of variable n. Use summation notation. Then use this value to give a tightly bounded Big-Oh analysis of the runtime of the code fragment.

(a)

int sum = 0;

for (int i = 1; i <= n * 3; i = i * 3) {

for (int j = n; j > n / 2; j--) {

sum++;

}

for (int j = 1; j < 10 * i / n; j++) {

sum++;

}

(b)

int sum = 0;

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= i; j = j * 2) {

sum++;

}

for (int i = n; i >= 1; i = i / 4) {

for (int j = n; j > i; j--) {

sum++;

}

2. (16 points): Linked Node Manipulation

Consider the following singly-linked Node class.

private class Node {
public Object element;
public Node next;
public Node(Object element) { this(element, null); }
public Node(Object element, Node next) {
this.element = element; this.next = next;
}
}

What code would be required to change the sequence of singly-linked Nodes, from the left picture to the right:

In both cases, front is a variable of type Node referring to the front of the chain of nodes. (The front and temp are not dummy headers. They are references of type Node.) You may declare one temporary Node variable if you need it, but you should solve this problem by adjusting links between nodes, not by reconstructing the list or by swapping element values between existing nodes. A solution that violates either of these restrictions gets at most half credit.

3. (20 points): Linked List Implementation

(The MyLinkedList and Node classes appear on the last page of this exam.)

Write a method public boolean isPalindrome() that could be put in the MyLinkedList class from Homework 2. (Recall that MyLinkedList is doubly-linked with dummy head and tail.) The isPalindrome method returns whether the list contains the same elements forwards as backwards. For example, if the linked list is stored in a variable theList and contains Integer objects with the following values:

[3, 9, 4, 2, 4, 9, 3]

Then the method call theList.isPalindrome() would return true.

If theList contains the values:

[11, 14, -27, 3, -27, 11, 19]

Then the method call theList.isPalindrome() would return false. The empty list and any one-element list should be considered palindromes. You may assume that no element in the list is null.

When your method completes, the contents of the list must be the same as when the method was called. For full credit, your method should be no worse than O(n), where n is the number of elements in the list. A solution that is not O(n) receives at most half credit. You may use the other methods in the MyLinkedList class to help you (keeping in mind their respective Big-Ohs).

4. (12 points): Binary Search Algorithm

Consider the following array of int data. The array contains 200 elements in sorted order. It is shown on this page in a 2D format of 10 elements per row because of page size constraints, but it is a one-dimensional array. For convenience, the table below of the array's elements lists the major indexes at left. For example, the element 27885 at index (40, +7) is the element at index 47 in the array.

// 200 elements placed into array

int[] numbers = new int[] {1506, 2020, 2177, ..., 99246, 99372};

index / +0 / +1 / +2 / +3 / +4 / +5 / +6 / +7 / +8 / +9
0 / 1506 / 2020 / 2177 / 2989 / 3068 / 3595 / 4206 / 5142 / 5958 / 6000
10 / 6933 / 7447 / 7872 / 9136 / 9782 / 10079 / 10640 / 10647 / 11333 / 11573
20 / 12345 / 12821 / 13016 / 13386 / 15211 / 16001 / 18365 / 18393 / 18795 / 19194
30 / 19286 / 20209 / 20524 / 21052 / 21094 / 21575 / 22395 / 22501 / 22847 / 23231
40 / 23355 / 23849 / 24253 / 24541 / 25306 / 25660 / 25701 / 27885 / 28421 / 28801
50 / 29140 / 29870 / 30630 / 31219 / 31998 / 32098 / 33101 / 33130 / 33167 / 36047
60 / 36644 / 37010 / 37428 / 37681 / 38018 / 38447 / 39335 / 39560 / 39587 / 40010
70 / 40132 / 40656 / 40909 / 41024 / 41740 / 41842 / 43058 / 44624 / 44904 / 45205
80 / 45290 / 45481 / 45571 / 45580 / 46805 / 47249 / 47612 / 48965 / 49307 / 49471
90 / 50143 / 50343 / 51527 / 52041 / 52281 / 53450 / 53751 / 54747 / 55057 / 55722
100 / 55788 / 56090 / 56487 / 56944 / 57827 / 58194 / 58330 / 58945 / 59072 / 59409
110 / 59641 / 59674 / 60572 / 61672 / 61694 / 61896 / 63567 / 63617 / 63822 / 64191
120 / 64518 / 65438 / 65481 / 65925 / 65945 / 66338 / 66988 / 67655 / 67737 / 67796
130 / 68980 / 70268 / 70553 / 70674 / 70738 / 71283 / 71432 / 72535 / 72544 / 72581
140 / 72726 / 72951 / 73199 / 73578 / 74271 / 74286 / 75309 / 75361 / 76449 / 77883
150 / 78368 / 78599 / 79264 / 80078 / 80271 / 81371 / 82019 / 82170 / 82212 / 83136
160 / 83248 / 83553 / 83563 / 84083 / 85207 / 85854 / 86264 / 86436 / 86546 / 86670
170 / 87610 / 88366 / 88807 / 89625 / 90182 / 90535 / 90633 / 91013 / 91422 / 91778
180 / 92157 / 93224 / 93990 / 94340 / 95232 / 95304 / 95876 / 96787 / 96882 / 96918
190 / 96979 / 97232 / 97994 / 98144 / 98426 / 98614 / 98921 / 99138 / 99246 / 99372

Using the binary search algorithm presented in class, answer the following for each method call in (a)-(b):

· Which indexes from the 200-element array would be examined, in order?

· What value would be returned from the method call?

(a) binarySearch(numbers, 56487)

(b) binarySearch(numbers, 95000)

5. (20 points): Stack and Queue Programming

(The Queue interface used in class, as well as the given subset of the methods of Java's Stack class, appear on the last page of this exam.)

Write a method public static void mergeReverse(Queue q1, Queue q2, Queue q3) that combines the contents of q1 and q2 into q3. Assume that q1 and q2 contain Integer elements, and that each of q1 and q2 has its elements in sorted order. The behavior of mergeReverse is to fill the initially-empty queue q3 with the combined contents of q1 and q2, but in reverse-sorted order. For example, if the queues have the following initial contents (where the left is the front of the queue, and the right is the back):

q1: [1, 4, 9, 27, 63, 95]

q2: [2, 3, 6, 39, 50, 87, 1000, 4096]

q3: []

After a call to mergeReverse(q1, q2, q3), the contents of the three queues should be:

q1: [1, 4, 9, 27, 63, 95]

q2: [2, 3, 6, 39, 50, 87, 1000, 4096]

q3: [4096, 1000, 95, 87, 63, 50, 39, 27, 9, 6, 4, 3, 2, 1]

When your method completes, the contents of the two queues q1 and q2 must be the same as when the method was called. You may assume that q3 is initially empty, and that neither q1, q2, nor any of their elements are null. Note that q1 and q2 may not contain the same number of elements, and they could be empty.

You may only declare at most one auxiliary data structure to solve this problem; it may be either a Queue or a Stack. You may not use any other auxiliary data structures to solve this problem, although you can have as many simple variables as you like. Solutions that violate these conditions receive at most half credit. For +1 point extra credit, write a solution that would work with any type of comparable object, not just Integers.

6. (18 points): Sorting

Consider the following array of int values. Each of parts (a)-(f) below shows this array in the middle of being sorted by unknown sorting algorithms. (If the algorithm is a multiple-loop algorithm, the array is shown after a few of these loops have completed. If the algorithm is recursive, the array is shown after the recursive calls have finished on each sub-part of the array.) Assume that the quick sort algorithm chooses the first element as its pivot at each pass.

For each of (a)-(f), examine the partially-sorted array, and circle the sorting algorithm that would most likely cause the array to have that appearance partway through the sort, or "none" if no sorting algorithm listed could possibly produce that ordering partway through. Circle exactly one answer for each question; you will receive no credit if you circle more than one answer for a question. The same sorting algorithm might be correct for more than one question, or might not be used at all.

Original: [ 7, 17, 22, -1, 9, 6, 11, 35, -3]

(a) [-3, -1, 6, 22, 9, 17, 11, 35, 7]