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?

Peter: I sit in a cubicle and I update bank software for the 2000 switch.
Joanna: What's that?

public static void tail(String input, String output, int howMany)
{
    // make a queue to hold the last howMany lines read

    // Java 5: LinkedList< String > = new LinkedList< String >();
    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.

// Java 5: public static List< String > pathToList(String path)
public static List pathToList(String path)
{
    // make an empty list to hold the subdirectory names
    
    // Java 5: List< String > = new LinkedList< String >();
    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 a_k, where a_k is defined as follows: a₀ = 2, a₁ = 1, and a_k = a_k-1 + 2 * a_k-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 a(k - 1) + 2 * a(k - 2);
}

Problem 7: Consider the following recursive function.

public int w(int k)
{
  if (k == 0)
    return 2;
  else if (k <= 3)
    return 1;
  else if (w(k - 1) + w(k - 2) + w(k - 3) % 3 == 0)
    return 2;
  else
    return 1;
}

          w(5)
       /    |   \
   w(4)    w(3)    w(2)
 /   |   \
w(3) w(2) w(1)

w(5) and w(7) both return 1.

Problem 8: 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(n²) 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 9: Show the result of running quicksort on an array containing the strings "The", "Air", "Is", "Like", "A", "Butterfly", "With", "Frail", "Blue", "Wings" in that order.

qsort(0, 9)

0	1	2	3	4	5	6	7	8	9
The	Air	Is	Like	A	Butterfly	Frail	Blue	Wings	With

qsort(0, 7)

0	1	2	3	4	5	6	7	8	9
Air	A	Blue	Like	The	Butterfly	Frail	Is	Wings	With

qsort(0, 1)

0	1	2	3	4	5	6	7	8	9
A	Air	Blue	Like	The	Butterfly	Frail	Is	Wings	With

qsort(3, 7)

0	1	2	3	4	5	6	7	8	9
A	Air	Blue	Butterfly	Frail	Is	The	Like	Wings	With

qsort(3, 4)

0	1	2	3	4	5	6	7	8	9
A	Air	Blue	Butterfly	Frail	Is	The	Like	Wings	With

qsort(6, 7)

0	1	2	3	4	5	6	7	8	9
A	Air	Blue	Butterfly	Frail	Is	Like	The	Wings	With

A Air Blue Butterfly Frail Is Like The Wings With

Problem 10: Add a method to the LinkedList202 class called split. split should split the list into two halves. All of the items in the second half of the list should be removed from the original list and returned in the same order in a new list. For example, if l is [1, 5, 9, 3, 4] then l.split() should return the list [3, 4] and l should contain [1, 5, 9] (note that for a list with an odd number of elements, the extra element remains on the original list).

    public LinkedList202 split()
    {
        Node halfway = head;

        // step 1: position halfway where we are going to break the list 

        for (int i = 0; i < (numElements - 1) / 2; i++)
            halfway = halfway.next;

        if (halfway != null)
            {
                // step 2: make the new list (its head/tail will be null)

                LinkedList202 secondHalf = new LinkedList202();

                // step 3: set head for new list

                secondHalf.head = halfway.next;

                // step 4: set tail for new list

                secondHalf.tail = tail;

                // step 5: break link between halfway point and second half

                halfway.next = null;

                // step 6: set new tail for this list

                tail = halfway;

                // step 7: set numElements for the two lists

                int itemsRetained = (numElements + 1) / 2;
                secondHalf.numElements = numElements - itemsRetained;
                numElements = itemsRetained;

                return secondHalf;
            }
        else
            {
                // special case for splitting an empty list
                
                return new LinkedList202();
            }
    }