COMPSCI 170 Lecture Notes - Longest Path Problem, Set Cover Problem, Dynamic Programming
22 Oct 2013
School
Department
Course
Professor
Document Summary
1 set cover input: items: b = {1, , n} sets: s1, , sn b. We want to nd the fewest sets that will cover b. algorithm: choose set si that has largest number of elements, remove elements in si from all other sets, repeat. Property: set cover of size k (best solution) a set contains 1 k of the remaining elements. But it still runs in k ln n time instead of k time. k )n t = k ln n. Dynamic programming: de ne a set of subproblems, order them so each subproblem can be solved using solutions to previous subproblems. All can be seen as a path problem in a dag (directed, acyclic graph). Sequence: a1, a2, , an (like 7, 3, 5, 6, 1, 2, 9, 4, 1) Convert to a dag; any path is an increasing subsequence.
