Assignment: #FinalAssessment Due: 12/12/02018 Points: 15
1. Given ArrayList a = new ArrayList(); The memory for the object variable a gets allocated from the _____ and the memory for the ArrayList object gets allocated from the _____.

2. class Foo does not compile.

```   public class Foo {
public static void main(String[] argv) {
Foo f = new Foo();
}
public Foo() throws Exception { }

//
// note:  Exception e = new Exception();
//        The expression:  e instanceof RuntimeException
//        evaluates to false.
//
}
```
Explain the two ways class Foo can be modified to get it to compile.

3. Array B and array C are unsorted arrays each having n elements. The Big-O notation for a failed search of both arrays is what?

```   a. O(log n)   b. O(n log n)   c. O(n)   d.  O(n^2)
```

4. Record the Big-O notation for a failed search of a balanced binary search tree.

5. Record the Big-O notation for a failed search of a degenerate binary search tree.

6. The worst case run-time for algorithm A is defined by the function: f(n) = 2.5n^2 + 4n + 3.14. Record the Big-O notation for algorithm A.

7. Rewrite the following code snippet without using the logical NOT operator.

```   if (!isEmpty()) {   // isEmpty() returns a boolean value
A;
} else {
B;
}
```

8. Rewrite the following code snippet without using the logical NOT operator.

```   !(yn == 'n' || yn == 'N')
```

9. Rewrite the following code snippet without using the logical NOT operator.

```   !(!false && !true)
```

10. Write the method comment block for method goo.

```   int goo(Scanner stdin) {
int ntries = 2, sum = 0;
do {
System.out.print("enter an integer: ");
try {
sum += Integer.parseInt(stdin.next());
} catch (NumberFormatException e) {
ntries--;
}
} while (ntries != 0);
return sum;
}
```

11. This is a #FinalAssessment, so let's look one final time at Java's final keyword.

```   [a]  What does it mean when a class is declared final?
[b]  What does it mean when a method is declared final?
[c]  What does it mean when a variable is declared final?
```

12. Briefly explain the difference between overriding a method versus overloading a method.

13. Explain why class Int prints:

```      205 == 205
x != y
!x.equals(y)
Int@5fe5c6f...Int@6979e8cb
```
```   public class Int {
public int i;
public Int(int i) { this.i = i; }
public static void main(String[] argv) {
Int x = new Int(205);
Int y = new Int(205);
if (x.i == y.i) System.out.println(x.i + " == " + y.i);
if (x == y) System.out.println("x == y");
else System.out.println("x != y");
if (x.equals(y)) System.out.println("x.equals(y)");
else System.out.println("!x.equals(y)");
System.out.println(x + "..." + y);
}
}
```

14. The following code snippet prints 3.14. Document how the code computes Pi rounded to the nearest hundredth.

```   Stack stack = new Stack();
stack.push(100).push(3).push(11).push(3).push(100);
Queue queue = new Queue();
queue.enqueue('f').enqueue('o').enqueue('o').enqueue('!');
int y = stack.pop();
do {
char m = queue.dequeue();
int n = stack.pop();
if (m == 'f') y = y * n;
else if (m == 'o') y = y + n;
else if (m == '!') answer = (double)y / n;
```

15. Write the file comment block for class Lognames and the method comment block for method logname.

```   public class Lognames {
public static void main(String[] argv) {
char d[] = { 'd','e','n','n','i','s','m','r','i','t','c','h','i','e' };
char j[] = { 'j','a','m','e','s',' ','a','g','o','s','l','i','n','g' };
int  i[] = { 7, 6, 0 };
System.out.println(logname(d, i));  // c created circa 1972
System.out.println(logname(j, i));  // java created circa 1995
}
static char[] logname(char a[], int[] b) {
char[] c = new char[b.length];
c[0] = a[b[2]];
c[1] = a[b[1]];
c[2] = a[b[0]];
return c;
}
}
```

16. Rewrite the for statement so that is uses polymorphism.

