Posted by: yuanzhan | November 9, 2010

The statistics of HW6 are:

• Mean 56.0
• Median 73
• Standard Deviation 36.1

I found some common mistakes or misunderstandings in the solutions of HW6:

• There are several students who use ” the greedy algorithm always stays ahead” as an argument to prove the greedy solution is optimal. This is a big misunderstanding. Greedy algorithm DO NOT always stays ahead for every problem. In fact,  greedy algorithm is like a wild guess. After you make a guess that the greedy solution may also be the optimal solution we, you need to start proving it is the optimal solution. One possible way or idea of proving this is to prove IN THIS PROBLEM, the greedy algorithm/solution we choose always stays ahead of other possible algorithm/solution. If this is proven, the greedy algorithm should stay ahead till the end and therefore generate an optimal final/overall solution. We are lucky to have a right guess then.
• For Q3, many students prove their solutions are optimal by using the same or similar argument of “because the greedy algorithm will make Ms. LiberalElite drive as far she can, therefore the total number of stops is minimized”. The logic is not right or rigorous. Because here the “as far as she can” does not mean Ms. LiberalElite does not have any gas when she stops, it only means Ms. LiberalElite cannot make it to the next stop based on her choice of the previous stop. It might help to understand this if we give a more detailed description of “as far as she can” which is like “the greedy algorithm will make Ms. LiberalElite drive as far she can from the previous stop she chooses”. In other words, the furthest distance Ms. LiberalElite can go is also decided by previous stop she chooses.  If Ms. LiberalElite choose a different previous stop from the one given by the greedy algorithm, she might be able to drive further this time than the furthest stop she can make after she chooses the previous stop according to the greedy algorithm.  Although actually this case is impossible, you still have to check that possibility and prove it’s impossible.