Announcements
Announcements
Homework 5 Due Today
Exam 3 next week
Same Rules
Let me know by W if you need an alternative testing time (and didn’t need to for earlier tests)
Practice problems on webpage, review video soon
Exam 3 Topics
Chapter 5
Greedy Algorithms
Exchange Arguments
Interval Scheduling
Optimal Caching
Huffman Code
MSTs
Chapter 6
DPs
LCSS
Knapsack
CMM
All-Pairs Shortest Path
MIS in trees
TSP
Last Time
Dynamic Programs
Family of Subproblems
Recursion Relation
Tabulate and Solve
Proof of Correctness by Induction
Runtime: [#subproblems][time/subproblem]
Finding right subproblems is key
Today
Maximum Independent Set of Trees
Travelling Salesman Problem
Independent Set
Definition: In an undirected graph G, an independent set is a subset of the vertices of G, no two of which are connected by an edge.
Problem: Given a graph G compute the largest possible size of an independent set of G.
Call answer I(G).
Simple Recursion
Is vertex v in the independent set?
If not: Maximum independent set is an independent set of G-v.
I(G) = I(G-v).
If so: Maximum independent set is v plus an independent set of G-N(v).
I(G) = 1+I(G-N(v)).
v
Recursion: I(G) = max(I(G-v), 1+I(G-N(v)))
Subproblems
I(G)
I(G-N(v))
I(G-v)
I(G-v-w)
I(G-v-N(w))
I(G-N(v)-w)
I(G-N(v)-N(w))
Very little subproblem reuse.
Need subproblems I(G’) for every subgraph G’.
– Number of subproblems 2|V|.
Hardness
Independent Set is what’s known as an NP-Hard problem. This means that people believe that there may well be no efficient algorithm for it.
However, there are special cases where we can do better.
Independent Sets and Components
Lemma: If G has connected components C1,C2,…,Ck then
I(G) = I(C1)+I(C2)+…+I(Ck).
Proof: An independent set for G is exactly the union of an independent set for each of the Ci. Can pick the biggest set for each Ci.
Independent Sets of Trees
Subproblems are all subtrees!
Recursion
Root not used:
I(G) = Σ I(children’s subtrees)
Root is used:
I(G) = 1+Σ I(grandchildren’s subtrees)
Example
1
1
1
1
1
1
1
3
4
3
8
Travelling Salesman Problem
In your job as a door-to-door vacuum salesperson, you need to plan a route that takes you through n different cities. In order to space things out, you do not want to get back to the start until you have visited all cities. You also want to do so with as little travel as possible.
Formal Definition
Problem: Given a weighted (undirected) graph G with n vertices find a cycle that visits each vertex exactly once whose total weight is as small as possible.
5
2
1
2
3
2
1
4
2+1+2+2+5 = 12
Naïve Algorithm
Try all possible paths and see which is cheapest.
How many paths?
n possible options for first city.
(n-1) possible options for second city.
(n-2) for third city
…
Total n!
Runtime ≈ n!
Note on Difficulty
The Travelling Salesman problem is a difficult problem. In fact it is widely believed that there is no polynomial time algorithm for it (more on this in chapter 8).
However, there is an algorithm that beats the n! naïve algorithm.
Setup
Need partial solutions for subproblems.
Look for s-t paths instead of cycles.
Bestst(G) = Best value of a path starting at s and ending at t that visits each vertex exactly once.
Answer is minimum of Bestst(G)+ℓ(s,t).
Recursion
What happens if we undo the last step?
Last step some edge (u,t).
Value is ℓ(u,t)+length of rest of path.
Want best s-u that uses every vertex except for t.
Bestst(G) = minu[Bestsu,-t(G)+ℓ(u,t)].
Now we need a recursion for Bestsu,-t(G).
s
t
u
Recursion II
How do we solve for Bestsu,-t(G)?
Remove last edge (v,u).
Need best s-v path that uses all vertices except for t and u.
Need more complicated subproblems to solve for that.
Recursion III
Bestst,L(G) = Best s-t path that uses exactly the vertices in L.
Last edge is some (v,t) ∈ E for some v ∈ L.
Cost is Bestsv,L-t(G)+ ℓ(v,t).
Full Recursion:
Bestst,L(G) = minv[Bestsv,L-t(G)+ ℓ(v,t)].
Runtime Analysis
Number of Subproblems:
L can be any subset of vertices (2n possibilities)
s and t can be any vertices (n2 possibilities)
n22n total.
Time per Subproblem:
Need to check every v (O(n) time).
Final Runtime:
O(n32n)
[can improve to O(n22n) with a bit of thought]
Runtime Comparison
We have O(n32n) time.
Naïve algorithm is O(n!).
Note: n! > (n/e)n >> 2n.
Dynamic programming doesn’t make this problem fast, but it is much better than what we had before.