Exam 4: Final Examination

Distributed: Friday, May 12, 2000
Due: 5 p.m., Friday, May 19, 2000
No extensions!

This page may be found online at http://www.math.grin.edu/~rebelsky/Courses/CS152/2000S/Exams/exam.03.html.

• Useful Files
• Policies
• Problems
  • A. Some Java
    • 1. Exceptional Exceptions
  • B. ADTs and Data Structures
    • 2. A Graph ADT
  • C. Graph Algorithms
    • 3. Dijsktra's Shortest Path Algorithm
    • 5. Cycle Determination

Useful Files

Exceptions

• Exceptional.java

Utilities

• SimpleInput.java
• SimpleOutput.java

Policies

There are four problems on this exam. Each problem is worth twenty-five (25) points. If you answer more than five questions, I will only grade five of my choice. As in past exams, the point value of a question does not necessarily reflect its complexity or length.

This examination is open book, open notes, open mind, open computer, open Web. You may use all reasonable resources. You may not use other people as resources. As always, you are expected to turn in your own work. If you find ideas in a book or on the Web, be sure to cite them appropriately.

This is a take-home examination. It is likely to take you about ten hours. You may use any time or times you deem appropriate to complete the exam, provided you return it to me by the due date. No late exams will be accepted. I will discuss the exam in class when I return it.

Because different students may be taking the exam at different times, you are not permitted to discuss the exam with anyone until after I have returned it. If you must say something about the exam, you are allowed to say ``This is definitely the hardest exam I have ever taken.'' You may also summarize these policies.

Answer all of your questions electronically. That is, you must write all of your answers on the computer and print them out. You should also email me a copy of your exam (a plain text file, please). Put your answers in the same order that the problems appear in.

I will give partial credit for partially correct answers. You ensure the best possible grade for yourself by highlighting your answer and including a clear set of work that you used to derive the answer. In any case, if you include a note about the amount of time spent on each problem or subproblem, I will give you five points of extra credit.

I may not be available at the time you take the exam. If you feel that a question is badly worded or impossible to answer, note the problem you have observed and attempt to reword the question in such a way that it is answerable. If it's a reasonable hour (before 10 p.m. and after 8 a.m.), feel free to try to call me in the office (269-4410) or at home (236-7445).

Some of the questions use or require Java code. If a question requires you to write working code, it will note that explicitly.

I will also reserve time at the start of classes next week to discuss any general questions you have on the exam.

Problems

A. Some Java

1. Exceptional Exceptions

In their attempts to better understand exceptions, Carla and Carl Caffeinated have decided to write a somewhat strange method that they call antiExceptional. Their method calls another method. If the called method throws an exception, their method prints ``Error''. If the called method does not throw an exception, their method throws an exception. (You may recall that we did something similar for the hash table in exam 3.)

Here's what they've come up with.

    public static boolean antiExceptional(SimpleOutput out, 
                                          String[] stuff)
        throws Exception
    {
        try {
            sampleMethod(stuff);
            throw new Exception("That method succeded");
        }
        catch (Exception e) {
            out.println("Failed because: " + e.getMessage());
        }
    } // antiExceptional

Unfortunately, it seems as if their method never throws an exception. If sampleMethod succeeds, antiExceptional prints ``Failed because: That method succeded'', which is not what they wanted.

Update the antiExceptional method so that it throws an exception when sampleMethod succeeds.

B. ADTs and Data Structures

2. A Graph ADT

Herman and Hermione Hacker hate the theoretical topics in computer science studies. They are particularly annoyed that our consideration of graphs never involved the design of an actual ADT, let alone the implementation of one. To help themselves and their colleagues, they've decided to write one. Unfortunately, I've lost it. Hence, I must ask you to write your own. Write a Java interface that for describes a reasonable graph ADT. Note that you interface should include the many methods we use (explicitly and implictly) in our other graph algorithms.

C. Graph Algorithms

3. Dijsktra's Shortest Path Algorithm

Show the steps involved in running Dijkstra's Shortest Path Algorithm on the following graph, using A as the starting node.

                     15
    A-----------------------------------B
    |                                   |
   3|                                   |
    | 1   4   1   9   2   8   2   3   2 |
    C---D---E---F---G---H---I---J---K---L
    |   |   |       |   |       |   |   |
   9|  2|  0|       |   |      1|  1|  7|
    |   |   |       |   |       |   |   |
    +---M---+       |   |       +---N---+
        |      6    |   |     8     |
        +-----------+   +-----------+

5. Cycle Determination

Our suggested algorithm (not yet proven correct or incorrect) for finding the minimum spanning tree was something like the following:

Arrange the edges in order, from smallest to largest
Graph MST = new Graph();
For each edge, e
   if adding e to MST does not create a cycle then
       add e to MST
Return MST

The fictitious alliterative members of our class have decided to break up the tasks associated with implementing this algorithm. As you might guess, Thelma and Theodore Theoretician have been assigned the task of proving the algorithm correct. Hermione and Herman Hacker have chosen to implement the graph data structure. Carla and Carl are stuck implementing the ``does the addition of an edge create a cycle'' algorithm. And yes, they are really stuck. They have no idea how to write such an algorithm.

a. Write an algorithm that determines whether the addition of an edge to a graph creates a cycle.

Now that you've presented them with an algorithm, they wonder whether or not it's an efficient algorithm. Unfortunately, Thelma and Theodore are still too busy working on their proof to help you analyze your own algorithm.

b. Determine the running time of your algorithm using big-O analysis.