FAQ
VSComp 2014 FAQ
Hi organizers!
I have just registered and received login credentials for vscomp.org/wp-login.php. I can successfully login to the backend. However, I do not seem to find the verification challenges there. Is page http://vscomp.org/main-application-description/ a part of it?
Thanks for your help.
Mattias
No, the “Main Application Description” is left over from last year’s contest. It is not part of this year’s contest.
Hi Mattias, The problem statement is at the very bottom of http://vscomp.org/. The source code for problem 5 is still missing; I am trying to get a hold of it. Peter
I have emailed the source code for Problem 5 to the registrants.
It wasn’t possible to upload it for security reasons.
I’ve placed a Binheap.tar.gz file containing the two .java files.
The aforementioned Binheap.tar.gz file link is on the bottom of http://vscomp.org/
To submit your solutions, please create a separate page per problem and upload your files to this page. We can then conduct a peer review through the discussion section.
I am not sure how to upload my solution. Should I create a Post, or an Article, or Media? I tried to upload one Isabelle file, but I could not due to security restrictions.
Could you try a zip or tar file? That should work.
The graph in problem 4 seems to be a multigraph. According to the description one could have two edges from node1 to node2, labeled by 1 and 2, respectively. Is this the intended structure, or it is a consequence of the representation?
Yes, the graph is a multi-graph. There can be more than one edge from node n1 to node n2 provided that they have different labels.
I have a question about problem 2. The statement suggests that the elements of A should be unchanged (except that they may be swapped). This seems to agree with the outline of a suggested algorithm, which only includes swaps on A. But in the example given, then input and output arrays do not store the same elements – is this a mistake? What should the output array represent, if it is not the original set?
Thanks
Hi Alex, I think Ernie’s reply to Mattias’s question answers this.
I have a question about problem 4. Is it assumed that the integers stored in the nodes themselves are unique per graph? Otherwise, I’m not sure that the algorithm provided will work (but perhaps that’s my misunderstanding).
Thanks
Hi Alex, no, the natural numbers in the nodes need not be unique. A node is uniquely identified by its address in the heap (its object identity). Let me know if there is a problem with the pseudo code.
Thanks for your answer.
A question on Proplem 2: Isn’t the array after the algorithm (top of p. 4) supposed to be a permutation of the initial array? Or is the presented map the permutation to be applied? (But then it does not go with D)
Thanks for a clarification!
Yes, it looks like the initial value of A in the example was changed without adjusting the final value for A appropriately. The final value should be
<0|->22, 1|->11, 2|->55, 3|->33, 4|->100, 5|->44>
If I simulate the algorithm, I find a different result:
22, 1|->33, 2|->100, 3|->11, 4|->44, 5|->55>
(and also different values for D, compatible with the above)
Your values for A and D are not compatible with the result you give for F.
Sorry, I just inverted the value of D that was listed. You are right about the final value of A. The final value of D should be its inverse.
P and F look correct.
In question 5, is the wikipedia page a correct alternative reference? i.e.
http://en.wikipedia.org/wiki/Binomial_heap
The book cited does not appear to be freely available (at least, I couldn’t find it immediately from google).
Thanks
This problem deals with a standard binomial heap; so the Wikipedia documentation should be fine.
As stated by Peter, that wikipedia page should serve just fine.
Hi organizers, the problem 2 seems to imply that X is a subset of A, although this is not stated explicitly. Indeed, it says “let i be D(x)” for any x in X, which is only possible if x is also in A. Is it correct to assume X is a subset of A?
Hi Yannick, Yes, you may assume that X is a subset of the elements in A.
Problem 1: Can two equal cards be placed on top of each other in the same stack?
The problem statement says that “Each subsequent card is placed on the leftmost stack where its card value is no
greater than the topmost card on that stack.” I think the phrase “no greater” answers your question.
Thank you for the answer. “no greater” answers my question, but the fact the the provided example does not contain this situation made me wonder about the correct interpretation.
In problem 2, there is a typo in “add a new interval p′ to P with p′.first = p.count”, which should read “add a new interval p′ to P with p′.first = p.first + p.count”. It also seems to me that the precision about “If i < p.first+p.count then x has already been processed so the state is left unchanged" is useless, as this case should never occur.
Yes, you are correct about the typo. It should read “p′.first = p.first + p.count” as you suggest! I think you are also right about the other observation, but that’s less critical. Thanks!
We added an Errata page at http://vscomp.org/errata/, where we will post corrections to the problem statements. Please check it periodically.
For problem 2, are we obliged to use the given (outlined) algorithm? Or is it ok to verify different code which achieves the same result?
Thanks
Yes, you should verify the algorithm described in the problem statement (and corrected on the Errata page).
I see. So, which parts are “putative” and which belong to the algorithm specified? I assume that the breakdown into three procedures is not part of the definition. Is it just the sentence “The algorithm reﬁnes the partition P by processing each element x of X” which is in some sense, fixed (e.g., it’s not ok to use an algorithm which handles the whole set X at once..) ?
actually, I don’t think I understand this usage of “putative”, also in my own question :) But I understood the overall sentence to mean that this is just one possible design.
Hi Alex, I think your algorithm should operate on the data structures described in the problem statement. How you break down the operations into procedures and whether you process one element of X at a time or the whole set at once is up to you.
Great – thank you.
There is another typo in Problem 2 in the Verification Tasks section. In Part (a), it should talk about F’ instead of F: “For any i < N, P'(F'(i)) is an interval containing i".
Hi Julian, Yes, you are right. Thanks!
Question on problem 3: in function lookup(), in the for loop, there is a reference to “h” array. But this array is not defined in that function and is not a global variable.
Should we define a local variable “h” and do a “grab(h, hd)” before the for loop ?
Other fix?
That “h” should be “log”. This has been entered into the errata. Thanks for the catch.
V.0.2 makes the corrections suggested by Yannick, Peter, and Julian.
Another question on problem 3: in macro grab(), advance() is called twice. However, from the way advance is written, it would produce exactly the same result (effect: ht[me()] == var && local == var) if it was called only once. Is there a bug in the code of advance()?
The code is correct. The read of var is volatile, and the two successive calls to advance may read different values if var is being concurrently updated. And yes, it is not hard to see that if advance() is called only once, a bug would result.
Also, note that the read of var and the writing of ht[me()] are two separate atomic actions. If they constituted a single atomic action, a single call to advance() would suffice.
OK, thanks.
In the for loop, for the test I would write “i != t && abs(x = log[i-1]) != val”.
See the answer to your question above – this is what you get if you replace “h” with “log”.
Problem 2 – when you say for verification task 1: “The algorithm always terminates returning an output state A′, D′, P ′, F ′.”
Do you mean checking that A’ is a permutation of A, D’ is the inverse of A’, P’ is a partition of A’, and F’ is the corresponding map?
No, task 1 is just to show that it terminates; the detail on the output state is given merely to provide a binding for task 2.
Submit your solutions by creating a separate page for each problem and adding a tar file for the solution.
When you’re ready, please create a separate page for each problem with the uploaded tar files (using “Add Media”). You can hit publish if it is past the deadline, but please upload files before the deadline.
Okay, everyone. Wrap up what you’re doing and publish your solutions. I’m going to change the roles of the participants so that you can’t upload stuff.
I have added some comments to our solution to problem 1 after the competition; it’s the same solution as the one we submitted but easier to read. You can browse it on https://bitbucket.org/nadiapolikarpova/vscomp14.
Sam Owre
Please submit questions here.