Interesting chapters and sections for the <algorithm design> book
Chap 4: 4.7, 4.8
Chap 5: 5.1, 5.2, 5.5, 5.6
Chap 6: 6.6
Chap 7: 7.1, 7.2, 7.3, 7.5, 7.6, 7.7-7.11
Chap 10: 10.1, 10.2
Chap 11: 11.3, 11.6, 11.8,
definition: a graph is strongly connected if every pair of nodes is mutually reachable.
Algorithm to find it:
pick a node.
run BFS from s in G
run BFS from s in G' (the reverse G)
return true if all nodes are reachable
Strong components (undone)
Algorithm to find SCC
Minimum spanning tree
Application to Clustering: max spacing k-clustering
prefix code. definition
average information per bit
huffman coding. Algorithm
computing the recurrence is a central part of divide-conquer, which includes techniques like
unrolling the recurrence directly
substituting a solution into the recurrence
convolution and FFT
Edit distance, sequence alignment
Typical solution for a DP problem
Solutions:Typically, a DP solution involves the following 4 steps:
Define an array (holding the optimal values of “subproblems”). Explain how to extract
the answer to the original problem from the array.
State a recurrence to fill in the array.
An algorithm to fill in the array using the recurrence (usually trivial).
An algorithm to recover an actual optimal solution from the array once the array is filled in (usually easy by “re-tracing” the steps through the array).
analysis, such as running time or others.
BFS: basic feasible solution.
The point in finding solution in linear programming is that the optimal solution is always at the vertex of the space defined by the linear constraints. So we just need to numerate the vertex to find the optimum. In the simplex algorithm, since the number of vertex is exponential, a greedy local update scheme is used.
procedure: a greedy algorithm to find adjacent BFS
choosing pivot column: the increase per unit.
choosing pivot row: to preserve feasibility
when to stop: all coefficient in the top row is non-negative
why is the resulting solution optimal?
Bad cases → degeneracy: new basis but is in fact the same vertex, which would results in cycling infinitely.
this algorithm could take exponential time but in practice it runs very fast.
runs fast after a random perturbation of the input instance.
however, there is a poly-time algorithm for LP→The Ellipsoid Algorithm. But simplex is still preferred. (why?)
s t shortest path finding.
max-flow: formulate max-flow as a LP problem.
multi-modality flow (to find whether it is possible to do it)
Complexity and coping with complexity
P: exists a poly-time algorithm
NP:exists a poly-time certifier. 3-SAT, TSP, Vertex-cover, ...
EXP: exists an exponential-time algorithm
P is in NP
NP is in EXP
and a Fact: P \neq EXP → either P \neq NP or NP \neq EXP, or both
Asymmetry of NP-completeness: co-NP
complement of decision problems in NP
Coping with NP-completeness
Sacrifice one of the three desired features and solve them using DP, divide&conquer, network-flow algorihtms, etc.
Solve arbitrary instances of the NP-hard problem → design algorithm for special instances.
Solve NP-hard problem optimally → design approximate algorithms or heuristics.
Solve NP-hard problem in polynomial time → design algorithm that take exponential time.
How to cope with np complexity: three cases: ****
Solve arbitrary instances of the problem
For special cases:
Independent set on trees
start with leaf, delete the parent together (with edges). Some nodes will be isolated without any edges, but these nodes would also be in the independent set.
weighted independent set on trees
greedy algorithms could simple fail → we ask for dynamic programming.
divide into subproblems: max value with or without the current node.
the updating formula:
using an order from leaf to root (like an inverse topological order?), just ensuring that a node is processed after all its descendants have been processed.
the key that we could use this dynamic programming for this problem on trees because the tree structure ensure that the subproblems do not intervene with each other thus could be solved independently.
Solve by Approximation or Heuristics:
challenge here is you need to prove you approximate the optimum with a solution very close to optimum.
run in polynomial time
applies to arbitrary instances of the problem
guarantteed to find a solution within some ratio of the true optimum.
The central problem is that we need to compare our approximation with the optimal solution which we don't know and have no hope of computing this →we need a lower bound of the optimum and this lower bound, we hope, should not be too weak to be useful.
Four technique to use:
pricing method (or primal-dual technique)
linear programming and rounding
using greedy algorithm:
we seek to minimize a quantity known as makespan: simply the maximum load on any machine. The scheduling to find an assignment of minimum makespan is NP-hard.
A simple algorithm is to assign a job to the machine which currently has the least makespan.
Not a bad algorithm
Solve by Exact algorithm (but with "reasonable" exponential time)
Reduce the complexity to “limit exponential” level.
You don’t brutally search all possible solution and apply a certificate test on each solution. Instead you based from some observations to design a better algorithm. It’s very important in this situation.
The finding small vertex covers algorithm reduce the brutal search from O(kn^(k)* ) to O(2^(k)kn)
Using max flow algorithm
Using local search. Gradient descent.
local search as an optimization problem
the idea of gradient descent.
Metropolis Algorithm and simulated annealing.
the metropolis algorithm takes directions towards the "down-hill", but is also accepts "up-hill" moves with a smaller probability.
simulated annealing: apply the metropolis algorithm with a temporature gradually decreasing.
Hopfield neural networks
use a simple state-flipping algorithm to determine a stable configuration.
we find this algorithm will always converge because each time the total absolute weight of "good" edges is always increasing, at least by one.
a demonstration to how to related the locally optimal solution related to the global optimum.
bound a local optimal configuration to the real global optimum in the single-flip algorithm
What are more advanced relation than single-flip?
Best-response dynamics and Nash Equilibria.
very interesting but the analogy of
nash equilibria → local optimum
social optimum →global optimum
may not always hold. Because a social optimum is not always stable.
aims at maximizing successful access with fewer deadlock in a symmetry-breaking way → distributed system with no communications.
The important thing is how to define the event and describe its probability.
Very useful facts as in the analysis of algorithm.
this now simplifies the bound.
important fact. the union bound.
Note that in proof related to these algorithms, it is very tricky to find the right number, to choose the right bound. In this section, it is the choice of t.
finding global minimum cut
As a quite naturally "robust" parameter, global min-cut finds the smallest number of edges whose deletion disconnects the graph.
An efficient deterministic algorithm does exist. A polynomial time by applying s-t cut n-1 times. See proof 13.4 at page 714.
But, David Larger 1992, the contraction algorithm.
the probability of successfully finding the global min-cut is only polynomial small. So let us run it for polynomial number of times.
linearity of expectations
the linearity of expectations is simply expectatios of two random variable is just the sum of two expectations.
Useful math fact
it goes with complexity of O(log n)
could be used to prove the waiting-time bound (13.7 in KT textbook).
The applications in this technique includes the guessing card problem (with or without memory).
And also the problem of collecting coupons。
Max 3-SAT random approximation
the expectation of a random assignment
We could find better solution than expectations!
The lession in this appication is that
we first base on random construction, find a expectation.
we then identify a quantity of interest, we denote it as a variable and use the above mentioned expectation to find a bound fir the quantity of interest.
→ In short, for example, use the lower bound of the expectation to find the lower bound of the quantity of interest. (in this case, the probability of a random assignment give more than expected 3-Max clauses.)
universal hash function: randomized hashing
Ad-hoc hashing is potentially bad because it could be attacked.
→ An ideal hash function should map n elements uniformly into m hashing slots.
Universal hashing (Carter-Wegman 1980s)
Note that it talks about a set of hash functions.
A simple variation. (Note the difference in coding scheme)
one bounding the probability of x deviates below E(x)
one bounding the probability of x deviates above E(x)
are called Chernoff bounds
It has a complementary use compared with computing the expectation.
It gives you a bound on estimating how far it will deviates from the expectation
A simple reminder.
distributing load to processors just uniformly would result in a good solution.
This problem is quite similar to the hashing problem. We are now interested in measuring how well a randomized algorithm works.
a simple application
Randomized divide&conquer: k-th smallest element finding,QuickSort
we wish to show that divide and conquer works quite well in conjunction with randomization.
In particular, the 'divide' step is done by randomization.
We also show that the expectation of random variables could be used to analyze the spen time on recursive calls.
If we want to shrink by at leat 3/4 →a quarter of number is smaller than the splitter, and a quarter of number is larger than the splitter → 1/2 possiblity to find such splitter.
means that the possiblity of randomly find such splitter is exactly 1/2.
the complexity is O(n) !!!
k-th element finding
Randomly select a splitter.
The analysis of the running time with a random splitter is based on this idea:
we expect (or rather explicitly restrict) the size of the set under consideration to go down by a fixed constant fraction every iteration
then we should get a convergent series and
hence a linear bound is obtained.
Quicksort: modified version with a random splitter testing.
Expected time O(nlog n), quite impressive and only modifies a small portion of algorithm. That is, refuse the bad splitters.
BST representation of the splitter of the QuickSort algorithm → help to understand where two elements are compared
→observation: elements are only compared with its ancestor and descendants.