1. Explain why a static method cannot use the non-static attributes of an object
using `this`

.

A static method is associated with a class rather than with object instances of the
class; thus, there is no instance for `this`

to refer to.

2. What is a singleton?

A singleton is a class that is instantiated exactly once and is used to ensure that there is at most one instance of the class and to provide a global point of access to the instance.

3. What is the difference between an overloaded method and an overridden method? Can you override an overloaded method?

An overloaded method is a method that has the same name as another method in the same class; the signature of the overloaded methods must be different. An overridden method is a method in a subclass that has the same signature as a non-private method in one of the superclasses.

4. Suppose that you are implementing an immutable class that has a mutable attribute. What must you do to ensure that objects of your class are truly immutable?

You need to follow the recipe for immutability from the slides on Jan 16.

-there must be no mutator methods

-the class must be marked `final`

so that no one can
extend it

-all attributes should be `private`

and `final`

-must be no privacy leaks of mutable attributes (e.g., defensive
copies are required)

5. (too hard for a CSE1030 exam)
When implementing `equals`

you were told to use the
`getClass`

method to check if the two objects being compared
had the same class. Discuss the consequences of using `getClass`

in `equals`

when inheritance is involved.

Using `getClass`

breaks substitutability. Suppose that you
have a parent class `X`

and a child class `Y`

.
If you implement `equals`

in `X`

using
`getClass`

then `x.equals(y)`

is always false
for any `X`

instance `x`

and `Y`

instance `y`

(because `x.getClass()`

is not
equal to `y.getClass()`

).

6. Suppose that you are implementing the group of classes in an
inheritance hierarchy, such as the
`Dog`

hierarchy that we studied. When could the topmost
class (e.g., `Dog`

) be an interface instead of an
abstract class?

The topmost class could instead be an interface if it has only methods and no attributes (because an interface is not allowed to have attributes).

7. What is the most important thing to remember when working with static attributes in an inheritance hierarchy?

There is only one copy of a static attribute and it resides in the class where it was defined; each subclass does not get its own independent copy of the static attribute.

8. Describe the steps that are taken when trying to prove that a recursive algorithm is correct.

1. Prove that the base cases are correct.

2. For each recursive case, assume that the recursive invocation
is correct, and prove that the case is correct.

9. What is the purpose of an iterator?

An iterator is an object that lets a client traverse all of the elements of a collection.

10. What is the solution to the puzzle on Slide 3 from Feb 25?

You are not allowed to override `equals`

; however, you
are allowed to overload it:

// in Enigma class public boolean equals(Enigma e) { return false; }

11. What is the definition of a binary search tree?

A binary search tree is a binary tree where the nodes are arranged according
to three rules:

1. all of the nodes in the left subtree have data elements that are less than
the data element of the root node

2. all of the nodes in the right subtree have data elements that
are greater than or equal to the data element of the root node

3. rules 1 and 2 apply recursively to every subtree

12. Why are linked lists and trees considered recursive data structures?

A linked list can be thought of as a sequence of nodes where each
node is the head of a sublist.

A tree is an arrangement of nodes where each node is the
root of a subtree.

1. What kind of relationship between two classes does inheritance model?

Inheritance models the is-a or is-substitutable-for relationship.

2. Suppose that you have three classes X, Y, and Z, where X is the parent class of Y, and Y is the parent class of Z. Explain what happens when a Z object is created.

The Z constructor runs, which causes the Y constructor to run, which causes the X constructor to run. The X subobject constructor finishes, which allows the Y subobject constructor to finish, which allows the Z object constructor to finally finish. In other words, the subobjects of Z are constructed in order from the top of the hierarchy down.

3. Suppose that you have two classes X and Y, where X is the parent class
of Y. Suppose that Y overrides a method named `foo`

:

