CSC 425/520: Class Project: Submission 1

CSC 425/520 Class Project: Submission 1
Due Friday Nov. 11, 2016
Late submissions accepted (with late penalty) until Tuesday Nov. 15.

The goal of this class project is to investigate and evaluate heuristic algorithms for the minimum dominating set problem. The aim of the first submission is to ensure that the code is correct and meets the specifications. Your new heuristics will be evaluated more thoroughly for the quality of their solutions at the end of term.

Command line parameters

Your program has two command line parameters:

Usage: dom.exe <maximum number of seconds per graph> <verbose>

The first parameter gives a time limit in seconds for the maximum time that the heuristic should run on each graph. Verbose is either 0 or 1 and specifies the type of output desired (described below).

Input

The input is in the same format as for assignment #2. The input should come from standard input.

Output

If verbose is true, for each graph a certificate is printed which is in the same format as the output for assignment #2. If verbose is false, then for each graph print 

graphNumber     n    k

where graphNumber is the number of the graph (numbering starts at 1), n is the number of vertices of the graph, and k is the minimum size of a dominating set that your heuristic finds.

The output should go to standard output.

To make sure your code compiles and runs properly

Use
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/times.h>
This ensures that the programs will run using any compiler or machine. Some compilers include these automatically. Others do not and programs without them do not compile.

Use a constant NMAX set to 2187 for the maximum number of vertices:
#define NMAX 2187
If NMAX is not big enough, print an error message that explains that the user should increase NMAX and recompile. Do not use dynamic memory allocation (for example malloc/free). Using repeated malloc/free calls will end up slowing the program down and could create bugs that cause memory leaks. Memory leaks are a disaster when you are working with large computations.

It is very important that your program works when I try to run it on more than one graph at a time. As part of our research efforts we want to be able to find a minimum dominating set on potentially thousands of graphs and so it is essential to have programs that work on more than one input.

Resources Provided

The files in dom_set_heuristics.zip that you can download from the connex resources will help you a lot with this project. It contains:

  1. Code snippets that can help you generate random permutations of an array of integers and that can show you how to limit the time of your approach to the maximum number of seconds allowed.
  2. Input graphs for testing. There is information provided regarding the smallest known dominating set for each problem, and command files to help you run and summarize the results.
There is more information about this in the README.txt files.

Submissions

I have three (four for CSC 520) places for you to submit three algorithms on connex. The first two algorithms are very simple approaches based on your assignment #2 algorithm. We are using them as a basis of comparison so we can see when your new creative algorithms are performing well.

Algorithm #1: Random vertex order greedy

  1. Choose a random permutation p of 0 to n-1.
  2. Run the algorithm from assignment #2 with these changes: At a given level, choose u= p[level] to be the vertex that is first colored blue then colored red.
  3. The algorithm terminates as soon as you find the first small dominating set.

Algorithm #2: Random BFS-order greedy

  1. Randomly select a vertex r to be the root for BFS.
  2. Perform a BFS starting at r. When you visit the neighbours of a vertex, choose a random permutation of the neighbours to be the order in which the neighbours are visited.
  3. Use the algorithm from assignment #2 but at a given level, chose u= queue[level] to be the vertex that you try blue then red (queue is from the BFS).
  4. The algorithm terminates as soon as you find the first small dominating set.

For algorithms 1 and 2, do repeated random trials until you run out of time.

Algorithm 3: Your own creation

Do whatever you like to try and beat the performance of algorithms 1 and 2. If you discover a smaller dominating set than the minimum known for one of the open problems, be sure to let me know. The known results are summarized in the file known_results.txt that is included with the files I am giving you for the assignment.

Your programs should be called respectively LastName_k.c or LastName_k.cpp where k is the algorithm number. For example, my three programs would be Myrvold_1.c, Myrvold_2.c and Myrvold_3.c. For last name Yang, please also use your first initial: YangA_1.c or YangN_1.c for example.

Algorithm 4: CSC 520 only, submission is optional, a published heuristic

CSC 520 students will eventually implement some published heuristic. If you submit an approach, then I will check it along with the other heuristics. You will not lose any marks if you wait and submit it later.

Technical Issues

I had to use
limit stacksize unlimited
on my Linux machine to have enough space for the big problems. You only need to type this once per session. On other machines, you might type something like:
ulimit -s unlimited
Try asking me or the consultants or use google to find out how to do this on your machine.

Stopping the algorithms after a time limit

Unfortunately, the
#include <sys/types.h>
is not available on Windows machines. Two things you can do instead to develop and test your programs:
  1. Use one of the Linux machines provided by the computer science department either by going to a lab or by logging into it using a remote login protocol such as putty. The labs page has more information about access to Linux machines available to students. For remote login information look under Application Services and click on Unix Login Servers. For information about labs with machines, look under ECS Computing Facilities and click on UNIX Labs.

    To get putty:
    putty: http://www.chiark.greenend.org.uk/~sgtatham/putty/download.html

  2. Cygwin provides a large collection of GNU and Open Source tools that give functionality similar to Linux on Windows. You can use the C compiler gcc, or the C++ compiler g++. The code I have given you for timing works with both gcc and g++ on cygwin. Cygwin also optionally includes programs such as a Java compiler and LaTeX (used for preparing theses, and conference/journal submissions). I personally find this the most convenient way to program on a Windows machine.

Policy on Copying

All code submitted must be your original work except for the code I have given you permission to use. You may use the sampel code I have provided on connex and if you do, I think it will help you a lot in developing your programs. If you use my sample code, include an acknowledgement in your program. If you use code taken from the internet, an API, other students, previous model solutions or other sources and submit it as your own work you will not get credit for that code. Further if your source is not acknowledged, you are subject to disciplinary action according to the department policies for plagiarism.

CSC 425/520 Project submissions/ maintained by Wendy Myrvold / wendym@cs.UVic.ca / revised Halloween, 2016