CSSE 230
Data Structures and Algorithm Analysis

Written Assignment 6

To Be Turned In

Except where noted, these are to be turned in as hard copy. You can write solutions out by hand, or write them on your computer and print them.

Papers must not have ragged, spiral-notebook edges. Multiple page solutions must be stapled. Solutions not following these guidelines will be returned ungraded. I regret this rigidity, but it is necessary given the number of students in CSSE 230 this term.

Late days may not be used for written assignments.

  1. (5 points) Problem 6.22. You do not have to do this on the computer, but you may. You must turn in a hard copy of your code. You will (probably) need to refer to the Javadoc documentation of java.util.Map to complete this problem.

  2. (30 points) Complete the non-attacking queens problem as discussed in class during Session 16. The template code for this project is in your individual SVN repository as the Queens project. There are three methods for you to implement, all in RealQueen and all indicated by TODO comments.

    You will probably need to study the javadocs of Queen and RealQueen to solve this problem.

    Two forms of test code are provided. The Main class includes a main method that you can use while working on your solution and debugging. The MainTest class contains unit tests that we will use to check your solution. You must pass the unit tests to earn the correctness points for this problem.

    Be sure to commit your solution to SVN for grading.

  3. (20 points) For this task you’ll add four more methods to the Threaded Binary Search Tree project. Check out the new template code given in ThreadedTree2 in your individual SVN repository. (Because of the extended deadline on the original Threaded assignment, the template code for this one will not be available until Wednesday of week 6.)

    The methods you are to write are the last two methods in ThreadedBinaryNode and the last two in ThreadedBinarySearchTree. Near the end of ThreadedBinarySearchTree, you’ll find a couple of new methods that illustrate the use of the methods you will write. The code in the JUnit tests in ThreadedTree2Test.java should also help you to understand how your methods should work.

    Your code, which you should commit to your repository, should pass all of the unit tests in ThreadedTree2Test.java, plus the other unit tests that are already passed by the template code. That is, don’t break the existing code while adding your code. In Eclipse 3.4, you can right-click a project to run all the JUnit tests in the entire project. That’s how we’ll test your solution.

  4. (30 points) Consider the following directed graph:

    1. (5) Show the first three rows of an adjacency matrix for this graph. Label the rows and columns.
    2. (5) Show an adjacency list representation of this graph.
    3. (5) Show an edge list representation of this graph.
    4. (15) Which of the above representation will use the least space? Support your answer with calculations. Be explicit about your assumptions concerning details of the representations.