*

Problem Set 8

Due: 9 November.

Write the code for the following problem. Turn your solution into the class server in the ps8 folder. You must follow all of the programming guidlines given in the Program Format Guide .

  1. Do problem 28 on page 599 of Sahni. This problem asks you to create a solution, in Java, for the crossing distribution problem using a indexed binary search tree. You may use the crossing distribution solution that is given in the book (it's the CrossingDistribution.java file in the Applications folder of the book code) and the indexed binary search tree that is also given in the book (it is also in the book code directory; look for the file IndexedBinarySearchTree.java in the directory dataStructures).

    The iBST is used in two places. It is used in place of the linear list in the crossing distribution solution. If you look at the code on page 595 (Program 15.13), you'll notice that there are 4 data structures used in the program. The first declaration is for a variable named list that is of type ArrayLinearList. The type of list will change to be an indexed binary search tree. The remaining three variables will continue to be arrays. In this case, you should not have to change the code for the indexed binary search tree. You will have to change some of the method calls that list made since the methods used in the indexed binary search tree are different than the methods used in the ArrayLinearList class.

    If you look at the crossing distribution solution provided by Sahni, you'll note that he hardcodes in the "C" array (the crossing distribution) and the "k" array (the crossing table). You will have to provide for input of the "C" array from a file and will have to create the "k" array.

    This presents your second, and more interesting, challenge: creating the k array (the crossings table). You must also use an indexed binary search tree to create this array. The technique is described in some detail on page 597 of your text book and is covered in greater detail in the lecture slides in the powerpoint file lect12-01.ppt (available on the class web page).

    Unfortunately, the basic code for the indexed binary search tree must be modified to make the algorithm for finding the crossing table work. In particular, the entry for the k-table for some index i is calculated by adding up the leftSize values for every node whose right child is visited. The code provided by Sahni does not return this value (since you would normally not need to access it if you're using an iBST). Thus, you'll have to modify the code to make it work. There are several approaches to this modification, two of which are:

    1. subclass the IndexedBinarySearchTree class and override the getDataElement method so that you also receive the sum of the appropriate leftSize values.

    2. subclass the IndexedBinarySearchTree class and create a new method that will find an index and return the sum of the appropriate leftSize values.

    The last problem is that the algorithm given in the book (Program 15.13 on page 595) uses a linear list. In particular, it uses the add function of the linear list, which places an element into the list at a specified index and moves other indices down. The iBST does not provide this method. In fact, when you add an element at a specific index to an iBST, if there is already an element at that index, the old element will be replaced by the new element. You will have to either modify the iBST to move elements down (if an element is already at that index) or will have to remove an element (if the index already exists), add the new element, and then add the old element.

  2. You must have a driver program that initializes a crossing problem and tests your solution.

  3. You must supply a test file that provides statement coverage. This file should supply the number of pins and the permutation array C. Your output must be the pins, the permutation array A that gives the connections in the top half of the channel, the permutation array B that gives the connections of the pins in A to the bottom pins and the array C.

  4. On the due date you must hand in a written analysis of your programs running time. You must include an analysis of every operation.
Return to John Barr's Home Page

Last Modified: 27 October 2001

THIS PAGE MAINTAINED BY: John Barr, Ithaca College