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.