Skip to Content

COMP473 : Advanced Algorithms

Exercises

Week 1

Due: week 2 class

The goal of this week's exercises is to get you back in the swing of handling graphs, and to get you familiar with the DIMACS format for graphs, so you'll be able to use DIMACS(-style) graphs in your project.

  1. There's a nice piece of code for generating random graphs by Joseph Culberson. You can download it from here; you want the current version in the tar file. Try installing it. I installed it with no minimal problem on verus.

  2. Read the manual, and then generate some random graphs. At this stage, you just want the "No hidden graphs" option for the hidden colour selection, and "IID" for the generation of edges.

  3. Write some code to handle graphs, and specifically to carry out a breadth-first traversal of graphs. (You can get it from the Web if you like, but bear in mind that you might want to use this code later in your project, so think carefully about what kind of data structure you want for your graph.) Try it out on the random graphs to confirm that it's correct. Also, try it out on some hand-constructed examples (so you know the solution). Bring along the code, graphs and traversals for discussion in Week 2.

Week 2

Due: week 3 class

The goals of this week's exercises are to (1) introduce you to DIMACS-format benchmarks, and (2) get you implementing a solution to an NP-hard problem, (3) make sure you're comfortable with ACO as introduced in this week's lecture.

  1. There's a collection of benchmark graphs for graph colouring at Michael Trick's webpage, all in DIMACS format.

    Confirm for yourself that your code for reading in your random DIMACS-format graphs works here; determine the breath-first traversal starting from the lowest numbered node for some smaller graphs, and check that you both end up with the same answers.

  2. Implement a solution to the optimisation problem the Minimum Edge Dominating Set. There's a satisfactory definition in Wikipedia; there's also a listing in the Compendium of NP Optimization Problems, which tells you information like what the best approximation is. (The Compendium is a great resource in general, characterising different types of intractable problems.)

    Apply your solution to some graphs randomly generated according to last week's specifications. (I know the graph generator is for creating graph colouring instances, but we're just going to use it on this different problem first.) Some of these graphs should be small: for these, work out what the optimal solution is (by hand or by brute force), and see how your solution compares. Some of them should be larger; for these, you don't need to work out the optimal solution, just get a feel for how your algorithm scales up.

    Your solution doesn't have to be especially clever -- there's no benchmark you have to meet, so don't spend too much time on it. That said, you should still tell me what general approach you took to the solution, what the solution size is, and what tweaks you implemented to improve the solution.

  3. To make sure you've understood the ACO work, read this short overview paper,
    M. Dorigo, M. Birattari, T. Stützle, Ant Colony Optimization-- Artificial Ants as a Computational Intelligence Technique, IEEE Computational Intelligence Magazine, 2006.

  4. Skim this longer overview paper,
    M. Dorigo & T. Stützle, The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances, Handbook of Metaheuristics, 2002.

Week 3

Due: week 4 class

The three goals this week are to have some practice with constructive methods for graph colouring; to get familiar with software for visualising graphs (which you can use to understand the graphs you'll be using in the project); and to read an ACO paper on graph colouring.

  1. Prepare a graph (maybe ~15 nodes) and manually colour it using the D-SATUR and RLF heuristics. (So part of the exercise will be getting familiar with RLF, which wasn't covered in detail in lectures. You can use the code below to help you.)

  2. Colour a range of random graphs using DSATUR and RLF.

    1. Use the Culberson code to generate graphs for a couple of different sizes (n, the number of vertices) with a range of edge probabilities. Make sure you the edge probabilities result in graphs spanning the phase transition at theta = 2.3 (recall that that's the ratio of edges to nodes), equivalent to average degree of 4.6.

    2. It's probably easiest to get code that implements DSATUR and RLF from here. Have a look inside the code to see how it might differ from standard versions of the algorithm.

  3. For the graph visualiser, I propose PIGALE, although you can find another one if you'd prefer. Do the following:

    1. Go to the GSVR site for the link to download Pigale. There's also the Software List link there to check out other graph visualisation software.

    2. Install Pigale. It's pretty straightforward.

    3. Look at some of the test graphs. Use the Open menu command to access the sample graphs in the tgf directory. In particular, look at the ones in text format.

    4. Manually move the nodes around on some of the graphs. Then try different algorithms for automatically arranging them. These are found in the Embed menu item. In particular, try Tutte Circle, FPP Fary, and both Schnyders.

    5. Save a displayed version of the graph, using the Image icon (fifth from the left).

    6. Try out some graphs of your own.

    7. Write some code to transform your DIMACS-format graphs so that they can be displayed in Pigale.

  4. Read the paper (the source of the ACO graph colouring material): 

    Ants Can Colour Graphs
D. Costa, A. Hertz
The Journal of the Operational Research Society, Vol. 48, No. 3 (Mar., 1997), pp. 295-305
Published by: Palgrave Macmillan Journals on behalf of the Operational Research Society
Stable URL: http://www.jstor.org/stable/3010428
    From uni you'll have access to JSTOR, but not from home (unless you go via the uni library catalogue).

Week 4

Due: week 5 class

  1. Your major activity this week will be preparing your presentation.

  2. In addition, construct an exercise to test out the Las Vegas graph colouring algorithm for a graph that is not k-colourable. That is, you should:

    • Construct a graph G and choose an integer k such that G is not k-colourable.
    • Construct the Zykov tree for G.
    • Trace the operation of the algorithm of the Zykov tree.

Week 5

Due: week 6 class

The two goals this week are to have a look at randomised algorithms and to do a couple of exercises on hypothesis tests using non-parametric statistics.

  1. Implement RandQS from the lecture notes.

    1. Generate some random data for varying sizes of n (e.g. n = 10, 20 40, 80, 160, ...). For each value of n, generate 5 instances.

    2. For each instance of each value of n, determine the runtime of your program. If you're using C++, for example, you'll probably use clock() to do that. It's almost certain that the program will be so fast, and the granularity of your clock so coarse, that you'll get a value of 0 msec returned. So for each instance of each value of n, run your program a large number of times, and then average. For C++, there's some discussion here. This will give you a runtime value for a particular instance of n.

    3. Plot each instance of each value of n (with axes x = n vs y = time), and on the same graph plot y = x, y = n log n and y = x^2.

  2. For the stats question, you're going to use the following data. You want to solve the optimisation problem OptProb, which has solutions that can be represented as single integers. (Vertex Cover is of this type: the solution is the size of the cover.) You've generated 10 graphs all of the same type (same numbers of vertices and edges), and run two heuristic algorithms over them, HeuristicA and HeuristicB. The solutions for each heuristic on each graph is as follows:

    Graph # HeuristicA HeuristicB
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    		 118
    137
    112
    142
    107
    131
    159
    121
    108
    156
    121
    159
    119
    123
    106
    144
    151
    135
    136
    114
    		 128
    134
    117
    140
    120
    135
    166
    127
    121
    161
    120
    173
    134
    119
    123
    157
    167
    146
    135
    126

    1. Use the Wilcoxon rank-sum test to determine whether the performance of HeuristicA and HeuristicB are significantly different.

      Note that I've updated the lecture notes to include a brief discussion of the application of the Wilcoxon test specifically to paired data. There's also a useful detailed example here.

      An online calculator for carrying out the test is here.

    2. Use the sign test to determine whether the performance of HeuristicA and HeuristicB are significantly different.

      An online calculator for carrying out the test is here.

    3. Consider the case where the 10 graphs above are not all of the same type. What should you do?