Scoring Criteria
The judges were a bit disappointed in the number of entries. There were only six applications entered, 2 on Linux and 4 on Windows. We thought that this would be a pretty straightforward problem to solve with many chances for parallelism. Perhaps it is the time of year?
Six different graph data files were used to compute the execution score for this problem. The smallest file had 12 nodes and 60 edges; the largest file had 36 nodes with 161 edges. The table describes features of the data sets (Degree is the range of the number of edges per node):
File | Nodes | Edges | Degree | Colors
------------------------------------------------------
paley17.txt | 17 | 67 | 8 | 5
------------------------------------------------------
K6.txt | 36 | 111 | 2-10 | 6 (run with max=5)
------------------------------------------------------
K6a60.txt | 36 | 129 | 2-14 | 5
------------------------------------------------------
q6-6-3-4.txt | 36 | 161 | 4-15 | 5
------------------------------------------------------
zz328-1-2.txt | 33 | 133 | 3-12 | 5
------------------------------------------------------
CP12.txt | 12 | 60 | 10 | 6
To get bigger test cases that were still computable with the time limit, the judges started with a "small" test case and examined the coloring results. One of the colors was chosen and edges were added between pairs of nodes that had been assigned the chosen color. Three rounds of adding edges in this way typically boosted the execution time from less than 1 second to around 5 minutes. At first, the judges found it odd that adding edges, which would restrict the problem further, would increase the computation time when the number of nodes remained the same. It was soon realized that the added restrictions limited the number of solutions and having more solutions possible (fewer edges) led to finding one of those solutions much quicker.
A maximum of 10 minutes (600 seconds) was allowed for each data file. If an application exceeded this limit or terminated with some form of runtime error, a time of 600 seconds was recorded for the time on that data file. If the application delivered the wrong number of minimum colors it was considered incorrect and a time of 600 seconds was recorded. The total execution time of all six files was summed and a fraction of 100 points was awarded based on where the total fell within the range of the minimum and 3600 seconds. A 5 point penalty accessed to entries that printed colors starting with "0".
One entry was threaded with Cilk++, one was in Java, one used C#, and the rest were written in C/C++.
Point spread:
100
99
82
33 33
0
The write-up portion of each entry was read and scored by two judges. Each judge used the 10-30-10 breakdown of points for serial algorithm description, parallel algorithm description, and performance, respectively. One important component to the judging was to determine how close the submission was for publication on ISN. The assigned score was the average of the two judges scores.
Point spread:
45 42
36
10
0 0 0
Bonus points were given for contestant’s forum posts made before the problem entries were closed. Five points per post (maximum 25 points possible) were awarded.
The overall winner was akki (we tripled checked this time :-), who had the fastest code execution and highest scoring write-up. As an extra (unrecorded) test, larger data files were run. The entry submitted by mdm100 was able to handle the largest file used (76 nodes, 1367 edges, 12 colors) in less than the time limit.
| |
Re: Scoring Criteria
The judges were a bit disappointed in the number of entries. There were only six applications entered, 2 on Linux and 4 on Windows. We thought that this would be a pretty straightforward problem to solve with many chances for parallelism. Perhaps it is the time of year?
Six different graph data files were used to compute the execution score for this problem. The smallest file had 12 nodes and 60 edges; the largest file had 36 nodes with 161 edges. The table describes features of the data sets (Degree is the range of the number of edges per node):
File | Nodes | Edges | Degree | Colors
------------------------------------------------------
paley17.txt | 17 | 67 | 8 | 5
------------------------------------------------------
K6.txt | 36 | 111 | 2-10 | 6 (run with max=5)
------------------------------------------------------
K6a60.txt | 36 | 129 | 2-14 | 5
------------------------------------------------------
q6-6-3-4.txt | 36 | 161 | 4-15 | 5
------------------------------------------------------
zz328-1-2.txt | 33 | 133 | 3-12 | 5
------------------------------------------------------
CP12.txt | 12 | 60 | 10 | 6
To get bigger test cases that were still computable with the time limit, the judges started with a "small" test case and examined the coloring results. One of the colors was chosen and edges were added between pairs of nodes that had been assigned the chosen color. Three rounds of adding edges in this way typically boosted the execution time from less than 1 second to around 5 minutes. At first, the judges found it odd that adding edges, which would restrict the problem further, would increase the computation time when the number of nodes remained the same. It was soon realized that the added restrictions limited the number of solutions and having more solutions possible (fewer edges) led to finding one of those solutions much quicker.
A maximum of 10 minutes (600 seconds) was allowed for each data file. If an application exceeded this limit or terminated with some form of runtime error, a time of 600 seconds was recorded for the time on that data file. If the application delivered the wrong number of minimum colors it was considered incorrect and a time of 600 seconds was recorded. The total execution time of all six files was summed and a fraction of 100 points was awarded based on where the total fell within the range of the minimum and 3600 seconds. A 5 point penalty accessed to entries that printed colors starting with "0".
One entry was threaded with Cilk++, one was in Java, one used C#, and the rest were written in C/C++.
Point spread:
100
99
82
33 33
0
The write-up portion of each entry was read and scored by two judges. Each judge used the 10-30-10 breakdown of points for serial algorithm description, parallel algorithm description, and performance, respectively. One important component to the judging was to determine how close the submission was for publication on ISN. The assigned score was the average of the two judges scores.
Point spread:
45 42
36
10
0 0 0
Bonus points were given for contestant’s forum posts made before the problem entries were closed. Five points per post (maximum 25 points possible) were awarded.
The overall winner was akki (we tripled checked this time :-), who had the fastest code execution and highest scoring write-up. As an extra (unrecorded) test, larger data files were run. The entry submitted by mdm100 was able to handle the largest file used (76 nodes, 1367 edges, 12 colors) in less than the time limit.
Thanks for triple-checking... :D
Might I add, IMHO, things are being handled much better in phase 2. There is a definite improvement in the quality of problem descriptions. That leaves little to be discussed on the forums but I see that as a positive. Also, responses to queries and the judging process is much quicker this time round. Good job clay and team.
I do still wish I had direct access to the scores, though...
| |
Re: Scoring Criteria
Congratulations to akki!
I agree, it would be some consolation for the loosers to know what scores were achieved.
| |
Re: Scoring Criteria
I've just checked the graph data, and I must admit that I'm dissapointed. Given the scope specified the problem n<=676, with possibly disconnected graphs, why are only trivial-sized graphs tested? All graphs executed in less than 1 second on my 4 core machine, which to my mind is not a thorough test of the solutions.
One graph did not comply with the specified input criteria, q-6-6-3-4.txt - Clay stated in a forum post that parallel edges would not be present, yet this graph includes two edges from AA to DD. Was this corrected in the files used for scoring? My solution would throw an error indicating the input file was invalid since an edge between these nodes was already defined. Was I scored 600 seconds for this graph?
I've not verified it, but it also seems that none of the graphs are disconnected. This was stated as a possibilitiy, but implementing this seems like wasted effort, as was implementing approaches to handle larger graphs.
All in all, I feel the bounds of this problem were set unnecessarily loose, and with such loose bounds, providing a solution that could handle the scope of the problem took a lot of time away from the intent of these challenges, namely writing effective threaded code.
The present open problem, travelling baseball fans, is similar in nature, with no polynomial time algorithm and even looser bounds (26^3 and 2^31 for the two size variables in the problem.) Will this also be tested with toy examples?
I kindly request that the judges consider setting bounds that are realistic compared to the scoring instances used, and that the scoring instances exercise the full scope of the problem stated. Anything less than that, and contributors are simply wasting their time.
mat.
| |
Re: Scoring Criteria
Congrats akki
| |
Re: Scoring Criteria
thanks avparate, mdm100...
| | |
