CS 4820 develops techniques used in the design and analysis of algorithms, with an emphasis on problems arising in computing applications. Example applications are drawn from systems and networks, artificial intelligence, computer vision, data mining, and computational biology. This course covers four major algorithm design techniques (greedy algorithms, divide and conquer, dynamic programming, and network flow), computability theory focusing on undecidability, computational complexity focusing on NP-completeness, and algorithmic techniques for intractable problems, including identification of structured special cases, approximation algorithms, and randomization.
Greedy Algorithm
Greedy Stays Ahead
Greedy is at least as good as the optimal solution in each step
Exchange Argument
- Take any optimal solution, we can make it exactly the same as our greedy solution without having the optimal solution produce a worse result.
- There is some “structure” unique to this problem. All solutions have this “structure” give the same number of lateness.
- Our greedy solution has this “structure”
- We can exchange any optimal solution to have this “structure” without making this solution worse
Divide and Conquer
Master theorem says that for an algorithm with running time $T(n) = aT(\frac{n}{b}) + f(n)$. $f(n)$ is some polynomial of $n$, so we have $T(n) = aT(\frac{n}{b}) + O(n^c)$.
- $a = b^c$: $T(n) = O(n^c ; logn)$ - A balance between constant work at each level and number of subproblems at each level.
- $a < b^c$: $T(n) = O(n^c)$ - Time dominated by the constant work we do at upper levels: take $a=1$ as an extreme example, all of the time will be spent on top level.
- $a>b^c$: $T(n) = O(n^{log_ba})$ - Time dominated by each subproblems we have as the recursion go deeper. A lot of branches of subproblems will be generated.
Network Flow
- Max flow 问题转换为 Min Cut 问题，Min Cut 问题永远可以给自己不想要的边 infinite capacity 来将它排除在 min cut 之外。
- effectively infinite: 任何一个无法达到的数，都可以视作 infinite，比如 infinite capacity 可以是一个已知的 cut 值+1 (max flow 必然小于任意一个 cut，所以没有任何一个 flow 可以达到 cut + 1)
NP
Proving Reduction
- Show that your reduction σ takes polynomial time.
- Show that x is a solution to the problem you are reducing from if and only if σ(x) is a solution to the
problem you are trying to show is NP-hard. You need to show the implication in both directions.
Proving NP, NP-Hard, NP-Completeness
- NP: prove you can verify a solution in polynomial time
- NP-hard: prove some known NP-Hard (or NP-complete) problem can be reduced to A in polynomial time (注意是别的已知问题可以被转换成我们要证明的问题)
- NP-completeness: it is NP-hard and it is NP
Important NP-Complete Problem
- satisfiability problems: Boolean satisfiability, CNFSAT (conjunctive normal form satisfiability) , 3CNFSAT (aka 3SAT)
- graph problems: Clique, Independent Set, Vertex Cover, Dominating Set, Colorability, Planar 3-colorability
- covering problems: Set Cover, 3-dimensional matching (3DM)
- tour problems: directed and undirected Hamiltonian circuit (HC), Traveling Salesperson (TSP)
- numerical problems: Subset Sum (SS), Partition, Knapsack, Bin Packing
Tips
- If a problem asks you to decide if there exists a set of at least k objects satisfying some property, try reducing from another problem that involves picking at least k objects, e.g. Independent Set or Clique.
- Similarly, if a problem asks you to decide if there exists a set of at most k objects satisfying some property, try reducing from another problem that involves picking at most k objects, e.g. Vertex Cover or Set Cover.
- When reducing Independent Set / Vertex Cover to another graph-like problem. We find out adding a node representing edges is very useful. (Dominating Set, practicefsol 4, fakesol7 3)
- When a problem does not easily fit into either of the general categories listed above, usually the best thing to try first is 3CNFSAT.
- When do the reduction from A to B, try to reduce A to a special case of B. (hw5 P3 Clique -> Submatrix Domination, hw6 P2 Vertex Cover -> Dominating Set)
Turing Machine
Decidability
Give a total Turing Machine (one that always halts) to accept any “yes” instance and reject any “no” instance
Undecidability
- Prove by Diagonalization
- Prove by Reduction: we usually reduce our problem to Halting Problem or the complement of it (Non-Halting Problem aka. Looping Problem). Note: σ in this case has to be computable instead of polynomial-time
To prove some problem is undecidable within a certain time bound, use clocked diagonalization.
Crucial Facts
Minimum Spanning Tree
- cut property: Let A and B partitions vertices V, if e is the minimum edge connecting A and B, e must be in every minimum spanning tree.
- cycle property: Let C be any cycle in G, e be the maximum cost edge on that cycle, e is not in any minimum spanning tree
Proof Techniques
Loop Invariant and Recursion: 一个很好的例子是 T7.42 的证明
recursion = induction
loop invariant = induction hypothesis
termination condition = basiscomputation = logic
-- Dexter Kozen