- Find bugs in my implementation. A bug report must contain enough
information for me to reproduce the bug. For extra extra credit,
suggest a fix.
- We have discussed enough concepts to write a tiny compiler for
Java expressions. The compiler should read a file containing
expressions like (3+4)+7-8+2, represent the expressions using a binary
tree, then traverse this binary tree generating duckMachine
instructions in an object file:
0 LOAD 100 # get 3 to the acc
1 ADD 101 # 3 + 4
2 STORE 105 # save result in temp location 105
3 LOAD 102 # get 7 to the acc
4 SUBTRACT 103 # 7 - 8
5 STORE 106 # save result in temp location 106
6 LOAD 105 # get (3+4) to the acc
7 ADD 106 # (3+4) + (7-8)
8 STORE 107 # save result in temp location 107
9 LOAD 107 # get ((3+4)+(7-8)) to the acc
10 ADD 104 # ((3+4)+(7-8)) + 2
11 STORE 108 # save result in temp location 108
12 LOAD 108 # leave result in the acc
100 3
101 4
102 7
103 8
104 2
I've produced (by hand) the sequence of instructions that a simple
compiler might produce. You can clearly optimize the sequence by
avoiding pairs of store/load, by re-ordering the expression taking
advantage of the commutativity of the operators, etc.
- If you haven't noticed yet, in the textual interface to the
hardware machine, the commands "step" and "run" expect the name of a
file containing a visitor. This filename is internally converted to a
visitor object using the introspective capabilities of Java (see the
package java.lang.reflect). The relevant class in my code is
duckMachine.operatingSystem.VisitorFile. Try to write this class!
- The solution to the sameFringe problem discussed in class is
rather inefficient. Write a better solution and provide timings that
show that it performs better on large trees. There are several ways to
optimize the problem. One of them is to have two threads, each
traversing the tree in preorder. The threads communicate via streams
with a controller. The controller reads the numbers coming on its two
input streams, and whenever it receives two unequal numbers, it kills
the threads, and immediately returns false.
The above idea can be implemented without using threads at all by
time-slicing the visit of each tree. First you visit the first tree in
preorder until you find a leaf. Before returning that leaf, you save
enough information so that you can resume the traversal from where you
left it. Then you return the value of the leaf to the controller,
which starts the traversal of the second tree, compares the values of
the leaves, and resumes the traversals only if necessary.
- Try the Spirited Binary Trees problem discussed in class.
- Look up the remaining paradoxes of Zeno, and write a small
paragraph on each.
- Your grade file looks like:
Code Lab1 Lab2 Lab3 Lab4 Midterm
03481 85 100 9 73
07546 95 90 95 0 56
10115 99 100 50 67
10466 100 100 75 100 69
...
97593 0 0 0 31
98708 96 100 66 95 49
Min 0 0 0 0 0
Max 100 100 100 100 100
I started writing a little program to process this file, but decided
it'd be a great extra credit problem instead. What's needed is a
program that parses the above file (using a StreamTokenizer), and then
produces some statistical information: the average, standard
deviation, etc. Ideally you should provide a graphical user interface
that displays the current distribution and lets the instructor curve
it, etc. If you are interested, talk to me for details.
- Towers of Hanoi: You are given three pegs A, B, and C, and n
squares of varying size. Initially the squares are stacked on peg A in
order of decreasing size, the largest square on the bottom. The
problem is to move the squares from peg A to peg B one at a time in
such a way that no square is ever placed on a smaller square. Peg C
may be used for temporary storage of squares. Write a Java method that
takes n as an argument and outputs the sequence of moves. For example,
here is my output when calling hanoi(3):
move from a to b
move from a to c
move from b to c
move from a to b
move from c to a
move from c to b
move from a to b
For extra extra credit, implement a graphical interface that shows the
pegs and the moves.
- This problem builds on Lab 4. Finish the lab first. The
organization of our code makes it easy to add new visitors that
operate on instructions. It is considerably harder (though not
impossible) to add a new instruction to the machine without modifying
any code. Try adding an instruction MULTIPLY to the machine: you
cannot update any existing code. Hint: The book: A Little Java
with Patterns has the solution.
- I have explained in class how shadowed instance variables and
overridden instance methods are accessed in the presence of
inheritance. What happens with static variables and static methods?
Write a short program similar to Inheritance1.java to test your idea
and then explain the semantics in less than one paragraph.
- (Open ended) Redo the homeworks using 32-bit words instead of
integers. You should keep the classes Word, Address, Data, etc, but
change their implementation to have a method toBits(). The memory unit
would have to be reorganized as explained in the text: An Invitation to
Computer Science (or any similar book about machine architecture).
- Try to write the Division3.java example without
using exceptions. You must keep the code for the IntArithmetic class
separate from the code of the clients Client1, Client2, and Client3.
(The earlier version of the problem using the Division2.java program has a
trivial solution which I didn't have in mind.)