COM SCI 180 Lecture Notes - Lecture 13: Vertex Cover, Vertep, Contraposition
Dictionary Data Structure
- Hashing with Chaining: array of lists use hash function to index
- Hash function (h:≥ → {1, 2, ,3 , …, r} is random)
- (1) For all x in U and i in {1, 2, ,3 , …, r}. P[h(x) = i] =
- (2) For all x ≠ y in ≥, h(x), h(y) are independent
- (3) h(x) takes O(1) time to compute
- If h satisfies (1), (2) and ४ n, then E[insert/find] = O(1)
- bucket(u) = all items that are accessed when inserting and finding
- The cost to insert or find is O(size of the bucket(u))
- Claim: ∀ u in ≥, E[bucket(u)]
- Proof:
- Let X = |Bucket(u)|
- For all v let Xu be 1 if collision or 0 otherwise
Intractability
- Which problems can be solved efficiently?
- Polynomial time algorithm: an algorithm runs in polynomial time if there exists a
constant d which gives runtime O(nd)
- How to compare problems
- X is easier than Y; Finding Median is easier than sorting
- Polynomial time reducibility
- We say that X reduces to Y (X p Y) if there is an algorithm for X that runs
in polynomial time and makes polynomial number of calls to an algorithm
solving Y
- We assume there is a black box that solves the problem Y. If we have the
power to solve Y then we have the power to solve X.
- We say X is polynomially easier (PE) than Y. We also say X reduces to Y
- Y is at least as hard as X
- Example
- Vertex cover
- A set S of subset of vertices is a vertex cover if every edge in the
graph has an endpoint in S
- Input: G = (V, E), and number k
- Output: does G have a vertex cover of size less than or equal to k
- Independent Set problem
- Independent set G = (V, E) a set S in V is an independent set in G
if no two vertices in S share an edge between them
- Input: G = (V, E), and integer r
- Output: yes if G has independent set of size greater than or equal
to r, no otherwise
- Claim: independent set p vertex cover
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
Hashing with chaining: array of lists use hash function to index. Hash function (h: {1, 2, ,3 , , r} is random) (1) for all x in u and i in {1, 2, ,3 , , r}. P[h(x) = i] = 1 (2) for all x y in , h(x), h(y) are independent (3) h(x) takes o(1) time to compute. If h satisfies (1), (2) and (cid:3640) n, then e[insert/find] = o(1) Bucket(u) = all items that are accessed when inserting and finding. The cost to insert or find is o(size of the bucket(u)) Claim: u in , e[bucket(u)] (cid:3639) For all v let xu be 1 if collision or 0 otherwise. Polynomial time algorithm: an algorithm runs in polynomial time if there exists a constant d which gives runtime o(nd) X is easier than y; finding median is easier than sorting.