```   abstract class Foo { abstract int f(int x); }
class Goo extends Foo { int f(int a) { return a - 95; } }
class Moo extends Foo { int f(int b) { return b; } }
class Boo extends Foo { int f(int c) { return c + 35; } }

public class Polymorphism {
public static void main(String[] a) {
Foo[] y = { new Goo(), new Moo(), new Boo() };
for (int i = 0, j = y.length; i < j; i++) {
if (!(y[i] instanceof Foo)) continue;
if (y[i] instanceof Goo) {
Goo x = (Goo) y[i];
System.out.println(x.f(205));
} else if (y[i] instanceof Moo) {
Moo x = (Moo) y[i];
System.out.println(x.f(205));
} else if (y[i] instanceof Boo) {
Boo x = (Boo) y[i];
System.out.println(x.f(205));
}
}
}
}
```

17. Is class QueueOrStack an implementation of a stack or queue?

```   public class QueueOrStack {
private Vector<Object> v = new Vector<Object>();
public void push_or_enqueue(Object o)  {
v.add(o);   // object o appended to the end of v
}
public Object pop_or_dequeue() {
if (v.size() == 0) return null;
return v.remove(0);
// via class Vector API at Oracle.com:
// Removes the element at the specified position
// in this Vector. Shifts any subsequent elements
// to the left (subtracts one from their indices).
// Returns the element that was removed from the Vector.
}
public static void main(String[] argv) {
int[] y = { 1, 5, 3, 2, 9 };
QueueOrStack q_or_s = new QueueOrStack();
for (int i = 0; i < y.length; i++)
q_or_s.push_or_enqueue(y[i]);
for (int i = 0; i < y.length; i++)
System.out.println(q_or_s.pop_or_dequeue());
}
}
```

18. Write the file comment block for class StroustrupCPP.

```   public class StroustrupCPP {  // bs created C++ circa 01985
public static void main(String[] argv) {
System.out.println(stroustrupCPP());
}
static int stroustrupCPP() { return stroustrupCPP(2, 2 * 2); }
static int stroustrupCPP(int a, int b) {
if (0 == b) return 1;
return a * stroustrupCPP(a, b - 1);
}
}
```

19. Briefly explain the motivation for a class to implement interface Serializable.

20. Briefly explain the motivation for a class to implement interface Cloneable.

21. Briefly explain the motivation for having an instance method return this.

22. No or Yes: The statement Object[] o = new Object[205]; results in the instantiation of 205 objects of type Object.

23. A linked-list has a "head" pointer to the first node in the list. Briefly explain the motivation for using a "tail" pointer.

24. Match application with either stack or queue.

```   method calls
line printer spooler
buffered I/O
RPN calculator
```

25. If a class contains an abstract method, then it must be declared abstract. Briefly explain the motivation for declaring classes and methods to be abstract.

26. int[] a = { 5, 2, 9, 4, 7, 8, 3, 6 }; is sorted using selection sort. Print a after the third pass through the array.

27. Given the following tree:

```   node: 50;  left: 10    right: 75
node: 10;  left: 7     right: 15
node:  7;  left: null  right: null
node: 15;  left: 12    right: null
node: 12;  left: null  right: null
node: 75;  left: 60    right: null
node: 60;  left: 55    right: 64
node: 55;  left: null  right: null
node: 64;  left: null  right: null
```
```[a] Record all of the leaf nodes.
[b] Record the parent of node 60.
[c] Record the sibling of node 64.
[d] Record the grandparent of node 15.
[e] No or Yes:  Node 75 has two children.
[f] Record all of the descendants of node 10.
```

28. Record the post-order traversal (left right root) for the following BST.

```                           87
/    \
/      \
84        103
/  \       / \
68    86    90  109
/  \        /  \
32   74      88   97
/  \
70   80
```

29. Draw the BST for the following inputs. No duplicates are allowed.

```
J A M E S G O S L I N G
```
Note: numerically (Unicode): A < B < C < ...

30. The following is not a BST, but it is a binary tree and it can be traversed. Record the in-order traversal (left root right) for the following binary tree.

```
or
|
+------+--------+
|               |
program        programmed
|
+-----+
|
be
```