Binary trees. The CAR is the left child, and the CDR is the right child.
(EVAL (QUOTE (CDR (QUOTE (A B C)))))
?(B C)
if (myHashSet.contains(new Position(i, j))
System.out.println("Been there, done that.");
- (5 points) Why doesn't it work?
If Position uses the default equals(Object) and hashCode(), a newly created Position cannot possibly already be in the HashSet.
- (5 points) Briefly, how would you tell your friend to fix it?
The simplest way is probably to override equals(Object) and hashCode() within the Position class.
11
n, the size of the
problem.)
static int euclid(int x, int y) {
assert x > 0 && y > 0;
if (x > y) return euclid(x - y, y);
if (x < y) return euclid(x, y - x);
return y;
}
|
On average, and in the worst case, it will be O(n). There are various ways to choose n. The simplest (though not the most accurate) is just to choose n as the larger of x and y. |
euclid
method given above. static int euclid(int x, int y) {
assert x > 0 && y > 0;
while (x != y) {
if (x > y) x = x - y;
else y = y - x;
}
return y;
}
 |
 |
- Black pieces may only move right.
- White pieces may only move left.
- A piece can either:
- Move one square, into an unoccupied space, or
- Jump one piece of the opposite color, landing in an unoccupied space. (Jumped pieces are not removed.)
Represent this puzzle as a state space. For this puzzle, tell:
- (5 points) How would you represent a "state" in Java? (Be
specific.)
The simplest way is as a 7-element array; any distinguishable values can be used for black, white, and blank.
- (7 points) What are the "operators"? For each operator, tell
exactly what it does. (Hint: You probably need 6 or 7 operators.)
If you clearly didn't understand the basic idea that an operator transforms one state into another, you got zero points on this part. An operator that is represented by a method must have a state as its argument and a state as its result.
There are two simple approaches:- Move marble n (six marbles, therefore six operators).
- Move the marble in location n (seven locations, therefore seven operators).
- (5 points) To solve this puzzle, would you need to do a tree search
or a graph search? Explain your answer.
A tree search, since (by the nature of the puzzle) states cannot be repeated.
The correct answer is Heapsort, but a very good case can also be made for Selection Sort.
Yes. However, if you define your own hashCode() and equals(Object) methods for your keys, and those keys are changed in any way that changes the results of these two methods, the behavior of the HashMap will be undefined. (Note that this is not a problem for classes that you define, if you do not override one or both of these methods.)
- (5 points) Refactoring
Rewriting and rearchitecting a program, typically as it is being written.
- (5 points) Unit testing
Testing a module in isolation.
- (5 points) Source code control system
A tool for keeping track of all current and old versions of code, along with modification dates and who is or has been working on that code.
- (5 points) The DRY principle
Don't Repeat Yourself.
3/4. - (10 points) Define an ADT for the class
Fractionby specifying Java method (or constructor) headers for each operation. Be sure to include any essential constructors or methods.
Here's my version.(C) public Fraction(int numerator, int denominator)
(AT) public Fraction add(Fraction f)
(AT) public Fraction subtract(Fraction f)
(AT) public Fraction multiply(Fraction f)
(AT) public Fraction divide(Fraction f)
(A) public boolean equals(Fraction f)
(A) public int hashCode()(A) public boolean isNegative()
(A) public boolean isZero()
(A) public int compareTo(Fraction f)
(A) public String toString()
(A) public double toDouble()
And maybe these less useful methods:
(A) public int getNumerator()
(A) public int getDenominator()
Notes:
- Fractions are numbers. The whole point of having numbers is to do arithmetic on them.
- Apparently, nobody but me thought about comparing fractions.
- Fractions should be kept in the lowest
terms. This can be done automatically, in the constructor and
the arithmetic routines. There is no reason to expect the user to
do this.
- (5 points) Label each of your above methods as a constructor (C), accessor
(A), applicative transformer (AT), or mutative transformer (MT).
- (5 points) Tell whether you made your
Fractionobjects mutable or immutable, and why you did it that way.
Immutable. This is safer, consistent with Strings and other types of numbers, and allows easy use as keys in hash tables. Immutable objects are Thread-safe and never need to be cloned. There seems to be no reason to make Fractions mutable.
Note: Several students list mutative transformers (MT) yet claim their class is immutable. I find it difficult to understand this error.
- (6 points) Where in the
Fractionclass should you raise an exception?
In the constructor, and in divide(Fraction), to ensure the denominator is not zero.
- Preorder: A B C D E
- Inorder: B D E C A
- Postorder: E D C B A
Yes. Although there are cycles in the graph, the problem is small enough that a solution will be found quickly. Iterative deepening ensures that we won't get caught in a cycle forever.
Assign to each road a "cost" equal to the number of bridges on that road. Use Dijkstra's algorithm to determine the least-cost paths.
Please note that I did not ask you to explain Dijkstra's algorithm!
Create a new binary tree whose data is the String in the given binary tree. (Strings are immutable, so there's no need to make a copy of the string.) Recursively copy the left subtree and the right subtree, and use these copies in the new binary tree.
Incidentally, a good way to implement this is to write a copy constructor (a constructor that takes an object and produces a new, identical object).
I spent considerable time in lecture explaining why implementing Cloneable will not work.