Class Notes (837,698)
United States (325,166)
Lecture

# Lecture 21 - Set Cover and Dynamic Programming.pdf

2 Pages
147 Views

Department
Computer Science
Course
COMPSCI 170
Professor
Satish Rao
Semester
Fall

Description
CS170: Efﬁcient 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 ﬁnd 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: deﬁne 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
Me

OR

Join OneClass

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

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.