Posted by: atri | October 31, 2012

## Some suggestions

I have talked to you some of you over this week and I mentioned some things that might be useful for the course in general and HW 6 in particular. So here is a list of them (in no particular order):

• For every problem in this course (be it on a HW or the exam) that asks for an algorithm you should try to design the algorithm in the following order:
1. Use a reduction first: i.e. just change the input and use an existing algorithm as a “black box”
2. Modify an existing algorithm slightly to make it work for the problem on hand
3. Design an algorithm from “scratch”
• To prepare yourself better for the final, solve as  many problems as you can. You should definitely do the HW problems but in addition solve unassigned problems from the book. When picking which problems to solve, pick problem that look really different. Your goal should be to apply the main concepts/ideas that we cover in the lectures in as many different scenarios as possible. The exam question will not test whether you can apply the concepts in context which we have already covered but whether you can apply them in different contexts. Thus, solving similar problems is not going to be of much help here. Also the problems in the book, like problems that I assign, tend to be verbose. So as a first step you also have to figure out how to extract the mathematical problem from the English specification. Hence, the more such problems you solve, the better placed you would be to solve them during the exam.
• If you are working on a problem from the book that is not assigned and want to run by your solution with someone: talk to your teammates. Or the TAs. Or me.
• It general, I would not ask you to prove something from scratch. In general, you will have to build proofs from things we have already seen. In particular for HW 6, your correctness proofs for greedy algorithms should be doable with either the “greedy stays ahead” (Sec 4.1) or the “exchange argument” (Sec 4.2)