CSC 422/522: Assignment #4: Summer 2017

Due Friday July 21 at 11:55pm

Name your program Lastname.c or Lastname.cpp and upload it to connex. For example, I would use either Myrvold.c or Myrvold.cpp.

Program (in C or C++) the dominating set algorithm presented in class in Lecture 3.

For your graph data structure, use an adjacency list stored in an array with NMAX set to 2187 and DEG_MAX set to 16:

#include <stdio.h>  // include this even if your compiler is fine without it
#include <stdlib.h> // include this even if your compiler is fine without it
#define NMAX 2187
#define DEG_MAX 16

int n;
int degree[NMAX];
int G[NMAX][DEG_MAX];

Do not use dynamic memory allocation anywhere in your program (e.g. malloc). Do not use any library functions except printf and scanf (do not use ceil or floor from the math library).

Input: graphs are input in the same format as used for assignment #1. Input must come from standard input.

Output: Your program will have one command line parameter, verbose. If verbose is 1 then the output will consist of a certificate for your solution consisting of a graph followed by a dominating set. Use the same format as assignment #1. You can use your assignment #1 program to check your answers. If verbose is 0, then the program should print one line per graph containing the graph number (start numbering at one), the number of vertices and the dominating set order. The output must go to standard output.

VERY IMPORTANT: The input files contain some very difficult graphs and your program will not be able to solve the dominating set problem for all of them. Use

fflush(stdout);

I used this to print the non-verbose output:

printf("%5d %3d %3d\n", graph_num, n, min);

Some graphs you can use for testing your program are available on connex in the resources section. The file is: inputs.zip

The lecture notes Assign4_and_project.pdf in the resources section on connex have descriptions of the graphs and some things you should think about when doing assignment #4 to make it easier to write the code for your final project.

The marking will depend on:

1. [10] Compiles without errors or warnings.
2. [10] Programming style. Click here for a list of good practices
3. [10] Faithfulness to the pseudocode.
4. [10] Efficiency- you must follow the pseudocode but as efficiently as you can (both time and space). For example, do not apply an update taking O(n) time if O(maximum degree) is possible.
5. [10] Correct output format- verbose mode.
6. [10] Correct output format- non-verbose mode.
7. [40] Finds minimum dominating sets (correctness).

Connex is set up to allow an unlimited number of submissions. There is no harm in submitting early and often. Do not submit "Drafts". These do not get downloaded when I ask for student submissions.