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.

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. 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.

Exam Directions

Solve and check each of the problems separately.

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.

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.