# 简单的个人梳理

这本书确实让人有种相见恨晚的感觉。和讲算法的好多书最终沦为工具书相比，这本algorthm design讲的更多的侧重可能是设计算法时需要做的各种考量。当然，我认为这一点在个人遇上了实际的问题需要定制算法时更为重要。

简单的罗列梳理一下本书我个人感到有意思的地方,罗列了很多的point。很多东西只是注明了在这书中有内容，具体的还是需要看书。

Interesting chapters and sections for the <algorithm design> book Chap 3 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 8: Chap 10: 10.1, 10.2 Chap 11: 11.3, 11.6, 11.8, Chap 12: Chap 13

## Graphs

Topological ordering definition

Strong connectivity 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)

DAG

Algorithm to find SCC

Minimum spanning tree

Application to Clustering: max spacing k-clustering

## Greedy algorithm

Huffman Coding

prefix code. definition

average information per bit

huffman coding. Algorithm

time complexity

## Divide-and-conquer

computing the recurrence is a central part of divide-conquer, which includes techniques like

unrolling the recurrence directly

substituting a solution into the recurrence

partial substitution

merge-sort

integer multiplication

convolution and FFT

## Dynamic Programming

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.

## Network Flow

concept:

## Linear programming

simplex algorithm 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.

Comments:

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?)

Application:

s t shortest path finding.

max-flow: formulate max-flow as a LP problem.

min-flow

multi-modality flow (to find whether it is possible to do it)

## Complexity and coping with complexity

definitions P: exists a poly-time algorithm NP:exists a poly-time certifier. 3-SAT, TSP, Vertex-cover, ... EXP: exists an exponential-time algorithm

Propositions P is in NP NP is in EXP and a Fact: P \neq EXP → either P \neq NP or NP \neq EXP, or both

NP-complete

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 key observation 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. O(n) time.

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. it should:

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:

greedy algorithm

pricing method (or primal-dual technique)

linear programming and rounding

dynamic programming using greedy algorithm:

load balancing 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.

vertex cover O(m+n) time.

Knapsack dynamic programming Not a bad algorithm

Solve by Exact algorithm (but with "reasonable" exponential time)

vertex cover 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.

set cover

## Local Search

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.

max-cut 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.

## Randomized algorithm

contention resolution 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) And this 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。 即"抽卡游戏"，每包有一张卡总共卡有n种，你要抽几包才能集齐所有卡片？

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)

Chernoff bounds Two bounds:

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 upper bound lower bound A simple reminder.

load balancing 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.

Markov inequality a simple application

other topics

closest pair

randomized caching

packet routing

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. then, 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.