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