Transcript Final Review

Final Review
Chris and Virginia
Overview
• One big multi-part question. (Likely to be
on data structures)
• Many small questions. (Similar to those in
midterm 2)
• A few questions from the homework and
class.
• (This slide is on the class webpage)
You need to able to
•
•
•
•
•
•
Summarize what we learned.
Recognize false proofs.
Use appropriate data structures.
Invent new data structures.
Design new (e.g. randomized) algorithms.
Know NP, coNP, NP-completeness,
approximation algorithms
• Matching, Graphs, and random walk.
Summarize what we learned.
•
Given a problem that appeared in class
or homework,
– Describe the approach to solve the problem
– Summarize the answer in 100 words or less.
•
You do NOT need to remember the
whole answer. We will NOT ask you to
repeat the entire solution.
Example: Planar 5 coloring
Example: Planar 5 coloring
1) Find v, any vertex of degree 5 or less.
–
Always possible, since |E| < 6 |V| in planar graph.
2) Merge x, y such that
(v, x) in E, (v, y) in E, but (x, y) not in E
–
We can always find x, y, since planar graph has no
5-clique.
3) Merge x and y, and remove v.
–
v will has only 4 neighbors, so there always exists a
color for v
4) Repeat Step 1 until there are no vertices
5) Color the vertices in reverse order of removal.
Recognize false proofs/argument
•
“Proof”: The above algorithm clearly runs
in O(n).
Recognize false proofs/argument
•
•
“Proof”: The above algorithm clearly runs
in O(n).
Problem in step 2: “Find x, y such that
(v, x) in E, (v, y) in E, but (x, y) not in E.”
– we don’t have adj. matrix to query in O(1)
– we can not afford to construct adj. matrix
since we only have O(n) total
– (Btw, this is not good answer, and Manuel
would not let me put something ambiguous
on the final.)
What data structure to use?
• You need Insert(x), Delete(x) and Find(x),
and you query a small subset of all the
elements very frequently.
What data structure to use?
• You need Insert(x), Delete(x) and Find(x),
and you query a small subset of all the
elements very frequently.
– Splay tree, because splay tree moves recently
accessed node to the top, so it is cheaper to
access it again.
What data structure to use?
• You need Insert(x), Delete(x) and
Findmin(x), and Findmax(x).
What data structure to use?
• You need Insert(x), Delete(x) and
Findmin(x), and Findmax(x).
– If a pointer to x is given for delete
• Use a maxheap and a minheap.
– If not,
• Use a binary search tree and maintain the pointers
to min and max elements.
What data structure to use?
• You need Insert(x), Delete(x) (given
pointer to x) and FindMedian().
What data structure to use?
• You need Insert(x), Delete(x) (given
pointer to x) and FindMedian().
– Use two heaps. A maxheap to store
everything less than the median, and a
minheap to store everything greater than the
median.
Prove lower bound
• Can you design a data structure where
Insert(x), Delete(x) and FindMedian() are
all little o(log n)?
Prove lower bound
• Can you design a data structure where
Insert(x), Delete(x) and FindMedian() are
all little o(log n)?
– No.
– Sorting lower bounds: Any algorithm that sorts
the set of elements, S, must perform at least
Omega(|S| log |S|) comparisons between
elements of S.
Decision problems, NP and coNP
NP-hardness and completeness
• Example: MINSAT
Given a formula in CNF and an integer K,
is there an assignment which satisfies at
most K clauses.
(no restriction on clause size, except that the
literals are distinct; no duplicate clauses)
MINSAT cont.
•
•
•
•
•
Reduction from Vertex Cover (VC).
Given [G=(V,E), K] instance of VC.
Direct the edges arbitrarily.
Create a clause Cu for each vertex u
For (u,v) add xuv to Cu and ¬xuv to Cv.
Approximation Algorithms
• Approximation Ratio: Malg/Mopt
• Example: 2-approximation for MINSAT
• Convert to VC:
– A vertex for each clause
– Edge between clauses if they have conflicting
literals: x and ¬x.
– Approximate VC instance.
Planarity
• You should know:
– Planar graph definition, duals, properties
– Planarity testing/planar embedding in linear
time
– Planar Separator Theorem: finding a small
separator in linear time
Planarity
• Example:
• a (1/3,2/3)-separator of size 2 for
outerplanar graphs
• A graph is outerplanar if it has a plane
embedding so that all vertices are on the
outer face
Outerplanar Separator
• Given the outerplanar embedding of G,
triangulate all inner faces.
• Create the plane dual, except for the
vertex of the outer face; this is a TREE of
degree at most 3.
• Find (1/3,2/3)-edge separator of the tree.
• Remove the two vertices of the
corresponding edge in G – this is the
separator.