15-111/200 Final Exam
Information Page

Brief Overview

This exam counts as 20% of your final grade. You have 3 hours to work on it. It consists of three parts.

• Part 1 covers Linked Lists (LL): it is worth 6 points (with no partial credit).
• Part 2 covers Binary Search Trees (BST): it is worth 6 points (with no partial credit).
• Part 3 covers standard Java Collection Classes (CC): it is worth 8 points
  (each of its two outputs are worth 4 points).

The Provided Classes

The Linked List and Binary Search Tree questions use the following classes respectively. Each of these classes contains a nested class that defines the node used by the class.

• LL.java
• BST.java

The Collection Class question uses the standard Java collection classes.

You may examine the Javadoc for all of the classes provided in this exam.

Question Pools

The pool of Linked List and Binary Search Tree questions are public: all students will be randomly assigned one question from each pool on their exam. The pool of Collection Class questions is private: all students in a session will solve the same problem, which will not be made public before the exam starts.

• Linked List Question Pool
• Binary Search Tree Question Pool
• The Collection Class Overview

Exam Directions

Solve and check each of the problems separately.

• Linked List: You are provided with the minimal Linked List classes specified above. You are also provided a class that extends this implementation using inheritence, in which to write one method; the ExtendedLL class contains the skeleton for this method. You should complete this method. Each extended class also contains a driver program to test it. You are also provided the same test data and output that will be used to grade your solution. Your solution should generate exactly the same output for each input; check each carefully

• Binary Search Tree: You are provided with the minimal Binary Search Tree classes specified above. You are also provided a class that extends this implementation using inheritence, in which to write one method; the ExtendedBST class contains the skeleton for this method. You should complete this method. Each extended class also contains a driver program to test it. You are also provided the same test data and output that will be used to grade your solution. Your solution should generate exactly the same output for each input; check each carefully.

• Collection Class: You are provided with a file in which to write your program. You are also provided the same test data and output that will be used to grade your solution. You must not change any of the test data files: your program must read them in the form that they are written. Your solutions should generate exactly the same output shown for each input file shown.

Please be aware that although special cases not present in our input files will not be graded, your solution must be algorithmically correct for the common case to receive credit. Solutions should not trivialize the problem, nor should they use unnecessary intermediate data structures.

For example, solutions that generate output by hard-coding for exactly the test cases, will not receive credit, nor will solutions that operate by parsing toString() output or copying the whole of the Linked List or Binary Search Tree data into an array, Vector, or other collection.

Sample Exam

The following sample exam is provided to familiarize you with the exam infrastructure. It includes the directory tree, test drivers, menu program, and test data for all three parts.

• Eclipse exam.zip (zip archive)
• exam (browsable directory)

Please understand that the information in this handout is designed to familiarize you with the exam environment. It is not an actual exam. The test data, for example, may be less rigorous than we might offer during an actual exam.

Running Test Drivers: Metrowerks/Command Line

Test drivers are provided to assist you with running all the program. To run them, use Metrowerks in the standard way. You do not have to read/understand the material below.

If you want to use use Java via the command line, use the following commands (issued from the LL, BST, or CC directories respectively).

  javac -classpath ../introExam/cs151xx.library.jar ../introExam/LinkedList/*.java *.java
  javac -classpath ../introExam/cs151xx.library.jar ../introExam/BinarySearchTree/*.java *.java
  javac -classpath ../introExam/cs151xx.library.jar ../introExam/*.java *.java

And the following command to run all three programs on the Mac

  java -cp ../introExam/cs151xx.library.jar:.:.. Test

On the PC, you use the following command instead (replacing the colons by semicolons).

  java -cp ../introExam/cs151xx.library.jar;.;.. Test

It is easiest to just COPY these commands from this document and PASTE them into your console window, when you want to compile/run your program.

Status

This page, and the exam, itself, are under development. Please advise your instructor of any opportunities for improvement, including but not limited to omissions, ambiguities, errors, &c.

Revision history:

• Not yet revised since initial posting.