Skip to Content

COMP473 : Advanced Algorithms

Project: Graph Colouring

Due (draft): Wed 27 Apr, 2011
Due (final): Wed 4 May, 2011

Task

As mentioned in class, the graph colouring optimisation problem will be the topic of this assignment; see the lecture notes with the definition and ACO approach, and the lectures notes with Monte Carlo and Las Vegas approaches. The goal of the project will be for you to examine these approaches, and design a probabilistic algorithm inspired by either the ACO metaheuristic or the randomised approach (or both). You'll then compare the performance of your algorithm to a simpler alternative. As we've also talked about in class, most of what you need to do in the lead-up to this has been covered in the weekly exercises; this project draws them all together.

The subparts of the task are then as follows:

  1. Implement a dynamic order solution to graph colouring (probably either DSATUR or RLF) for use as a baseline.

  2. Design and implement a probabilistic algorithm.

  3. Evaluate your algorithms:

    1. Use two types of graphs -- randomly generated graphs and benchmark graphs. (You'll recall these from the Week 2 exercises.)

    2. Include some assessment of statistical significance in comparing your probabilistic algorithm to the baseline. Note that much of the work we've looked at has used multiple graphs of the same type in the evaluation.

  4. Write a report outlining what you've done. It should have the same basic structure as the papers we've looked at, although it will be different in some ways:

    1. The abstract or summary is fairly standard: it should be around 150-200 words in length, and able to stand alone as a concise and comprehensive description of your project's objectives, approach and outcomes.

    2. The Introduction can be quite short, since we all know what the graph colouring problem is.

    3. The Method should be reasonably detailed. For describing the dynamic order solution, illustrate with an example graph. For your algorithm, give pseudocode, and explain how a probabilistic aspect has been incorporated; as part of this, be clear about how your algorithm is related to, and different from, the algorithms discussed in lectures.

    4. Results and Discussion are standard. In particular, talk about whether different graphs behave differently.

    5. Include the code as an Appendix.

Assessment

Assessment
Attribute		Levels of Attainment
UnsatisfactoryFunctionalProficientAdvanced
Comprehensiveness of Abstract Incomplete, in that it does not provide a brief statement of all three of the problem, approach and outcomes; or, all three are expressed, but the descripiton is muddled and generally unclear. Conveys the problem, the approach, and outcomes, but a little less clearly than might be expected, or at an inappropriate level of detail. Stands as a surrogate for the full report: a clear summary of the problem, approach and outcomes; but may require some rewording to make it accessible to a non-specialist. An excellent summary of the work carried out, clearly stating the problem, the approach taken, and the outcomes, in a manner that is accessible to a technical but non-specialist audience.
Clarity of Problem Statement The introduction to the report does not clearly state the problem the project set out to solve. The introduction does state the problem to be solved, but it takes a little effort to disentangle. The introduction states the problem clearly, and its significance is clear. The introduction provides an exceptionally clear and well-motivated problem statement, presented in a way that makes the reader eager to learn about the details of how the problem was solved.
Clarity of Method Unclear what was done at all. Sufficient to know which approach was taken as the dynamic ordering solution, and what the basis of the ACO approach was. Good level of detail in description of both approaches: all parameters are explained, and work can be replicated. As for Proficient, also including well-illustrated examples.
Quality of Work Carried Out A weak or incomplete effort; significant doubt that the work reported represents an appropriate amount of effort for a half-semester honours project. A competent piece of work, perhaps with some loose ends and gaps. A quality piece of completed work that demonstrates ability on the part of the student. A very high quality piece of work that would have a very good chance of being accepted for presentation at a professional conference in the field.
Quality of Algorithm A token change to a simple algorithm; no real thought involved. A satisfactory algorithm, performs comparably with baseline; some evidence of thought regarding choice of probabilistic aspect. A good algorithm that performs well with respect to the baseline; perhaps some evidence of investigation of alternatives before finally settling on algorithm presented. An excellent algorithm that performs comparably with those published in the literature.
Clarity of Evaluation Unclear what was achieved in the project. The report carries out an evaluation, if a little unclearly. The report clearly evaluates the project implemented. The report clearly evaluates the project implemented, indicates how these relate to the originally stated outcomes and to the Costa and Hertz work, and realistically appraises the scope for future work.
Overall Quality of Writing Very poor; problems with coherent presentation of ideas. Understandable, but with some problems in grammar, style and spelling. Grammar and style of an acceptable standard; could be safely given to an external party with only minor editing. High quality prose; well written; could comfortably be made available via a corporate website.