CSC 422/522: Final project

Due on Sunday August 13 by 11pm.

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

Given an input graph G, an exact algorithm for the dominating set problem finds a minimum dominating set for G. Program (using C or C++) an exact algorithm for dominating set that is faster than the Assignment #4 approach on the types of graphs in the input files provided for assignment #4 (these graphs have small maximum degree).

Follow all the specifications given for assignment #4 except that the algorithm you choose should be your own creation. Some ideas that might work to make a faster algorithm are in the lecture notes Assign4_and_project.pdf on connex in the resources section.

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] Efficiency of operations.
4. [10] Correct output format- verbose mode.
5. [10] Correct output format- non-verbose mode.
6. [10] Finds minimum dominating sets (correctness).
7. [40] Number of graphs completed. To get marks for this, the program must have correct solutions. It is easy to make a fast program that gives incorrect solutions.

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.