Final Exam
==========

12 pages long, similar in style to last year's final, which I posted
on the web.

There is going to be no problems explicitly on Dynamic Programming or
Greedy Algorithms; still, you need to review these sections (see below
why).

One big question (50% of the total mark) on P vs NP-complete, in the
style of Q3 in PS3.  It has 10 parts (i.e., 10 problems), for each you
have to decide if it is in P (and here you may need polytime greedy
algorithms or polytime dynamic programming algorithms) or NP-complete,
and justify your assertions.

There is a list of NP-complete problems on the last page of the exam
that you can use to prove other problems NP-complete.  

40% of the exam (in terms of marks and content) is on Computability.  

There is one question on reducing a search problem to a decision
problem.
 
No aids are allowed for the final.

Unless something of the above is not clear, I do not intend to discuss
the contents of the final exam any further.