Problem 1: Assume that the given class definitions are in the appropriate files. There are 16 statements below the comment in main, which is in the SubC class. Some of those 16 statements are illegal. Cross out the illegal statements and indicate whether they cause a compiler error or a runtime error.. Give the output of the remaining statements (ignore the effects of any illegal statements). Some legal statements may produce no output.
abstract public class Super {
abstract public void kick();
public void pass() {System.out.println("Super.pass");}
private void tackle() {System.out.println("Super.tackle");}
}
public class SubA extends Super {
public void kick() {System.out.println("SubA.kick");}
public void pass() {System.out.println("SubA.pass");}
public void punt() {System.out.println("SubA.punt");}
}
public class SubB extends Super {
public void kick() {System.out.println("SubB.kick");}
public void punt() {System.out.println("SubB.punt");}
}
public class SubC extends SubA {
public void kick() {System.out.println("SubC.kick"); super.kick();}
public static void main(String[] args) {
SubA one = new SubA();
SubB two = new SubB();
Super three = new SubC();
// Some of these statements may cause errors at compile- or run- time.
one.kick();
one.pass();
one.punt();
one.tackle(); // tackle is private
two.kick();
two.pass();
two.punt();
two.tackle(); // still private
three.kick();
three.pass();
three.punt(); // three declared as Super; punt not declared in Super
three.tackle(); // funny how some things don't change
SubA four = (SubA)two; // no ancestor/descendant relationship
SubA five = (SubA)three;
three = new Super(); // Super is abstract
two = three; //
three = one;
three.pass();
}
}
All of the errors were compiler errors. The output is given below.
SubA.kick
SubA.pass
SubA.punt
SubB.kick
Super.pass
SubB.punt
SubC.kick
SubA.kick
SubA.pass
SubA.pass
Problem 2:
Write an applet that has two text fields and a button. One of the text
fields is used for user input. The other is used to display the
total of the numbers the user has entered. The total starts at zero and
is updated each time the user clicks the button. The applet should display an
error message if the user enters a non-numeric value.
import javax.swing.*;
import java.awt.event.*;
import java.awt.*;
public class AddingMachine extends JApplet implements ActionListener
{
private JTextField inputField;
private JTextField outputField;
private JLabel statusLabel;
private double total = 0.0;
public void init()
{
// make a panel to hold the text fields
JPanel textPanel = new JPanel(new GridLayout(2, 2));
inputField = new JTextField();
textPanel.add(new Label("Input:"));
textPanel.add(inputField);
outputField = new JTextField("0.0");
outputField.setEditable(false);
textPanel.add(new Label("Total:"));
textPanel.add(outputField);
// make a panel to hold the button and status
JPanel bottomPanel = new JPanel(new BorderLayout());
// put the button in another panel so it won't get stretched
JPanel buttonPanel = new JPanel();
JButton addButton = new JButton("Add");
addButton.addActionListener(this);
buttonPanel.add(addButton);
statusLabel = new JLabel(" ");
bottomPanel.add(buttonPanel, BorderLayout.CENTER);
bottomPanel.add(statusLabel, BorderLayout.SOUTH);
// put the panels in the applet
getContentPane().setLayout(new BorderLayout());
getContentPane().add(textPanel, BorderLayout.CENTER);
getContentPane().add(bottomPanel, BorderLayout.SOUTH);
}
public void actionPerformed(ActionEvent e)
{
try
{
// read user input and add to total
total += Double.parseDouble(inputField.getText());
// display new total
outputField.setText(String.valueOf(total));
// clear any error message
statusLabel.setText(" ");
}
catch (NumberFormatException ex)
{
statusLabel.setText("Please enter a number");
}
}
}
Problem 3: Write a method called tail that takes three arguments: the name an input file, the name of an output file, and the number of lines to copy from the end of the input file to the output file. For example, if the input file contains
Joanna: So where do you work, uh, Peter? Peter: Initech Joanna: And, uh, what do you do there? Peter: I sit in a cubicle and I update bank software for the 2000 switch. Joanna: What's that?and the last argument was 2 then the output file should contain
Peter: I sit in a cubicle and I update bank software for the 2000 switch. Joanna: What's that?One way to do this without creating a list to hold the entire file is to use a queue. As you read lines from the input file, put them on back of the queue. If the queue is then bigger than the number of lines required, remove a line from the front of the queue. Once the end of the file has been reached, the method could output each line in the queue.
public static void tail(String input, String output, int howMany)
{
// make a queue to hold the last howMany lines read
LinkedList q = new LinkedList();
try
{
// open the input file
BufferedReader infile
= new BufferedReader(new FileReader(input));
// read to end of file
String line;
while ((line = infile.readLine()) != null)
{
// save line in last howMany read
q.addLast(line);
// remove line read howMany+1 ago
if (q.size() > howMany)
q.removeFirst();
}
}
catch (IOException e)
{
System.err.println("Error reading " + input);
}
try
{
// open the output file
PrintWriter outfile = new PrintWriter(new FileWriter(output));
// output all strings on the queue
while (q.size() > 0)
outfile.println(q.removeFirst());
// close the output file
outfile.close();
}
catch (IOException e)
{
System.err.println("Error writing " + output);
}
}
Problem 4: Write a method that takes as its parameter a string containing a Windows path and file name, for example "C:\Documents and Settings\All Users\Desktop\Calendar.java". The method should output, using System.out.println, all of the subdirectories in the path. For the above example the output should be three strings
Documents and Settings All Users Desktop
public static void pathToList(String path)
{
// break path up based on backslash (\\ stands for a single backslash)
StringTokenizer tok = new StringTokenizer(path, "\\");
// throw away drive specification
if (tok.hasMoreTokens())
tok.nextToken();
// go through the rest of the tokens, remembering the previous one
String last = null;
while (tok.hasMoreTokens())
{
// save the previous token on the list
if (last != null)
System.out.println(last);
last = tok.nextToken();
}
// since the last token (the filename) is no other token's previous
// token, it has not been saved
return result;
}
Problem 5:
Redo problem 2, but return the subdirectory names in a List object
instead of printing them to the screen.
public static List pathToList(String path)
{
// make an empty list to hold the subdirectory names
List result = new LinkedList();
// break path up based on backslash (\\ stands for a single backslash)
StringTokenizer tok = new StringTokenizer(path, "\\");
// throw away drive specification
if (tok.hasMoreTokens())
tok.nextToken();
// go through the rest of the tokens, remembering the previous one
String last = null;
while (tok.hasMoreTokens())
{
// save the previous token on the list
if (last != null)
result.add(last);
last = tok.nextToken();
}
// since the last token (the filename) is no other token's previous
// token, it has not been saved
return result;
}
Problem 6:
Write a recursive method that computes ak, where
ak is defined as follows:
a0 = 2,
a1 = 1, and
ak = 2ak-1 + ak-2
for k > 1.
public static int a(int k)
{
if (k < 0)
throw new IllegalArgumentException();
else if (k == 0)
return 2;
else if (k == 1)
return 1;
else
return 2 * a(k - 1) + a(k - 2);
}
Problem 7: Consider the following recursive function (taken from the solutions for the last practice set).
public int w(int k)
{
if (w == 0)
return 2;
else if (w <= 3)
return 1;
else if (w(k - 1) == 1 && w(k - 2) == 1 && w(k - 3) == 1)
return 2;
else
return 1;
}
Draw the recursion tree for the call w(5). What value does
w(5) return? What value does w(7) return?
w(5)
/ | \
w(4) w(3) w(2)
/ | \
w(3) w(2) w(1)
w(5) and w(7) both return 1.
Problem 8:
Write a recursive function that takes as its parameter a Node in
a binary search tree and returns the height of the subtree starting at that
node, where the height is defined to be the number of nodes on the path
to the deepest leaf, so an empty tree has height 0 and a tree with only
one node has height 1. (Hint: the height of the subtree starting at a node
is one more than the taller of the two trees starting at its children.)
public int height(Node n)
{
if (n == null)
return 0;
else
return 1 + Math.max(height(n.left), height(n.right));
}
or, for a more object-oriented approach, add the following to the
Node inner class (so we would call n.height() instead
of height(n)):
public int height()
{
if (left == null && right == null)
return 1;
else if (left == null)
return 1 + right.height();
else if (right == null)
return 1 + left.height();
else
return 1 + Math.max(left.height(), right.height());
}
Problem 9: The following code displays all the items on a List called l. What is the big-Oh running time if the list is an ArrayList? What if the list is a LinkedList?
for (int i = 0; i < l.size(); i++) System.out.println(l.get(i));
For a linked list, get takes O(n) time; there are O(n) calls to get, so O(n * n) = O(n2) time total. For an array-based list, each get takes O(1) time, and the number of calls is still O(n), so O(1 * n) = O(n) time total.
Problem 10: Modify the existing code for TreeSet202 so that each Node has a reference to its parent in addition to its children (the root's parent should be null). Show the additions to the Node class definition and the add method.
We add a field to the inner class and allow that field to be initialized via the constructor:
private static class Node
{
Comparable data;
Node left, right, parent;
private Node(Comparable d, Node p)
{
data = d;
parent = p;
}
}
We also add code to add so each new node knows where its parent
is:
public boolean add(Object o)
{
Comparable toAdd = (Comparable)o;
Pair position = find(toAdd);
if (position.child != null)
{
// already in the set
return false;
}
else
{
if (position.parent == null)
{
// adding 1st node
root = new Node(toAdd, null);
}
else if (position.parent.data.compareTo(toAdd) > 0)
{
// adding left child
position.parent.left = new Node(toAdd, position.parent);
}
else
{
// adding right child
position.parent.right = new Node(toAdd, position.parent);
}
numNodes++;
return true;
}
}
Problem 11: Write a method that takes a node as a parameter and determines if that node is the right or left child of its parent using the parent reference added in problem 8. The method should return -1 if the node is a left child, 1 if it is a right child, and 0 if the node is the root.
public boolean whichChild(Node n)
{
if (n.parent == null)
return 0;
else if (n.parent.left == n)
return -1;
else
return 1;
}
or, thinking of this from an object-oriented point of view and writing a
method in the Node class instead of a method that takes a
Node as an argument:
public boolean whichChild()
{
if (parent == null)
return 0;
else if (parent.left == this)
return -1;
else
return 1;
}
Problem 12: Show the result of adding the strings "Twas", "The", "Night", "Before", "Christmas", "And", "All", "Through", "House", "Not", "A", "Creature", "Was", "Stirring" to a binary search tree in that order.
Problem 13: Put the strings from the previous problem in an array in sorted order. Which strings are compared when doing a binary search for "Christmas", "Was", and "Not"?
0
1
2
3
4
5
6
7
8
9
10
11
12
13
A
All
And
Before
Christmas
Creature
House
Night
Not
Stirring
The
Through
Twas
Was