Problem Set 2. Posted 1/25

1. To the myGraph class add a method called listTriangles. This method takes no parameters and returns a collection of all triangles in the graph. A triangle is a set of three distinct vertices x, y, and z such that {x, y}, {y, z}, and {x, z} are all edges in the graph. The collection should be returned in a 2-dimensional array. The number of rows in the array should be exactly equal to the number of triangles found in the graph. The array should have three columns. Thus, each triangle can be stored in the three slots in a row. Each slot of the array should be of type String so as to store the name of a vertex.

   What to submit: Use the submit tool to electronically submit a single java file: myGraph.java. Here are instructions for using the submit tool.

2. Suppose that we use the myGraph class to build a graph. We start with an empty graph and first add vertices in the order: a, b, c, d, e, f. Then we add edges in the order {a, b}, {b, c}, {a, d}, {a, f}, {c, f}, {d, e}, {d, f}. After all of these additions show the contents of the four data members of the myGraph class: names, Edges, numVertices, and numVertices. Make sure you follow the code in the myGraph class carefully and show the contents of the variables exactly. Make sure you pay attention to how the arrays are resized.

3. Consider an m by n matrix of real numbers. Such a matrix is called sparse if most of the entries in the matrix are zeroes. Sparse matrices are quite common in many engineering applications. One can reduce the amount of memory it takes to store a sparse matrix by just keeping track of the non-zero entries. For example, suppose we have a 100 by 500 matrix of reals with the rows labeled 0, 1,...,99 and the columns labeled 0, 1,...,499. Now suppose that the only nonzeroes in the matrix are in positions (0, 5), (1, 10), and (25, 50). Then, rather than store the entire 100 by 500 matrix, it makes sense to just store the three positions and the corresponding nonzeroes. Write a function called compress that takes a matrix of real numbers and returns an object that stores only the positions and values of nonzeroes. You may have to design and implement an appropriate class (maybe, called sparseMatrix) for this purpose.

   ---