Assignment 2

Assignment 2 has deadline 18.00, December 16. This is a strict deadline. Send your solutions to me (Jens Lagergren <jensl@csc.kth.se>) and Kristoffer (Kristoffer Sahlin <kristoffer.sahlin@scilifelab.se>). A

OBS OBS OBS OBS OBS OBS OBS OBS OBS OBS OBS OBS OBS OBS OBS OBS OBS OBS OBS!

As I announced at the lecture today, forget about the weights for the tree case and merely consider Independent Set also for that case. Also notice that I want polynomial time algorithms and that there may be exponentially many maximum size independent sets in graph, so merely computing al of them will not be sufficient. In fact, all the algorithms are supposed to be based on Dynamic Programming.