New to Java? We'll help you get started with our revised beginner's tutorial, or our free online textbook.
|
|
 Get the latest Java books |
|
|
h t t p : / /w w w . j a v a c o f f e e b r e a k . c
o m /
|
||
Programming Exercises
For Chapter 11
THIS PAGE CONTAINS programming exercises based on material from Chapter 11 of this on-line Java textbook. Each exercise has a link to a discussion of one possible solution of that exercise.
Exercise 11.1: The DirectoryList program, given as an example at the end of Section 10.2, will print a list of files in a directory specified by the user. But some of the files in that directory might themselves be directories. And the subdirectories can themselves contain directories. And so on. Write a modified version of DirectoryList that will list all the files in a directory and all its subdirectories, to any level of nesting. You will need a recursive subroutine to do the listing. The subroutine should have a parameter of type File. You will need the constructor from the File class that has the form
public File( File dir, String fileName )
// Constructs the File object representing a file
// named fileName in the directory specified by dir.
Exercise 11.2: Make a new version of the sample program WordList.java, from Section 10.3, that stores words in a binary sort tree instead of in an array.
Exercise 11.3: Suppose that linked lists of integers are made from objects belonging to the class
class ListNode {
int item; // An item in the list.
ListNode next; // Pointer to the next node in the list.
}
Write a subroutine that will make a copy of a list, with the order of the items of the list reversed. The subroutine should have a parameter of type ListNode, and it should return a value of type ListNode. The original list should not be modified.
You should also write a main() routine to test your subroutine.
Exercise 11.4: Section 11.4 explains how to use recursion to print out the items in a binary tree in various orders. That section also notes that a non-recursive subroutine can be used to print the items, provided that a stack or queue is used as an auxiliary data structure. Assuming that a queue is used, here is an algorithm for such a subroutine:
Add the root node to an empty queue
while the queue is not empty:
Get a node from the queue
Print the item in the node
if node.left is not null:
add it to the queue
if node.right is not null:
add it to the queue
Write a subroutine that implements this algorithm, and write a program to test the subroutine. Note that you will need a queue of TreeNodes, so you will need to write a class to represent such queues.
Exercise 11.5: In Section 11.4, I say that "if the [binary sort] tree is created randomly, there is a high probability that the tree is approximately balanced." For this exercise, you will do an experiment to test whether that is true.
The depth of a node in a binary tree is the length of the path from the root of the tree to that node. That is, the root has depth 0, its children have depth 1, its grandchildren have depth 2, and so on. In a balanced tree, all the leaves in the tree are about the same depth. For example, in a perfectly balanced tree with 1023 nodes, all the leaves are at depth 9. In an approximately balanced tree with 1023 nodes, the average depth of all the leaves should be not too much bigger than 9.
On the other hand, even if the tree is approximately balanced, there might be a few leaves that have much larger depth than the average, so we might also want to look at the maximum depth among all the leaves in a tree.
For this exercise, you should create a random binary sort tree with 1023 nodes. The items in the tree can be real numbers, and you can create the tree by generating 1023 random real numbers and inserting them into the tree, using the usual insert() method for binary sort trees. Once you have the tree, you should compute and output the average depth of all the leaves in the tree and the maximum depth of all the leaves. To do this, you will need three recursive subroutines: one to count the leaves, one to find the sum of the depths of all the leaves, and one to find the maximum depth. The latter two subroutines should have an int-valued parameter, depth, that tells how deep in the tree you've gone. When you call the routine recursively, the parameter increases by 1.
Exercise 11.6: The parsing programs in Section 11.5 work with expressions made up of numbers and operators. We can make things a little more interesting by allowing the variable "x" to occur. This would allow expression such as "3*(x-1)*(x+1)", for example. Make a new version of the sample program SimpleParser3.java that can work with such expressions. In your program, the main() routine can't simply print the value of the expression, since the value of the expression now depends on the value of x. Instead, it should print the value of the expression for x=0, x=1, x=2, and x=3.
The original program will have to be modified in several other ways. Currently, the program uses classes ConstNode, BinOpNode, and UnaryMinusNode to represent nodes in an expression tree. Since expressions can now include x, you will need a new class, VariableNode, to represent an occurrence of x in the expression.
In the original program, each of the node classes has an instance method, "double value()", which returns the value of the node. But in your program, the value can depend on x, so you should replace this method with one of the form "double value(double xValue)", where the parameter xValue is the value of x.
Finally, the parsing subroutines in your program will have to take into account the fact that expressions can contain x. There is just one small change in the BNF rules for the expressions: A <factor> is allowed to be the variable x:
<factor> ::= <number> | <x-variable> | "(" <expression> ")"
where <x-variable> can be either a lower case or an upper case "X". This change in the BNF requires a change in the factorTree() subroutine.
Exercise 11.7: This exercise builds on the previous exercise, Exercise 11.6. To understand it, you should have some background in Calculus. The derivative of an expression that involves the variable x can be defined by a few recursive rules:
- The derivative of a constant is 0.
- The derivative of x is 1.
- If A is an expression, let dA be the derivative of A. Then the derivative of -A is -dA.
- If A and B are expressions, let dA be the
derivative of A and let dB be the derivative of B.
Then
- The derivative of A+B is dA+dB.
- The derivative of A-B is dA-dB.
- The derivative of A*B is A*dB + B*dA.
- The derivative of A/B is (B*dA - A*dB) / (B*B).
For this exercise, you should modify your program from the previous exercise so that it can compute the derivative of an expression. You can do this by adding a derivative-computing method to each of the node classes. First, add another abstract method to the ExpNode class:
abstract ExpNode derivative();
Then implement this method in each of the four subclasses of ExpNode. All the information that you need is in the rules given above. In your main program, you should print out the stack operations that define the derivative, instead of the operations for the original expression. Note that the formula that you get for the derivative can be much more complicated than it needs to be. For example, the derivative of 3*x+1 will be computed as (3*1+0*x)+0. This is correct, even though it's kind of ugly.
As an alternative to printing out stack operations, you might want to print the derivative as a fully parenthesized expression. You can do this by adding a printInfix() routine to each node class. The problem of deciding which parentheses can be left out without altering the meaning of the expression is a fairly difficult one, which I don't advise you to attempt.
(There is one curious thing that happens here: If you apply the rules, as given, to an expression tree, the result is no longer a tree, since the same subexpression can occur at multiple points in the derivative. For example, if you build a node to represent B*B by saying "new BinOpNode('*',B,B)", then the left and right children of the new node are actually the same node! This is not allowed in a tree. However, the difference is harmless in this case since, like a tree, the structure that you get has no loops in it. Loops, on the other hand, would be a disaster in most of the recursive subroutines that we have written to process trees, since it would lead to infinite recursion.)