This a list of questions on the project.
(Last updated: Thu Jan 13 11:03:00 CET 2011)




Q: The time limits listed, are they supposed to be seconds or minutes?
   (Felix P. Hargreaves So  2 Jan 2011 22:21:04 CET)

A: Seconds! I specified in the text.

Q: On page 4 on 1st paragraph, it says "....can be constructed by the
   algorithm in Figure 3", that is supposed to be figure 2 right?
   (Felix P. Hargreaves So 2 Jan 2011 22:21:04 CET)

A: Right. I corrected the text.

Q: Are we supposed to implement a correctness checker ourselves?
   (Felix P. Hargreaves So  2 Jan 2011 22:21:04 CET)

A: Yes! I will implement one for myself after the 20th of January.

 
Q: In figure 4, the PermutationToTreeDecomposition pseudo-code, line 7
   bothers me. It says "...by adding to E an edge between each pair or
   non-adjacent vertices ...". Since this makes little sense to me, and
   since the keyboard-keys "r" and "f" are next to each other on normal
   keyboard layouts, I'm assuming it is a typo and that it was supposed
   to be "...pair OF non-adjacent vertices...".
   (Felix P. Hargreaves Mon Jan  3 11:58:49 CET 2011)

A: Right! I corrected in the text.


Q: Do the listed times for the instances apply also when running the
   race-tests to determine which algorithm is the best? If yes, how is
   it possible to set up race such that the instances get paired with
   the correct times when running Race? (note: I am using these commands
   to make the vector of instance-filenames: instclass <- "instances"
   and then instances <- paste(instclass,dir(instclass),sep="/")
   (Felix P. Hargreaves Wed Jan 12 19:18:14 CET 2011)

A: It can be done, but it requires some knowledge of R programming. For
   example, you can read a file that contains name of instance and its
   time and put it in a data.frame, say A.  Then you can access the data
   by: A[i,]$nameinstance and A[i,]$time, where i is the row number
   corresponding to the instance sampled at a certain stage. Ok, if it
   is not clear come to visit me in my office with your laptop.

   An easy alternative (perhaps even more fair) is to run a different
   race for each different time limit.

Q: The algorithm in figure 2 has a variable called "tw" which contains
   the size of the maximal clique(s). The text states that this is the
   treewidth, however, Proposition 1. states that treewidth = w(G) -
   1. Am I correct in assuming that the algorithm is in fact returning
   w(g) and not tw(g)?
   (Felix P. Hargreaves Wed Jan 12 19:18:14 CET 2011)

Q: No, I do not think you are right. Read carefully what A_G(v) is and
   what would be the size of the clique...




Q. What does the LB and UB mean in the Talbe 1? Does that mean the
   treewidth should be between the LB and UB?
   (Ning Jin Thu Jan 13 11:03:00 CET 2011)

A. Lower Bound and Upper Bound. Yes, the tree width must be within those
   numbers. What you find with heuristics is an upper bound.


Q. What about the time limit? Does that mean that u can run the
   algorithm on that instance over and over again until it reaches the
   time limit and among those attempts, u get the best result?
   (Ning Jin Thu Jan 13 11:03:00 CET 2011)

A. Yes, if you algorithm terminates before the time limit. In the case
   of metaheuristics, they should be able to use all the time made
   available to them.


Q. In appendix C, if i use comet, do i need to compile it in C? and in
   the example, u put a time limit, what does this time limit used for?
   for one run, or for one algorithm each?  
   (Ning Jin Thu Jan 13 11:03:00 CET 2011)

A. No, a program in comet does not need to be compiled (comet does just
   in time compilation hence it would not be good to precompile). Just
   explain how I should run it in a README file.  The time limit is for
   one single run of the algorithm per instance. You can check times in
   comet with System.getCPUTime().