public class Y { // @pre. s begins with the character 'a' public int foo(String s) { // ... }

Give a different and acceptable precondition for `foo`

in class X.

Y must not strengthen the precondition of the method in X;
thus, the precondition of the method in X must be stronger
than the precondition of the method in Y. There are an
infinite number of possibilities:

@pre. s begins with the string "ab"

@pre. s begins with the character 'a' and ends with 'y'

@pre. s begins with the character 'a' and s has length 5

4. Suppose that you have two classes X and Y, where X is the parent class
of Y. Suppose that Y overrides a method named `bar`

:

public class Y { // @return a list of words that start with the string s public List<String> bar(String s) { // ... }

Give a different and acceptable postcondition for `bar`

in class X.

Y must not weaken the postcondition of the method in X;
thus, the postcondition of the method in X must be weaker
than the postcondition of the method in Y. There are an
infinite number of possibilities:

@return a list of words that contains the string s

@return a list of words that starts with the first character of s

5. Suppose that you have two classes X and Y, where X is the parent class
of Y. Suppose that Y overrides a method named `baz`

:

public class Y { public void baz() throws Exception { // ... }

Give all of the possible legal signatures plus
throw clauses for `baz`

in class X that throw only a single kind of throwable object
(ignoring overloaded versions of `baz`

).

The method in
Y must only throw exceptions that are substitutable for
the exceptions thrown by the methods in X. In other words,
the method in X can throw an instance of any superclass of
`Exception`

. In Java, `Throwable`

is the root class of all throwable objects, so there are
only two possible solutions:

`baz() throws Exception`

`baz() throws Throwable`

1. Draw the UML class diagram for the dice rolling GUI application
from the Mar 04 lecture:

Your diagram should include the model, view, controller, JLabel,
and JButton classes, plus any other classes that you think are
necessary (do not show any classes related to the image of
the die or any inheritance relationships, however).

1. What is the maximum number of elements that can be held in
a binary search tree of height `m`

? (the height of
a tree is the number of levels of the tree.) Such a tree
is called a full tree.

`m = 1`

, elements = 1

`m = 2`

, elements = 1 + 2 = 3

`m = 3`

, elements = 1 + 2 + 4 = 7

`m = 4`

, elements = 1 + 2 + 4 + 8 = 15

`m = 5`

, elements = 1 + 2 + 4 + 8 + 16 = 31

`m`

, elements = 2^{m} - 1

2. Suppose that you have a full tree. What is an approximate recurrence relation for recursive search of the tree? (see question 4 below if you cannot recall the search algorithm) You can assume that checking the base cases and performing a comparison can be done in one unit of time (or constant time).

T(n) is the amount of time that it takes to search a tree having
n elements. To search a binary search tree for a particular element,
you check if the root node holds the element (this is the base case);
if it does not then you perform a comparison to determine which
subtree to recursively search. The question says that checking the base cases
and performing a comparison can be done in one unit of time.
The recursive search must search a tree having approximately
n/2 elements. The overall recurrence relation is:

T(n) = T(n / 2) + 1

3. Solve the recurrence relation from the previous question.

`T(n) = T(n / 2) + 1`

`= (T(n / 2 / 2) + 1) + 1`

`= T(n / 4) + 2`

`= (T(n / 4 / 2) + 1) + 2`

`= T(n / 8) + 3`

`= (T(n / 8 / 2) + 1) + 3`

`= T(n / 16) + 4`

`= T(n / 2`

^{k}) + k

Solving for k in terms of n by using T(1) = 1 yields

`k = log(n)`

Substituting k into the recurrence relation yields

`T(n) = log(n) ∈ O(log(n))`

4. The recursive search algorithm for a binary search tree can be stated as follows (the generic type syntax has been removed for simplicity):

boolean contains(E element, Node subtreeRoot) { if (subtreeRoot == null) { return false; } if (element.equals(subtreeRoot.data)) { return true; } boolean result; if (element.compareTo(subtreeRoot.data) < 0) { result = contains(element, subtreeRoot.left); } else { result = contains(element, subtreeRoot.right); } return result; }

(a) Prove that the algorithm terminates.

(b) Prove that the algorithm is correct.

To prove termination:

1. `contains(e, node)`

searches a tree of size `n`

2. Each recursive call `contains(e, node.left)`

or
`contains(e, node.right)`

searches a tree of size `n/2 < n`

for all `n > 1`

To prove correctness:

1. (Correctness of first base case) If subtreeRoot is null then
the element is not in the tree; the base case correctly returns false.

(Correctness of second base case) If the subtreeRoot holds the
element then the element is in the tree; the base case correctly returns true.

2. Assume that `contains(e, subtreeRoot.left)`

correctly
determines if the left subtree contains `e`

.
Assume that `contains(e, subtreeRoot.right)`

correctly
determines if the right subtree contains `e`

.
If `e`

is smaller than the element in `subtreeRoot`

then it must be in the left subtree; this recursive case invokes
`contains(e, subtreeRoot.left)`

which we have assumed
correctly searches the left subtree.
If `e`

is greater than or equal to the element in `subtreeRoot`

then it must be in the right subtree; this recursive case invokes
`contains(e, subtreeRoot.right)`

which we have assumed
correctly searches the right subtree.

1. Consider the simple linked list implementation that we studied
in this course and Java's `ArrayList`

(which you can
think of as being an array that can grow in size): Which is more
efficient in terms of big-O complexity for the following operations:

- getting an element using an integer index
- inserting an element at the front of the list
- inserting an element at the back of the list
- inserting an element in the middle of the list

Getting an element using an integer index is faster for
`ArrayList`

: O(1) vs O(n)

Inserting an element at the front of the list is faster for
`LinkedList`

: O(1) vs O(n)

Inserting an element at the back of the list is faster for
`ArrayList`

: O(1) vs O(n) unless
the `LinkedList`

implementation has a reference
to the last element in which case the complexity is the same
for both lists.

Inserting an element in the middle of the list is O(1) for
a linked list if you are doing a traversal and are at the
location where you want to insert; however, the traversal
to find the insertion point is O(n), which is the same
complexity for inserting into the middle of an `ArrayList`

.

2. Describe an algorithm (recursive or otherwise) that searches a linked list for a given value (returns true if the element is in the list, and false otherwise). Your algorithm can use plain English (instead of a programming language).

An iterative algorithm would look something like:

contains(e): n = head node while n is not null { if n.data equals e { return true } n = n.next } return false

An recursive algorithm would look something like:

contains(e, node): if node is null { return false } if node.data equals e { return true } contains(e, node.next)

3. (too hard for a CSE1030 exam) Describe an algorithm for removing an element from a binary search tree. Your algorithm does not need to be efficient but it must preserve the search tree property of the tree.

You can google the answer for a full explanation; it looks something like this:

if the element is in a leaf node { remove the node (set it to null) } else if the element is in a node with only 1 child node { replace the node with the child node } else if the element is in a node with 2 child nodes { set the element in the node equal to the largest value in the left subtree of the node remove the node containing the largest value in the left subtree of the node }

4. Draw a binary search tree containing 8 unique integers; the root of your tree must have a left and right child. What is the inorder, preorder, and postorder traversals of the tree you have drawn?

Here is one possibility:

inorder: 1, 2, 3, 4, 5, 6, 7, 8

preorder: 5, 2, 1, 4, 3, 6, 8, 7

postorder: 1, 3, 4, 2, 7, 8, 6, 5

5. Explain how to use a stack to check if a sequence of parentheses is correct nested; you only need to consider round brackets ().

This is a simplified version of eCheck11B from the Apr 1 slides: Process the sequence one character at a time. If the character is an "(" then push it on to the stack. If the character is an ")" then pop the stack. If you ever attempt to pop an empty stack, then there are more closing brackets ")" than opening brackets "(" so the sequence is not correctly nested. If the stack is not empty when you have finished processing the sequence, then there are more opening brackets "(" than closing brackets ")" so the sequence is not correctly nested.

6. (From Introduction to Programming in Java, Sedgewick and Wayne)
Suppose that a client performs an intermixed sequence of enqueue
and dequeue operations on a queue. The enqueue operations put the
integers 0 through 9 in order on the queue; the dequeue operations
print out the returned value. Which of the following sequence(s)
could not occur?

a. 0 1 2 3 4 5 6 7 8 9

b. 4 6 8 7 5 3 2 9 0 1

c. 2 5 6 7 4 8 9 3 1 0

d. 4 3 2 1 0 5 6 7 8 9

The question says that the numbers are enqueued in order, so the 0 must be the first number enqueued. Because a queue is a first-in-first-out data structure, the first element dequeued must also be the 0. Only one of the sequences (a) starts with 0 so (b), (c), and (d) could not occur.

7. See previous question: Which sequence(s) could have been produced using a stack instead of a queue, and what order of commands must have been given to produce the output? (for the stack, the pop operations print out the returned value)

The easiest way to solve this problem is to draw a stack and check if
you can generate the sequences. I will give you the operations
that generate as much of the sequences as possible:

a. push(0), pop(), push(1), pop(), push(2), pop(), ..., push(9), pop(), success!

b. push(0), push(1), push(2), push(3), push(4), pop(), push(5), push(6), pop(),
push(7), push(8), pop(), pop(), pop(), pop(), pop(), push(9), pop(), fail!

c. push(0), push(1), push(2),
pop(),
push(3), push(4), push(5),
pop(),
push(6),
pop(),
push(7),
pop(),
pop(),
push(8),
pop(),
push(9),
pop(),
pop(),
pop(),
pop(), success!

d. push(0), push(1), push(2), push(3), push(4),
pop(),
pop(),
pop(),
pop(),
pop(),
push(5), pop(),
push(6), pop(),
push(7), pop(),
push(8), pop(),
push(9), pop(), success!