DOC PREVIEW
Princeton COS 226 - Reductions

This preview shows page 1-2-3-4-5 out of 16 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Algorithms in Java, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2008·April 30, 2008 7:44:20 AMReductions‣designing algorithms‣establishing lower bounds‣establishing intractability‣classifying problems2Bird’s-eye viewDesiderata. Classify problems according to computational requirements.•Linear: min/max, median, Burrows-Wheeler transform, ...•Linearithmic: sort, convex hull, closest pair, …•Quadratic: •Cubic:•…•Exponential:Frustrating news.Huge number of fundamental problems have defied classification.3Bird’s-eye viewDesiderata. Classify problems according to computational requirements.Desiderata'.Suppose we could (couldn't) solve problem X efficiently.What else could (couldn't) 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.instance I(of X)Algorithm for Xsolution to IAlgorithmfor Yperhaps many calls to Yon problems of different sizes5ReductionDef. 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 integers:•Sort N integers.•Scan through consecutive pairs and check if any are equal.Cost of solving element distinctness. N log N + N.instance I(of X)Algorithm for Xsolution to IAlgorithmfor Y6ReductionDef. 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.-scan through consecutive triples and check if they are collinearCost of solving 3-collinear. N2 log N + N2.instance I(of X)Algorithm for Xsolution to IAlgorithmfor Y7‣designing algorithms‣establishing lower bounds‣establishing intractability‣classifying problems8Reduction: 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.•PERT reduces to topological sort. [see digraph lecture]•h-v line intersection reduces to 1d range searching. [see geometry lecture]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 counter-clockwise order).Proposition. Convex hull reduces to sorting.Pf. Graham scan algorithm.9Convex hull reduces to sortingconvex hullsorting1251432286153439888184190745135464648988544443434213Shortest path on graphs and digraphsProposition. Undirected shortest path (with nonnegative weights) reduces to directed shortest path.s2356t51012159121015410Shortest path on graphs and digraphsProposition. Undirected shortest path (with nonnegative weights) reduces to directed shortest path.Pf. Replace each undirected edge by two directed edges.s2356t51012159121015425 101215912 10910415 10151543 5 t5s11121212Shortest path with negative weightsCaveat. Reduction is invalid in networks with negative weights(even if no negative cycles).Remark. Can still solve shortest path problem in undirected graphs(if no negative cycles), but need more sophisticated techniques.tva7 -4tvs7 -47 -4reduction createsnegative cyclesreduces to weightednon-bipartite matching (!)PRIME. Given an integer x (represented in binary), is x prime?COMPOSITE. Given an integer x, does x have a nontrivial factor?Proposition. PRIME reduces to COMPOSITE.Primality testing13147573952589676412927composite147573952589676412931prime public static boolean isPrime(BigInteger x) { if (isComposite(x)) return false; else return true; }COMPOSITEPRIMEPrimality testingPRIME. Given an integer x (represented in binary), is x prime?COMPOSITE. Given an integer x, does x have a nontrivial factor?Proposition. COMPOSITE reduces to PRIME.14 public static boolean isComposite(BigInteger x) { if (isPrime(x)) return false; else return true; }147573952589676412927composite147573952589676412931primeCOMPOSITEPRIMECaveatPRIME. Given an integer x (represented in binary), is x prime?COMPOSITE. Given an integer x, does x have a nontrivial factor?Proposition. COMPOSITE reduces to PRIME.Proposition. PRIME reduces to COMPOSITE.A possible real-world scenario.•System designer specs the APIs for project.•Programmer A implements isComposite() using isPrime().•Programmer B implements isPrime() using isComposite().•Infinite reduction loop!15whose fault?COMPOSITEPRIMESome reductions16LPelementdistinctnesssortingshortest paths(nonnegative)bipartitematching maximum flow LP (standard form)convex hullmedianfindingarbitrageshortest paths(no neg cycles)VoronoiclosestpairEuclideanMST17‣designing algorithms‣establishing lower bounds‣establishing intractability‣classifying problems18Bird's-eye viewGoal. Prove that a problem requires a certain number of steps.Ex. Ω(N log N) lower bound for sorting.Bad news. Very difficult to establish lower bounds from scratch.Good news. Can establish Ω(N log N) lower bound for Yby reducing sorting to Y.assuming cost of reduction is not too largeargument must apply toall conceivable algorithms125143228615343988818419074513546464898854444343421319Linear-time reductionsDef. Problem X linear-time reduces to problem Y if X can be solved with:•linear number of standard computational steps•one call to YEx. Almost all of the reductions we've seen so far.Q. Which one was not a linear-time reduction?instance I(of X)Algorithm for Xsolution to IAlgorithmfor Y20Linear-time reductionsDef. Problem X linear-time reduces to problem Y if X can be solved with:•linear number of standard computational steps•one call to YEstablish lower bound:•If X takes Ω(N log N) steps, then so does Y.•If X takes Ω(N2) 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.21Lower bound for convex hullFact. In quadratic decision tree model, any algorithm for sortingN integers


View Full Document

Princeton COS 226 - Reductions

Documents in this Course
QUICKSORT

QUICKSORT

14 pages

QUICKSORT

QUICKSORT

55 pages

STRINGS

STRINGS

69 pages

Lecture

Lecture

4 pages

STRINGS

STRINGS

18 pages

Hashing

Hashing

7 pages

MERGESORT

MERGESORT

14 pages

Quicksort

Quicksort

12 pages

Strings

Strings

10 pages

Overview

Overview

15 pages

Hashing

Hashing

13 pages

Mergesort

Mergesort

15 pages

Tries

Tries

13 pages

Final

Final

12 pages

Final

Final

12 pages

Mergesort

Mergesort

13 pages

Final

Final

10 pages

Load more
Download Reductions
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Reductions and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Reductions 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?