Submissions accepted for full credit until Tuesday Oct. 11 at 11:55pm.
Submissions can be handed in up to 4 days late with a 10%
penalty for each day past the deadline.
It is very important that you follow the specifications for the programming submissions. I intend to evaluate them electronically. If you do not follow the instructions, the automated grading will not work for your program.
The adjacency list format consists of:
<number of vertices>
Then for each vertex v:
For example, for this graph,
The input is:
10
3 1 5 9
2 0 2
2 1 3
2 2 4
2 3 5
3 0 4 6
2 5 7
2 6 8
2 7 9
2 0 8
Your program should permit the user to use arbitrary amount of white space and arbitrary line spacing when typing these numbers in. The input files contain only integers.
After finding a minimum dominating set D for the graph, the program should print a dominating set certificate for D in the same format as used for input for assignment #1 (print the input graph followed by the dominating set).
Several sample input files and the expected output files are available here:
dom_inputs.zip (right click on this and use "Save as")
The input files are:
| File | Graph type |
|---|---|
| icayley.txt | Cayley Graphs |
| ifootball.txt | Football Pool Problem Graphs |
| ifullerene.txt | Fullerenes |
| ikneser.txt | Kneser Graphs |
| iqueen.txt | Queen Graphs |
These files have succinct representations of minimum dominating sets and can be useful for checking your answers:
ocayley.txt ofootball.txt ofullerene.txt okneser.txt oqueen.txt
These files have output format that matches what you are supposed to have for assignment #2. Since this output format is the same as your input format for assignment #1, you can use the program you wrote for assignment #1 to check your answers.
cert_cayley.txt cert_football.txt cert_fullerene.txt cert_kneser.txt cert_queen.txt
You can submit your program an unlimited number of times up until 4 days after the deadline. The date of your last submission will be used to determine how late your program was handed in. Do not use the connex option of submitting a "Draft". Draft submissions will not be graded (they are not included when I download student submissions from connex).
Use a constant NMAX set to 512 for the maximum number of vertices:
#define NMAX 512
If NMAX is not big enough, print an error message that explains
that the user should increase NMAX and recompile.
Do not use 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.
All code submitted must be your original work. 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.