Several of you approached me for remarkings of assignment 2. If you want to have an assignment remarked, the policy for requesting a remarking is clearly stated on the course web page. It is against policy for you to come and see me directly and request a remark, and such requests will not be accepted. Please refer to the course web page or discuss your situation with the professor if you are unclear with regards to this.
Secondly, if you want part of your assignment remarked, I expect you to perform the following first:
Most of assignment 3 was based on proofs, and marks were awarded for both correctness and clarity. In these sorts of problems, clarity and precision are what differentiate a mediocre solution from a perfect one. You may have had marks deducted because I didn't think your solution was clear; these deductions are consistent with the way that the other students were marked, and hence, I can't give you extra marks if you feel that the deductions were overly harsh or unjustified. I tried to understand each of your proofs thoroughly and read them all carefully, but if you feel that I made an error and misunderstood something you were doing, you are welcome to request a remarking in this case.
So, if, after checking the solutions, you feel that your answer was correct, and you can give me a very strong written justification as to why your answer was correct, then I will remark, but only under those circumstances. Of course, your answer does not have to follow the written solution; if you used a completely original solution that you strongly believe to be correct but that I considered incorrect, please justify its correctness.
In order to indicate to me that you have complied with the above guidelines, I will expect, amongst your written explanation justifying that your answer was correct but I didn't understand it, a written statement saying: "I have read the solution to this question, as well as the notes in the marking guide, in compliance with the remarking policy." Requests without this statement will not be honoured.
A general note: I cannot stress strongly enough that a proof by example is not a sufficient proof. Examples may be useful in order to help you to understand the problem, but I will not consider them (nor will nearly any TA) part of a solution when I am marking a proof question. Many of you are struggling with mathematical proofs and logic. I recommend that brush up on these techniques.
This question was generally well done. Some students had difficulties formulating their proof correctly, or made some errors. Marks were taken off accordingly.
Some problems here, namely in logical errors, but again, fairly well done. Proof by contradiction and proof by construction were both acceptable if done correctly.
Considerable proof problems here. Many of you attempted to prove by examples, or many of you made claims that were "obvious" without giving justification behind them (and some of these claims were blatantly wrong, as by counterexamples that I provided on your papers). Please refer to solution.
Many of you don't understand what an approximation ratio is. An approximation ratio has nothing to do with time complexity of an algorithm. Please review these concepts, as you will undoubtedly need them on the final exam.
Lots of problems here. Many of you used binary trees or heaps of various kinds, but in essence, you provided a "Best-Fit" heuristic as opposed to a "First-Fit" heuristic. Placing items into the most empty bin is not a characteristic of the First-Fit heuristic (earlier bins used first). Sorting the data, and then placing it in bins is not a characteristic of the First-Fit heuristic. Reasonable marks were given if your algorithm worked but was not a First-Fit heuristic approach.
Very few, if any, problems here.
Most of you did not give an O(|E|) algorithm. If your algorithm worked correctly, I gave you 10 points. If it ran in O(|E|) and you had a suitable justification, I gave you 5 points. Most of you implemented slight variations on the same O(|E|2) algorithm (which involved removing edges). I will not remark your time complexity.
Most of you got this question correct. Some of you made some faulty assumptions, which may have resulted in large loss of marks depending on how much you used those assumptions later on. There was some difficulty in clarity in many of your proofs. You made jumps in logic and said that one thing implied another, which was not at all obvious (or even correct!). Others amongst you made strong claims regarding the nature of the graph, matching, and vertex cover, and failed to give a reasonable proof for these claims. Marks were taken off for these errors.
The answer to this question was very simple, and it was extremely difficult to give part marks - this was either a 10 or 0 question, largely. Please refer to the solutions for the correct answer.
This question wanted you to show the existence of a vertex cover of size 2|M|; it did not want you to show that a vertex cover must be of size 2|M| or that the minimum vertex cover is of size 2|M|, etc... Lots of problems with this part, especially with clarity. Some of you tried to show the statement was false. It isn't. Some of you misunderstood the definition of a vertex cover. See the solution.
Many of you just made a short statement regarding this fact. You needed to give more detail for the full 10 marks. See the solution to see why you lost marks here. Some of you were relying on incorrect things you tried to show in (c) and (e), which also resulted in penalties. Some of you attempted to prove by contradiction. Most of you did this incorrectly, and you should have been using the concept of an approximation ratio.
Good luck on your exams, happy holidays, and have a great new year!