HW#3 --- last modified March 26 2019 00:03:48.Due date: Apr 8 Files to be submitted: Purpose: To gain experience with distributed algorithms Related Course Outcomes: The main course outcomes covered by this assignment are: CLO2 -- Analyze or code a parallel algorithm using a thread library CLO3 -- Analyze or code a parallel algorithm using a library such as OpenCL CLO4 -- Analyze the correctness and run time of a distributed algorithm Specification: This homework will consist of two parts, a written part and a coding part. Both parts will be submitted in the Hw3.zip file. The written part should be in a file Hw3.pdf. For the written part of the homework you should write solutions for the following questions. In what you turn in, make sure to write the names and student ids for each group member. For each problem, first copy and paste the question, then write your solution to it beneath it.
A triangle independent set is a set of vertices in a graph none of which share a triangle. Let MTIS (maximal triangle independent set) be the problem of finding a largest set of vertices in a graph none of which share a triangle. Modify our ParallelMIS algorithm so that it instead computes maximal triangle independent sets. Redo the arguments from class as part of your HW3 write-up to show your algorithm has similar properties as the ParallelMIS algorithm. For the coding part of the assignment I would like to code your Parallel MTIS algorithm using Java threads. Your program will be tested from the command line as follows: javac ParallelMTIS.java java ParallelMTIS graph_fileHere graph_file will be a file containing the adjacency matrix of a graph you want to find a maximal triangle independent set for. This will be written as a series of rows of 1's and 0's separated by spaces, `(i,j)` is `1` if there is an edge shared by `i` and `j`. As the graph is undirected it is symmetric. For example, the graph, in this lecture slide would be expressed as (I substracted 1 off each vertex name): 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 1 1 0 1 0 0 0 0 1 0 On such an input your program should output a maximal triangle independent set. For example, on the above input it outputs: 0 1 2 3 4 5 In this case here, the original graph did not have triangles, so all vertices are output. Each vertex in the independent set is listed on its own line from least to greatest. Again, I substracted 1 off each vertex names I used on the slide. In general, not all vertices in the original graph would be output. For example, consider the case of two triangle with vertices 0,1,2 and 2,3,4 respectively. I.e., they share vertex 2. Then possible maximal triangle sets are: 0,3 or 0,4 or 1,3 or 1,4 or 2. Point Breakdown
|