FAQ

VSComp 2014 FAQ

 

53 Comments

Comments RSS
  1. Mattias Ulbrich

    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

    • Ernie Cohen

      No, the “Main Application Description” is left over from last year’s contest. It is not part of this year’s contest.

    • Peter Mueller

      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

  2. Natarajan Shankar

    I have emailed the source code for Problem 5 to the registrants.
    It wasn’t possible to upload it for security reasons.

  3. Natarajan Shankar

    I’ve placed a Binheap.tar.gz file containing the two .java files.

  4. Natarajan Shankar

    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.

    • Viorel Preoteasa

      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.

      • Peter Mueller

        Could you try a zip or tar file? That should work.

  5. Viorel Preoteasa

    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?

    • Peter Mueller

      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.

  6. Alex Summers

    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

    • Peter Mueller

      Hi Alex, I think Ernie’s reply to Mattias’s question answers this.

  7. Alex Summers

    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

    • Peter Mueller

      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.

  8. Mattias Ulbrich

    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!

    • Ernie Cohen

      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>

      • Yannick Moy

        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.

        • Ernie Cohen

          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.

    • Peter Mueller

      This problem deals with a standard binomial heap; so the Wikipedia documentation should be fine.

    • Marcelo Frias

      As stated by Peter, that wikipedia page should serve just fine.

  9. Yannick Moy

    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?

    • Peter Mueller

      Hi Yannick, Yes, you may assume that X is a subset of the elements in A.

  10. Viorel Preoteasa

    Problem 1: Can two equal cards be placed on top of each other in the same stack?

    • Peter Mueller

      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.

      • Viorel Preoteasa

        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.

  11. Yannick Moy

    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.

    • Peter Mueller

      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!

  12. Alex Summers

    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

    • Peter Mueller

      Yes, you should verify the algorithm described in the problem statement (and corrected on the Errata page).

  13. Alex Summers

    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 refines 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..) ?

    • Alex Summers

      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.

      • Peter Mueller

        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.

  14. Julian Tschannen

    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".

    • Peter Mueller

      Hi Julian, Yes, you are right. Thanks!

  15. David Mentre

    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?

    • Ernie Cohen

      That “h” should be “log”. This has been entered into the errata. Thanks for the catch.

  16. Natarajan Shankar

    V.0.2 makes the corrections suggested by Yannick, Peter, and Julian.

  17. David Mentre

    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()?

    • Ernie Cohen

      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.

  18. David Mentre

    In the for loop, for the test I would write “i != t && abs(x = log[i-1]) != val”.

    • Ernie Cohen

      See the answer to your question above – this is what you get if you replace “h” with “log”.

  19. Yannick Moy

    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?

    • Ernie Cohen

      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.

  20. Natarajan Shankar

    Submit your solutions by creating a separate page for each problem and adding a tar file for the solution.

  21. Natarajan Shankar

    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.

  22. Natarajan Shankar

    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.

Leave a Comment