This series of obligatory assignments has the goal of preparing the student to the final project, thus setting up the development environment, gaining practical experience on the methods discussed in class and carrying out analysis of experimental results. The content of the assignments will also provide elements for discussion in class. The student is encouraged to search feedback among peers, posting on the discussion board within the Black Board, or posing questions in class. Working in groups of maximum three persons is allowed, but only in form of discussion and exchange of idea. Since submissions must be individual each student has to develop his own code (this will be good for the final project, which is going to be independent work).
The first assignments are focused on the well known Graph Coloring Problem.
The graph (vertex) coloring problem (GCP) asks to find an assignment of colors to vertices of a graph in such a way that no adjacent vertices receive the same color. Graph coloring problems arise in many real life applications like register allocation, air traffic flow management, frequency assignment, light wavelengths assignment in optical networks and timetabling. More formally, let G = (V, E) be an undirected graph, with V being the set of |V| = n vertices and E being the set of edges. A k-coloring of G is a mapping ϕ : V → Γ, where Γ = 1, 2,…, k is a set of |Γ| = k integers, each one representing a color. A k-coloring is feasible or proper if for all [u, v] ∈ E it holds that ϕ(u) = ϕ(v); otherwise it is infeasible. If for some [u, v] ∈ E it is ϕ(u) = ϕ(v), the vertices u and v are in conflict. A feasible k-coloring in which some vertices are uncolored is said to be a partial k-coloring.
The GCP can be posed as a decision or as an optimization problem. In the decision version, also called the (vertex) k-coloring problem, the question to be answered is whether for some given k a feasible k-coloring exists. The optimization version of the GCP asks for the smallest number k such that a feasible k-coloring exists; for a graph G, this number is called the chromatic number χG.
For some graphs the chromatic number is known. A famous example is the four color theorem: if a graph is planar then it admits a feasible 4-coloring. However, deciding for a planar graph whether it also admits a 3-coloring has been shown to be an NP-complete problem. For general graphs it remains NP-complete and, consequently, the chromatic number problem is NP-hard (Karp 1972).
A famous chess puzzle asks to dispose n queens on an n × n chessboard such that none of them is able to attack any other using the standard chess queen’s moves. Thus, a solution requires that no two queens share the same row, column, or diagonal. Derived from this puzzle, the n2 queen puzzle asks to dispose in a n × n chessboard n × n queens subdivided into n subgroups such that no two queens belonging to the same group can attack each other. See Figure 1 for an example, where queens are represented by the integers 0, … , n−1 and each integer indicates a queen group.
The n2 has a solution whenever (n mod 6) ≡ 1 or 5. This condition is sufficient. It is also necessary when n < 12. Thus none of the n2 queen problems with n = 2, 3, 4, 6, 8, 9 have solution, while for n = 5 and n = 7 a feasible solution is reported in Figure 1. For n ≥ 12 counterexamples have been found, eg, for n = 12, 14, 15, 16, 18, 20, 21, 22, 24, 28, 32, that are solvable despite of the fact that the condition does not hold.
0 1 2 3 4 3 4 0 1 2 1 2 3 4 0 4 0 1 2 3 2 3 4 0 1
0 1 2 3 4 5 6 5 6 0 1 2 3 4 3 4 5 6 0 1 2 1 2 3 4 5 6 0 6 0 1 2 3 4 5 4 5 6 0 1 2 3 2 3 4 5 6 0 1
Write the graph in a text file in which each line begins with a letter that defines the content of the line. The legal lines are:
c Comment: remainder of line ignored.
p Problem: is of form:
p edge n m where n is the number of vertices (to be
numbered 1..n) and m the number of edges.
e Edge: is of the form e n1 n2 where n1
and n2 are the endpoints of the edge.
\n (new line) has to be
printed. Colors start from 1 and the first color in the column
represents the color assigned to vertex 1. All vertices must receive
a color, if your solution has uncolored vertices assign to them any
color at random.The submission has to comply to the requirements described in this appendix. The submission for the final exam will follow a very similar procedure. In the assignments, if your submission is not compliant you will be asked to resubmit (up to a limited number of times), but at the final exam a resubmission is not allowed.
Your work must be handed in electronically within the given deadline. (In the final exam, in addition to the electronic submission, you must also deposit two printed copy of your report at the teacher’s mailbox in the secretary office.) The submission is done via BlackBoard. Your files must be organized as follows:
Main directory:
CPRN/
where CPRN is the student’s CPR number without the last four digits (eg, 030907) and content:
CPRN/README
CPRN/Makefile
CPRN/src/
CPRN/bin/
CPRN/res/
CPRN/doc/
The file README reports the name of the student and the manual for the
compilation of the program. The directory src contains the source
files, which may be in Comet, C, C++, Java or python. If needed a
Makefile can be included either in the root directory or in
src. After compilation the executable must be placed in
bin. For java programs, a jar package can also be submitted. The
directory doc will contain the written report (only in the final
project), that will be the main source for the evaluation of the
project. The report must be kept anonymous and only identified by the
CPRN.
For this assignment you will have to provide the solutions in
res. For every queen problem, identified by n you must provide
two files. The first containing the solution in the format required by
the verifier and the second consisting of a single line made by two
numbers separated by a space. The first number must be an integer
indicating the number of colors used by the solution provided and the
second number must be a real indicating the number of seconds used to
find the solutions (you must produce your results in IMADA machines).
For example in the case of n=8:
CPRN/res/queen8_8.sol
CPRN/res/queen8_8.txt
> cat CPRN/res/queen8_8.sol 1 2 4 3 2 2 1 ...
> cat CPRN/res/queen8_8.txt 8 10.6
Use the same name patterns and extensions as in the example.
Programs must work on IMADA’s computers under Linux Ubuntu operating system and with the compilers and other applications present on IMADA’s computers. You are free to develop your program elsewhere, but it is your own responsibility to transfer the program to IMADA’s system and make the necessary adjustments such that it works at IMADA.1 The Comet version is assumed to be the last one available.
Your program will be run by typing in
the directory CPRN/:
bin/gcp -i INSTANCE -t TIME -s SEED -o OUTPUT
For example:
gcp -i queen8_8.col -o queen8_8.sol -t 300 -s 1 will run
the program on the instance queen8_8.col opportunely
retrieved from the given path for 300 seconds with random seed 1 and
write the solution in the file queen8_8.sol.
It is advisable to have a log of algorithm activities during the
run. This can be achieved by printing on the standard error or in a
file (which maybe determined with a option -o filename) further
information. A suggested format is to output a line whenever a new
best solution is found containing at least the following pieces of
information:
best 853 col 10 time 0.000000 iter 0 par_iter 0