1090181
| Question | Answer |
| Give a dynamic programming algorithm that takes an n-node path G with weights and returns the total weight of the independent set of maximum total weight. The running time should be polynomial in n, independent of the values of the weights. | solution is here: www.sussex.ac.uk/Users/davidw/courses/pa/resources/exercises/answers/sheet9answers.pdf Note that G is a path not a graph ! The solution is also applicable for a tree . Was this question exactly in the previous comprehensive exam T132 ? |
Want to create your own Flashcards for free with GoConqr? Learn more.