Lecture 21 - Set Cover and Dynamic Programming.pdf

2 Pages
Unlock Document

Computer Science
Satish Rao

CS170: Efficient Algorithms and Intractable Problems Lecture 21 October 21, 2013 Lecturer: Satish Rao Scribe: Amy Boone 1 Set Cover input: items: B = f1;:::;ng sets: S ;:::;S ▯ B 1 n We want to find the fewest sets that will cover B. Algorithm: 1. Choose set S that has largest number of elements i 2. Remove elements in S fiom all other sets 3. Repeat 1 Property: set cover of size k (best solution) ) a set contaiksof the remaining elements. Analysis: ntelements remain at time t (after t sets) 1 an iteration t, covek ntremaining elements nt+1 ▯ n t n = (t ▯ )n 1 t 1 t k nt▯ (1 ▯ ) k ! 0hen do we stop? remember: (1 ▯ x) ▯ e ▯x so 1 t ▯ 1 t ▯ t nt▯ (1 ▯ ) k < (e k) n ▯ (e k )n ! t = k lnn No elements are uncovered? But it still runs in k lnn time instead of k time. 2 Dynamic Programming Dynamic programming: define a set of subproblems, order them so each subproblem can be solved using solutions to previous subproblems. Very similar to recursion. All can be seen as
More Less

Related notes for COMPSCI 170

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.