Algorithms, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2002–2012·April 30, 2012 5:16:12 AMAlgorithmsFOUR T H EDIT IONR O B E R T S EDG EWICK K EVIN W A Y N E6.5 REDUCTIONS‣designing algorithms‣establishing lower bounds‣classifying problems‣intractability2Bird’s-eye viewDesiderata. Classify problems according to computational requirements.Frustrating news. Huge number of problems have defied classification.complexityorder of growthexampleslinearNmin, max, median,Burrows-Wheeler transform, ...linearithmicN log Nsorting, convex hull,closest pair, farthest pair, ...quadraticN2?⋮⋮⋮exponentialcN?3Bird’s-eye viewDesiderata. Classify problems according to computational requirements.Desiderata'.Suppose we could (could not) solve problem X efficiently.What else could (could not) we solve efficiently?“ Give me a lever long enough and a fulcrum on which to place it, and I shall move the world. ” — Archimedes4ReductionDef. Problem X reduces to problem Y if you can use an algorithm thatsolves Y to help solve X.Cost of solving X = total cost of solving Y + cost of reduction.perhaps many calls to Yon problems of different sizespreprocessing and postprocessinginstance I(of X)solution to IAlgorithmfor YAlgorithm for X5ReductionDef. Problem X reduces to problem Y if you can use an algorithm thatsolves Y to help solve X.Ex 1. [element distinctness reduces to sorting]To solve element distinctness on N items:•Sort N items.•Check adjacent pairs for equality.Cost of solving element distinctness. N log N + N .cost of sortingcost of reductioninstance I(of X)solution to IAlgorithmfor YAlgorithm for X6ReductionDef. Problem X reduces to problem Y if you can use an algorithm thatsolves Y to help solve X.Ex 2. [3-collinear reduces to sorting]To solve 3-collinear instance on N points in the plane:•For each point, sort other points by polar angle or slope.-check adjacent triples for collinearityCost of solving 3-collinear. N 2 log N + N 2.cost of sortingcost of reductioninstance I(of X)solution to IAlgorithmfor YAlgorithm for X7‣designing algorithms‣establishing lower bounds‣classifying problems‣intractability8Reduction: design algorithmsDef. Problem X reduces to problem Y if you can use an algorithm thatsolves Y to help solve X.Design algorithm. Given algorithm for Y, can also solve X.Ex.•Element distinctness reduces to sorting.•3-collinear reduces to sorting.•CPM reduces to topological sort. [shortest paths lecture]•h-v line intersection reduces to 1d range searching. [geometric BST lecture]•Baseball elimination reduces to maxflow. [assignment 7]•Burrows-Wheeler transform reduces to suffix sort. [assignment 8]•…Mentality. Since I know how to solve Y, can I use that algorithm to solve X ?programmer’s version: I have code for Y. Can I use it for X?Sorting. Given N distinct integers, rearrange them in ascending order.Convex hull. Given N points in the plane, identify the extreme pointsof the convex hull (in counterclockwise order).Proposition. Convex hull reduces to sorting.Pf. Graham scan algorithm.Cost of convex hull. N log N + N.9Convex hull reduces to sortingconvex hullsorting125143228615343988818419074513546464898854444343421334435312cost of reductioncost of sortingShortest paths on edge-weighted graphs and digraphsProposition. Undirected shortest paths (with nonnegative weights) reduces to directed shortest path.10510121591210154s2356tShortest paths on edge-weighted graphs and digraphsProposition. Undirected shortest paths (with nonnegative weights) reduces to directed shortest path.Pf. Replace each undirected edge by two directed edges.5 101215912 10910415 10151541112125510121591210154s2356t23 5 t5sShortest paths on edge-weighted graphs and digraphsProposition. Undirected shortest paths (with nonnegative weights) reduces to directed shortest path.Cost of undirected shortest paths. E log V + E.51012159121015412cost of shortest paths in digraphcost of reductions2356tCaveat. Reduction is invalid for edge-weighted graphs with negative weights(even if no negative cycles).Remark. Can still solve shortest-paths problem in undirected graphs(if no negative cycles), but need more sophisticated techniques.13Shortest paths with negative weightsts7 –4ts7 –4reduction createsnegative cyclesreduces to weightednon-bipartite matching (!)7 –4Some reductions involving familiar problems14elementdistinctnesssortingconvex hullmedianDelaunaytriangulation2d closestpair2d EuclideanMST2d farthestpaircomputational geometrylinearprogramming(see ORF 307)directed shortest paths(nonnegative)bipartitematching maximum flow arbitrageshortest paths(no neg cycles)undirected shortest paths(nonnegative)baseballeliminationcombinatorial optimization15‣designing algorithms‣establishing lower bounds‣classifying problems‣intractability16Bird's-eye viewGoal. Prove that a problem requires a certain number of steps.Ex. In decision tree model, any compare-based sorting algorithmrequires Ω(N log N) compares in the worst case.Bad news. Very difficult to establish lower bounds from scratch.Good news. Can spread Ω(N log N) lower bound to Y by reducing sorting to Y.assuming cost of reduction is not too highargument must apply to all conceivable algorithmsb < cyesnoa < cyesa < cyes noa c b c a bb a ca b cb < cyes nob c a c b aa < byes nono17Linear-time reductionsDef. Problem X linear-time reduces to problem Y if X can be solved with:•Linear number of standard computational steps.•Constant number of calls to Y.Ex. Almost all of the reductions we've seen so far. [Which ones weren't?]Establish lower bound:•If X takes Ω(N log N) steps, then so does Y.•If X takes Ω(N 2) steps, then so does Y.Mentality.•If I could easily solve Y, then I could easily solve X.•I can’t easily solve X.•Therefore, I can’t easily solve Y.18Lower bound for convex hullProposition. In quadratic decision tree model, any algorithm for sortingN integers requires Ω(N log N) steps.Proposition. Sorting linear-time reduces to convex hull.Pf. [see next slide]Implication. Any ccw-based convex hull algorithm requires Ω(N log N) ops. allows linear or quadratic tests: xi < xj or (xj – xi) (xk – xi) – (xj ) (xj – xi) < 0linear or quadratic testssorting1251432286153439888184190745135464648988544443434213convex hulllower-bound mentality:if I can solve convex hullefficiently, I can sort efficientlyProposition. Sorting
View Full Document
Unlocking...