CSci 2101 Data Structures: Problem set 5

Due Wednesday, Dec. 15th at 8pm.

Problem 1: Counting Sort (12 points)

Counting sort is an algorithm for sorting elements with integers keys, where all keys are in a known interval. The algorithm is described in CLRS Section 8.2 (pp. 168). For this problem we assume that the keys are integers from 1 to 20 (inclusive) and two elements may have the same key value.

We assume that objects sorted by the algorithm implement the following abstract class KeyOneTwenty:


public abstract class KeyOneTwenty {

    // public method that returns a key only if
    // it's between 1 and 20
    public final int Key() {
	int key = _Key();
	if (key < 1 || key > 20) {
	    System.out.println("invalid key " + key);
	    System.exit(0);
	}
	return key;
    }

    // private class-specific method
    protected abstract int _Key();
}
Your task is to implement the counting sort algorithm as a method

public static void countingSort(KeyOneTwenty [] items)
You also need to write a class StringKey which extends KeyOneTwenty. The class has one private variable str of type String. The _Key() method of the class should return the length of the string.

Test your counting sort algorithm by creating an array of StringKeys in main and calling the method countingSort on that array.

Problem 2. AVL Trees (15 points)

Fill in the missing code in this implementation of AVL trees. Make sure to test it well and submit all your test cases. Print out the tree in in-order and pre-order to see the positions of all elements. Explain the results of the tests and show that the tree is indeed an AVL tree after each insert. You may submit this part of the problem on paper (draw the resulting tree after each insert).

Problem 3: Adding exceptions to Counting Sort (6 points)

Modify your counting sort solution as follows:

Problem 4: Adjacency matrix implementation of a graph (15 points)

In this program you have to write an implementation of a graph using an adjacency matrix. Your implementation must work exactly the same way as the adjacency list implementation that we did in class (i.e. if I replace the class Graph by your implementation, the output of the program must be exactly the same). You need to implement Breadth-First Traversal (BFT) and Depth-First Traversal (DFT) on your graph. You also need to compare the running time of BFT and, separately, DFT for the two implementations.

More specifically, you need to do the following:

  1. Replace the array of vertices in the Graph class by a two-dimensional array of integers to represent the edges. You will NOT need the classes Vertex and VertexNode in your implementation at all, Graph is the only class in this implementation.
  2. Change all the methods of the new Graph class to work with the new data representation. Do not change any of the method parameters or the types of return values.

    You should start by commenting out the old method code, put some dummy return values for all non-void methods, such as an empty string for toString(), and make sure that the program compiles and runs. Then start writing code for the methods one by one, compile and test often.

  3. Test your code for an undirected and a directed graph.
  4. Compare the two implementations on random graphs of 1000 vertices and 10000 edges:

This is a problem set from CSci 2101 course.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.