CSC 495-001, Spring 2020 Programming Assignment 1 page 1 of 3 Due: Tuesday, February 18, at 11:00 PM Purpose. This assignment has several objectives. 1. You will carry out computational experiments and document their results. 2. You will develop data structures to support graph algorithms and heuristics. 3. You will develop/use infrastructure for running and documenting experiments, including techniques for reporting runtime, solution quality, and other statistics, putting these in spreadsheets, and creating charts. 4. You will (use scripts to) generate random problem instances to assess effective- ness of algorithms and heuristics. Heuristics for Vertex Cover There are several different greedy heuristics for the vertex cover problem. Among them are the following. • Max-degree. Repeat the following until all edges are covered (all vertices have current degree 0): (i) pick a vertex v of largest (current) degree and add it to the cover; and (ii) decrement the current degree of each of v’s neighbors. • Min-degree. Repeat the following until all edges are covered: (i) pick a vertex v of minimum current degree; and (ii) for each neighbor w of v, add w to the cover and decrement the current degree of each of w’s neighbors. • 2-Approx. Repeat the following until all edges are covered: (i) pick an edge vw that maximizes d(v) + d(w), where d(x) is the current degree of vertex x; (ii) add both v and w to the cover and decrement the current degree of each of their neighbors. This is actually an approximation algorithm with guaranteed worst case ratio of 2. Implement each of these heuristics in a language of your choice. Your program(s) should take a graph in snap format (described below under Input format) as input and report the following in a format described below (under Output format). • filename – name of the file describing the graph • vertices – number of vertices • edges – number of edges • heuristic – name of the heuristic used • value – the number of vertices in the cover • runtime – execution time in milliseconds (integer value) • iterations – number of repetitions • solution – the cover as a list of vertex numbers, one per line Note: Instead of three separate programs, you can also write a single program with a command-line option that selects the heuristic – as long as this is clearly documented. CSC 495-001, Spring 2020 Programming Assignment 1 page 2 Input Format A snap file consists of comment lines – lines in which the first character is a # followed by whitespace, and lines containing two integers separated by whitespace. A line with two integers gives the endpoints of an edge in the graph. You may assume that each edge appears exactly once – since the graph is undirected you will not see the same two integers on the same line again, even in reverse order. A small example of a snap file is # This graph is a triangle, # a cycle with three vertices and three edges. 1 2 1 3 2 3 Output Format When you debug your programs and even when you are running them in “production mode” you will want to print a variety of information. Anything that is not part of the specifications detailed below should be printed to stderr instead of stdout. Output for each run should consist of the first five of the six fields listed earlier, one per line, and each line containing the name of the field, followed by whitespace (a tab makes the output easy to read and it is useful to have a standard format for numerical fields so that numbers line up). The solution will consist of multiple lines, each tagged with a c followed by a dash (-). For example, filename bigfile.snap vertices 15491 edges 917028 heuristic Max-degree value 10569 runtime 1576 iterations 10569 c- 7 … c- 10017 Scripts will be provided to • run your programs on all files in a given directory, producing a single output file; • create a csv file from that output; • verify that the vertex cover produced by running one of your programs on a single file is valid. You may find it convenient to suppress output of the solutions when running on a large number of larger instances. Consider adding a command-line option that accomplishes this, e.g., -q or –quiet. CSC 495-001, Spring 2020 Programming Assignment 1 page 3 Problem Instances I will provide both a collection of problem instances and some scripts that generate instances of various kinds. For the provided instances, I will provide a spreadsheet giving their optimal solutions so that you can assess the approximation ratios achieved by them. Report You are expected to write a short report that addresses the following issues. • The challenges you faced when implementing each heuristic and how you overcame them (data structures used, for example). • The relative performance of the heuristics on the instances I provided and a col- lection of instances generated using my scripts. Were there any major differences? • Characteristics of problem instances that might lead one heuristic to perform better than the others. For the last point, I will provide a script that analyzes graphs in a given directory and reports information about their degree distribution. Grading Your grade on this assignment will be based on the following criteria. This is only an approximation. Since the class is small, there will be lots of room for “negotiation”. 60% compilation and execution do your heuristics compile, run, and produce valid results 10% compilation/execution instructions is it easy for me to figure out how to run your program(s) 10% style and comments is your code readable; is it easy to figure out the purpose of each method/function and how you imple- mented and used data structures;a is the source code itself readable (even without the comments) 10% self documentation will your programs print easily un- derstandable usage messages if I try to run them without supplying any command-line arguments or if there are errors in the command line 10% the report do you do a good job of describing your observations aSome of this information should be included in your report.
