Graders report for HW 1 HW 1 Part a Question 1 ------------------------------------------------- 0. Average: Total 9.43/10.0 (21 handed in) 1. Grading Policy: 3 Points for 1a) and 1b) 4 Points for 1c) Deduction: 1a) -1 if didn't explain with only an assignment 1b) -1 if didn't explain with only an assignment 1c) -2 if only "Use bit-reversal ring" HW 1 Part a Question 2 ------------------------------------------------- 0. Average: 9.95/10.0 (21 handed in) 1. Grading Policy: -1 if didn't include message generation function HW 1 Part a Question 3 ------------------------------------------------- 0. Average: 9.18, Total Students 43 1. Grading Policy: Some students added extra round for notification. -2 Two students didn't consider the known ring size case at all. -2.5 Some students thought known and unknown ring size don't matter. -1 One student confused the question with c symmetry based problems. -6 HW 1 Part a Question 4 ------------------------------------------------- 0. Average = 8.7 (43 submitted) 1. Grading Policy: Part (a) 1 point Correct Algorithm 4 points Communication Complexity Analysis Part (b) 3 points Correct Algorithm 2 points Communication Complexity Analysis 2. Comments Part (a) We need the analysis show that the complexity is not O(nlogn). One of the following cases will be enough: 1) Give a sample case whose complexity is greater than O(nlogn) 2) Show the lower bound of complexity is Omega(n^2) 3) Show that the tightest upper bound of the complexity is O(n^2) Some people only show that O(n^2) is an upper bound, but did not show that it is the tightest upper bound. It would lose points. Another general mistake is that some people made mistakes during the complexity analysis. Part (b) To show that the algorithm restores the complexity of O(nlogn), we need the complexity analysis or enough explaination. HW 1 Part a Question 5 ------------------------------------------------- 0. Average: 7.7 (39) 1. Grading Policy: The algorithm itself was worth 5 points -1 or 2 points (depending on severity) if used Petersen's but left out details. An incorrect solution needed to have a lot of details and some supporting arguments to get 4 or 5 points. The time bound with reasoning was worth 2 points. You couldn't just state that "obviously, it satisfies the bound asked for". The correctness discussion was 3: 1 point for saying that a leader gets elected 2 points for convincing me somehow that he was the unique one... this may have been implicit in some other part of the paper. (This was the part most people didn't bother with) 2. General Comments: There were two main classes of solutions as well as a couple neat ones that only one or two people did. The first major class of solutions was that based on the Petersen algorithm in Chapter 15 of the book. With a little modification the algorithm could be made to work in the synchronous case. The other big group of solutions was a variant of the HS algorithm where in each round a process dumps tokens that are smaller than itself and forwards tokens that are larger (setting itself to be an inactive process in the next phase). It uses the same hop count idea as in the original algorithm. The biggest problem (and the reason that the average is not about 2 points higher) is that while most students got a working answer they didn't bother to provide any kind of argument at all for correctness. It's not so obvious that some of these things really elect a unique leader and if it is it at least requires that to be stated. The fact that these problem sets took a great deal of time to decipher and understand indicate that the algorithms are not always intuitive. HW 1 Part a Question 6 ------------------------------------------------- 0. Average: 8.02 (43) 1. Grading Policy: 4 pts correctness + 3 pts efficiency + 3 pts analysis = 10 pts 2. General Comments: Most people randomly generated IDs and then ran a normal algorithm, retrying if there is a collision. The most common ranges to generate IDs in were [1,n] and [1,n^2]. A couple of people had processes randomly drop out of contention to be the leader. That is, each process alive at the beginning of the round would drop out in that round with some fixed probability. There would be a recovery process if all processes dropped out in a round. HW 1 Part b Question 1 ------------------------------------------------- 0. AVERAGE: 8.6 1. Grading Policy: Points Awarded For 1)a Mentioning in one form or another that the 2 lower order bits become the significant bits and this is the source of the ordering. Showing that the processes are grouped by their 3 high order bits once their index number bits are reversed and that this forms (n/l) disjoint order equivalent intervals. 1 Providing a good proof to support the above facts. 1b) Correctly using the conclusion from 1a insofar as mentioning that based on 1a there are 3 order-equivalent intervals of length l and 2l, where l marked. This is okay (of course). It was also not necessary to set child pointers, since the question wasn't clear enough in asking for them. Errors in child pointer implementation, other than those that affect parent pointers, were not counted as wrong. HW 1 Part b Question 4 ------------------------------------------------- 0. Average = 9.1 (41 submitted) 1. Grading Policy 6 points Correct Algorithm 2 points Time complexity 2 points Communication Complexity 2. Comments Some people did not show the complexity of the algorithm. Since we cannot say it is "efficient" without any complexity analysis, these people lost some points. Most students chose Parallel BFS algorithm as shown in textbook page 61. Some made a mistake on the communication complexity analysis. It should be O(diam|E|). HW 1 Part b Question 5 ------------------------------------------------- 0. Average: 7.122 1. Grading Policy: Out of a total of 10 points: 3 points were given for good pseudocode. 3 points were given for a good time analysis/argument. 3 points were given for a good complexity analysis/argument. 1 point was given for having the right idea on how to approach the problem (see below). This problem set took over 6 hours to grade, and each problem was examined in detail. (No deductions were taken off for impossible handwriting, but save your classmates the grief and use a machine if possible!) Part of the difficulty was the wide variety of mostly correct solutions -- solutions that took O(N) but may not have directly followed the hint given on the problem set. Those that were mostly correct were given most of the credit. Deductions / Points were given according to the following code: Pseudo-code: For full credit, one gave clear pseudocode indication start state, corner cases (such as what happens on the initial round), and termination. A - Pseudocode given is ambiguous or leaves question as to exactly what is going on. Answers that only gave an English description, especially when not precise or clear about what was going on, were succeptible to this markdown. (-1 to -3) B - Pseudocode seems incorrect in a major way, often marked on paper. (-3) C - Minor errors seem to exist in pseudocode (-1 to -2) D - Missing root notifications to neighbors (max: -2) Other errors that were marked on paper included missing starting or halting conditions. Right Idea: For full credit, you are headed in the right direction from the hint given on the problem assignment. F - Some solutions gave O(n) algorithms but were very far removed from the algorithm presented in class. (-1) Correctness J - Convince me that your algorithm is correct. Although you didn't need a simulation relation to the algorithm presented in class for full credit, your argument must be convincing that all nodes end up in the DFS minimum spanning tree exactly once, and that it is a minimum spanning tree. Your algorithm should complete correctly. Again, nothing formal is needed, but convince me that you know your algorithm is correct. (-1 to -3) K - No formal correctness argument, but reasoning in other parts of answer hint at correctness, earning partial credit. (+1 to +2) L - Missing correctness argument, a common mistake for those who only read the first part of the problem. See J. (-1 to -3) Time Argument N - Convince me that you know the bound for your algorithm is O(N). Giving the exact time calculation and showing that this is O(N), even if you are off by one (as several students were), is a good way to get full credit. Arm waving arguments or "It could be shown ..." or "It is obvious that..." got deductions and partial credit. (-1 to -3) P - Missing time argument, see N. (-3) Q - OK time analysis on bad algorithm. Although the algorithm seems problematic, your analysis seems ok for the algorithm you gave. (-1 to -3) R - Mostly convincing time argument, but arm wavey enough to be somewhat questionable. (-1) 2. General comments: Y - More verbage than required by problem. Given to a few papers that were loooong. (no deduction, just a suggestion for improvement). Z - One of the least clear papers in the class. (no deduction, just a suggestion for improvement). Most people implemented a solution that notified all of a node's neighbors (often with a special message). When a node receives this notify message over edge k, it doesn't consider that edge k later when executing DFS. (See solutions.) Some people did a query to all neighbors, and then a neighbor responded with its status (found or not found). This method increased message complexity but is still O(n). Several people forgot to give a correctness argument. Several people wrote way too much and some wrote way too little; see the solution for what I thought was a good amount to answer the question.