Assignment 3

Question 1

1. There were lots of brute force search algorithms. This usually result in an algorithm which took a long time to run in the worst case (around n factorial) or the algorithm could get stuck (or did not always find a Hamiltonian path).
2. Some algorithms returned "no Hamiltonian cycle" in some cases. By Dirac's theorem, this case should never occur.
3. Some people provided a sample run of their algorithm rather than a proof. A proof certifies correctness for all cases whereas a sample run only guarantee correctness for a single case.

Question 2

1. An example is not a proof of correctness for any method.
2. For part b), depending on the method used, it may be necessary to check separate cases for odd and even values of |V(G₁)|,|V(G₂)|

Question 3

1. Some people assumed that |V(T₁)|=|V(T₂)| which was not given as an assumption.
2. Some people proved that there exists and edge whose removal disconnects the tree (rather for all edges).

Question 4 and 5

Assignment 4

Question 1

1. A lot of students used "upward induction" for part b). [UI] was marked on those copies. Please refer to the notes on common errors in proofs(PS PDF).
2. Some students have a long and clear explanations for their construction but badly explained the core reasoning of their argument.

Question 2

Question 3

1. A lot of people didn't clearly explain the steps of the algorithms for a) and b).
2. For c), some tried to argue that G is bipartite the property |S| &le |N(S)|. Of course, G is not necessarily bipartite (e.g., K₄). This was one of the more difficult questions where a counter-example exists. The question was meant for connected graphs only. But disconnected graphs were accepted as a solution.

Question 4

Question 5

Assignment 5

Question 1

1. A lot of students, again, used "upward induction" for a) and b). [UI] was marked on those copies. Please refer to the notes on common errors in proofs (PS PDF).
2. Some students copied a proof from the internet which involved colouring edges and other concepts not seen in class. The source should be provided in that case and all new definitions should be given. Even with a theorem and proof obtained online, some students incorrectly applied the copied theorem.

Question 3 and Question 4

1. Some students didn't show that they could generate all decks/matchings, [CGA] was written on those copies.
2. Some students didn't check that they weren't generating copies of the same deck/matching, [CC] was written on those copies.
3. For question 4b), a lot of people did a case analysis which involved the "best" that could happen (without proving why is was "best"). 4b) was a rather tricky question involving the pigeonhole principle.