***** 6.852: HW1 : Report from graders ********************************* ---- HW1a. Problem 1 ---- almost all students got this problem right, i.e., that the problem is impossible. Those who didn't understand what "comparison-based" meant, an showed that it was possible got 5--8 point. ---- HW1a. Problem 2 ---- all the students had the correct intuition to solve the problem. everybody understood the problem well. the ones who haven't proved their claims didn't get 10. ---- HW1a. Problem 3 ---- The grading scheme Marks were dedudcted for following Not mentioning the messege bound or time bound 2 Time or message bounds are given without proof 1 Detailed answer but answer is incorrect 5 Short commings (minor) in proof 2 Correct answer but vague resoning 4 If basic assumptions were not met (unknown ring size , comparison based etc..) 2 An additional mark of 1 was given for being orderly and methodical. Common problems, A large number of students has used Petersons algorithm some have reffered to it others have just used it. Some people had usd Petersons algorithm without considering the fact it is to be used in a synchronous network. ( 1 mark was deducted for copying the description in page 496 of the Text with very minor modifications ) . Some students had used number of messages to refer to number of distict messages ( without considering a message traveeled n hops to be n messages) Some students focused on neighbours in only one side and gave lgorithms that had O(n*n) message complexity. --- HW1a. Problem 4 --- 1. 3 pts for part a, 7 for part b 2. nothing written for part 0 pts something written 1 pts something sensible for prooof 4 pts 3. part a, any algorithm O(n^2) or O(nlog n) => full pts 4. -1 if in part a, not written -third step of circulating the final count to evryone -no mention of how to select leader or how to find size of ring after leader is elected 5. -1 to -2 for proof being unclear -not explaining no. of rounds -not explaining messages per round -not splitting the above two parts or unclear and non-conclusive proof --- HW1b. Problem 1 --- Since the algorithm was mostly straightforward, I decided to put more weight on a correct specification of the behavior. a) (4/10) I was looking for algorithm-independent properties stated in reference to particular variables. The main properties I was looking for were: guaranteed construction of a BFS, guaranteed delivery of a broadcast message, guaranteed acknowledgement. I took a point off if any of these were missing. Some people stated properties about their particular algorithm, which were more than invariants that imply the desired properties. I took a point off for this. I took a point off for stating properties imprecisely (i.e., without referring to specific variables). I also took points off for statements that just didn't make any sense. There were two variants in the answers to this problem: some people "piggybacked" the message with the search message used for BFS construction, others constructed the tree first and then used it for broadcast. There were also a couple of different interpretations as to what "acknowledgement of receipt from everyone" meant exactly, but this did not affect grading. b) (3/3) Most people got the algorithm right. I took a point off if it was not clear what kinds of messages were sent (the message alphabet), and took points off for incorrect algorithms. It was OK to refer to the SyncBFS algorithm from the book and say what extension to it were made. c) (3/3) I was looking mainly for two invariants: one used to prove that the algorithm guarantees delivery, one used to prove that it guarantees acknowledgement. It took a point off if one of these were missing. Also, these were supposed to be _invariants_, which means that they must state something that is true at every round. I took one point off for properties that were not stated as invariants or that were not easily rephrased as invariants. I also took a point off for incorrect or confusing properties. --- HW1b. Problem 2 --- 6 - got the general idea 2 - counterexample construction 1 - clarity of explanation, accuracy of details 1 - generalized the solution COMMON ERRORS ------------- - confusion about diam: refers to largest # HOPS required from any node A to node B (as opposed to max total path weight) - confusion about levels versus rounds. (Each level of the algorithm- a merging of trees- comprises many rounds) - explanation about O(n) for max # of rounds needed not always well supported/explained. - forgetting to clearly present the case against O(diam) for a particular construction (i.e. not explaining what diam is) --- HW1b. Problem 3 --- GRADING POLICY: Figuring out that the problem is unsolvable: 1 pt General method of the proof is correct (similar to Thm. 5.1): 1 pt The proof: 7 pt (In particular: Up to the last rounds (until all messages are lost): 4 pt Finalization (starting at loss of all messages, to the end): 3pt Generalization to all n>2: 1 pt --- HW1b. Problem 4 --- Only answered it for f=1 (not generic): - 3/10 Didn't mention the correct initial values: - 3/10 Gave good execution but didn't take the correct conclusions: - 3/10 Minor mistakes: - 1/10 Basically wrong answers are graded from 1 to 5/10 according to knowledge shown about the algorithm. -----