Algorithm analysis and design ppt

algorithm analysis and design lecture notes ppt and advanced algorithms and data structures pdf
Dr.AlexanderTyler Profile Pic
Dr.AlexanderTyler,India,Teacher
Published Date:21-07-2017
Your Website URL(Optional)
Comment
2. ALGORITHM ANALYSIS computational tractability ‣ asymptotic order of growth ‣ survey of common running times ‣ Lecture slides by Kevin Wayne Copyright © 2005 Pearson-Addison Wesley Copyright © 2013 Kevin Wayne http://www.cs.princeton.edu/wayne/kleinberg-tardos Last updated on Sep 8, 2013 6:19 AMA strikingly modern thought “ As soon as an Analytic Engine exists, it will necessarily guide the future course of the science. Whenever any result is sought by its aid, the question will arise—By what course of calculation can these results be arrived at by the machine in the shortest time? ” — Charles Babbage (1864) how many times do you have to turn the crank? Analytic Engine 3Brute force Brute force. For many nontrivial problems, there is a natural brute-force search algorithm that checks every possible solution. n Typically takes 2 time or worse for inputs of size n. Unacceptable in practice. 4Polynomial running time Desirable scaling property. When the input size doubles, the algorithm should only slow down by some constant factor C. Def. An algorithm is poly-time if the above scaling property holds. There exists constants c 0 and d 0 such that d choose C = 2 on every input of size n, its running time is bounded d by c n primitive computational steps. Cobham von Neumann Nash Gödel Edmonds Rabin (1964) (1953) (1955) (1956) (1965) (1966) 5Polynomial running time We say that an algorithm is efficient if has a polynomial running time. Justification. It really works in practice In practice, the poly-time algorithms that people develop have low constants and low exponents. Breaking through the exponential barrier of brute force typically exposes some crucial structure of the problem. Exceptions. Some poly-time algorithms do have high constants and/or exponents, and/or are useless in practice. Mapgraphs inpolynomialtime Mapgraphs inpolynomialtime MikkelThorup Department ofComputer Science,University ofCopenhagen MikkelThorup Universitetsparken1,DK-2100Copenhagen East,Denmark 100 1 + 0.02 ln n Department ofComputer Science,University ofCopenhagen Q. Which would you prefer 20 n vs. n ? mthorupdiku.dk Universitetsparken1,DK-2100Copenhagen East,Denmark mthorupdiku.dk Abstract Abstract Chen,Grigni,andPapadimitriou(WADS’97andSTOC’98) have introduced a modified notion of planarity, where two Chen,Grigni,andPapadimitriou(WADS’97andSTOC’98) faces areconsideredadjacent if they shareat least one point. have introduced a modified notion of planarity, where two The corresponding abstract graphs are called map graphs. faces areconsideredadjacent if they shareat least one point. Chenet.al. raisedthe questionofwhethermapgraphs canbe The corresponding abstract graphs are called map graphs. recognizedin polynomialtime. Theyshowedthat thedecision Figure 1. Large cliques inmaps Chenet.al. raisedthe questionofwhethermapgraphs canbe problem is in NP and presenteda polynomial time algorithm recognizedin polynomialtime. Theyshowedthat thedecision Figure 1. Large cliques inmaps forthespecialcasewhereweallowatmost4facestointersect problem is in NP and presenteda polynomial time algorithm addition, the hamantach may have at most two triangle faces inany point—if only3 areallowedtointersectin apoint, we forthespecialcasewhereweallowatmost4facestointersect touching all three corners. In 5 there is a classification of getthe usualplanar graphs. addition, the hamantach may have at most two triangle faces inany point—if only3 areallowedtointersectin apoint, we allthedifferenttypesoflargecliquesinmaps. Chenet.al.5 Chenet.al.conjecturedthatmapgraphscanberecognized touching all three corners. In 5 there is a classification of getthe usualplanar graphs. showed that recognizing map graphs is in NP, hence that the inpolynomialtime,andinthispaper,theirconjectureissettled allthedifferenttypesoflargecliquesinmaps. Chenet.al.5 Chenet.al.conjecturedthatmapgraphscanberecognized recognitioncanbe doneinsinglyexponentialtime. However, affirmatively. showed that recognizing map graphs is in NP, hence that the inpolynomialtime,andinthispaper,theirconjectureissettled theyconjecturedthat,infact,mapgraphscanberecognizedin recognitioncanbe doneinsinglyexponentialtime. However, affirmatively. polynomialtime. Theysupportedtheirconjecturebyshowing theyconjecturedthat,infact,mapgraphscanberecognizedin thatifweallowatmost4facestomeetinanysinglepoint,the 1.Introduction polynomialtime. Theysupportedtheirconjecturebyshowing resultingmapgraph6 scanberecognizedinpolynomialtime. In thatifweallowatmost4facestomeetinanysinglepoint,the 1.Introduction thispaper,wesettlethegeneralconjecture,showingthatgiven RecentlyChen,Grigni,andPapadimitriou4,5suggested resultingmapgraphscanberecognizedinpolynomialtime. In agraph,wecandecideinpolynomialtimeifitisamapgraph. the study of a modified notion of planarity. The basic frame- thispaper,wesettlethegeneralconjecture,showingthatgiven Thealgorithmcaneasilybemodifiedtodrawacorresponding RecentlyChen,Grigni,andPapadimitriou4,5suggested workisthesameasthatofplanargraphs. Wearegivenasetof agraph,wecandecideinpolynomialtimeifitisamapgraph. mapifitexists. the study of a modified notion of planarity. The basic frame- non-overlapping faces in theplane,Th each ealgbei orintghm a di casncehom asilyeo- bemodifiedtodrawacorresponding workisthesameasthatofplanargraphs. Wearegivenasetof morphism. By non-overlapping,wma empeiafnitthexatisttw s.ofacesmay non-overlapping faces in theplane, eachbeinga dischomeo- Mapcoloring Itshouldbenotedthatcoloringofmapgraphs only intersectin their boundaries. The plane may or may not morphism. By non-overlapping,wemeanthattwofacesmay datesbacktoOreandPlummerin19698,thatis,theywanted becompletelycoveredbythefaces. Atraditionalplanargraph Mapcoloring Itshouldbenotedthatcoloringofmapgraphs only intersectin their boundaries. The plane may or may not tocolorthefacessothatanytwointersectingfacesgotdifferent is obtained as follows. The vertices are the faces, and two datesbacktoOreandPlummerin19698,thatis,theywanted becompletelycoveredbythefaces. Atraditionalplanargraph colors. Foranaccountofcolorfulhistory,thereaderisreferred faces are neighbors if their intersection contains a non-trivial tocolorthefacessothatanytwointersectingfacesgotdifferent is obtained as follows. The vertices are the faces, and two to 7, 2.5. In particular, the history provides ananswer to a curve. Chen et.al.4, 5 suggestedsimplifying the definition, colors. Foranaccountofcolorfulhistory,thereaderisreferred faces are neighbors if their intersection contains a non-trivial problemofChenet.al. 5: ifatmost4facesmeetinanysingle by saying that two faces are neighbors if and only if they in- to 7, 2.5. In particular, the history provides ananswer to a curve. Chen et.al.4, 5 suggestedsimplifying the definition, point,canwecolorthemapwith6colors? Itisstraightforward tersect in at least one point. They called the resulting graphs problemofChenet.al. 5: ifatmost4facesmeetinanysingle by saying that two faces are neighbors if and only if they in- toseethattheresultinggraphsare1-planar,meaningthatthey “planarmapgraphs”. Herewewilljustcallthemmapgraphs. point,canwecolorthemapwith6colors? Itisstraightforward tersect in at least one point. They called the resulting graphs canbedrawnintheplanesuchthateachedgeiscrossedbyat Note that there are non-planar map graphs, for as illustrated toseethattheresultinggraphsare1-planar,meaningthatthey “planarmapgraphs”. Herewewilljustcallthemmapgraphs. mostoneotheredge. Alreadyin1965,Ringel9conjectured in Figure 1, map graphs can contain arbitrarily large cliques. canbedrawnintheplanesuchthateachedgeiscrossedbyat Note that there are non-planar map graphs, for as illustrated that all1-planar graphs canbe coloredwith 6 colors,and this We shall refer to the first type of clique as a flower with the mostoneotheredge. Alreadyin1965,Ringel9conjectured in Figure 1, map graphs can contain arbitrarily large cliques. conjecture wassettled in 1984 by Borodin 2, so the answer petals intersecting in a center.Thesecondisa hamantash that all1-planar graphs canbe coloredwith 6 colors,and this We shall refer to the first type of clique as a flower with the toChenet.al.’s problemis: yes. basedon three distinct corner points.Eachofthethreepairs conjecture wassettled in 1984 by Borodin 2, so the answer petals intersecting in a center.Thesecondisa hamantash of corner points is connected by a side of parallel faces.In toChenet.al.’s problemis: yes. basedon three distinct corner points.Eachofthethreepairs Map metrics The shortest path metrics of map graphs are Most ofthis workwasdonewhiletheauthor visitedMIT. of corner points is connected by a side of parallel faces.In Chen et.al.calledflowersforpizzas, but“flower”seems morenatural. commonly used in prizing systems,where you pay for cross- Map metrics The shortest path metrics of map graphs are Most ofthis workwasdonewhiletheauthor visitedMIT. Chen et.al.calledflowersforpizzas, but“flower”seems morenatural. commonly used in prizing systems,where you pay for cross-Worst-case analysis Worst case. Running time guarantee for any input of size n. Generally captures efficiency in practice. Draconian view, but hard to find effective alternative. Exceptions. Some exponential-time algorithms are used widely in practice because the worst-case instances seem to be rare. simplex algorithm Linux grep k-means algorithm 7Types of analyses Worst case. Running time guarantee for any input of size n. Ex. Heapsort requires at most 2 n log n compares to sort n elements. 2 Probabilistic. Expected running time of a randomized algorithm. Ex. The expected number of compares to quicksort n elements is 2n ln n. Amortized. Worst-case running time for any sequence of n operations. Ex. Starting from an empty stack, any sequence of n push and pop operations takes O(n) operations using a resizing array. Average-case. Expected running time for a random input of size n. Ex. The expected number of character compares performed by 3-way radix quicksort on n uniformly random strings is 2n ln n. Also. Smoothed analysis, competitive analysis, ... 8Why it matters 92. ALGORITHM ANALYSIS computational tractability ‣ asymptotic order of growth ‣ survey of common running times ‣ SECTION 2.2Big-Oh notation Upper bounds. T(n) is O( f (n)) if there exist constants c 0 and n ≥ 0 0 such that T(n) ≤ c · f (n) for all n ≥ n . 0 c · f (n) 2 Ex. T(n) = 32n + 17n + 1. T(n) 2 choose c = 50, n = 1 0 T(n) is O(n ). 3 T(n) is also O(n ). T(n) is neither O(n) nor O(n log n). n n 0 2 Typical usage. Insertion makes O(n ) compares to sort n elements. T(n) limsup . Alternate definition. T(n) is O( f (n)) if f(n) n 11Notational abuses Equals sign. O( f (n)) is a set of functions, but computer scientists often write T(n) = O( f (n)) instead of T(n) ∈ O( f (n)). 3 2 Ex. Consider f (n) = 5n and g (n) = 3n . 3 We have f (n) = O(n ) = g(n). Thus, f (n) = g(n). Domain. The domain of f (n) is typically the natural numbers 0, 1, 2, … . Sometimes we restrict to a subset of the natural numbers. Other times we extend to the reals. Nonnegative functions. When using big-Oh notation, we assume that the functions involved are (asymptotically) nonnegative. Bottom line. OK to abuse notation; not OK to misuse it. 12Big-Omega notation Lower bounds. T(n) is Ω( f (n)) if there exist constants c 0 and n ≥ 0 0 such that T(n) ≥ c · f (n) for all n ≥ n . 0 T(n) 2 Ex. T(n) = 32n + 17n + 1. c · f (n) 2 choose c = 32, n = 1 0 T(n) is both Ω(n ) and Ω(n). 3 3 T(n) is neither Ω(n ) nor Ω(n log n). n n 0 Typical usage. Any compare-based sorting algorithm requires Ω(n log n) compares in the worst case. Meaningless statement. Any compare-based sorting algorithm requires at least O(n log n) compares in the worst case. 13Big-Theta notation Tight bounds. T(n) is Θ( f (n)) if there exist constants c 0, c 0, and n ≥ 0 1 2 0 such that c · f (n) ≤ T(n) ≤ c · f (n) for all n ≥ n . 1 2 0 c · f (n) 2 T(n) 2 Ex. T(n) = 32n + 17n + 1. c · f (n) 1 2 choose c = 32, c = 50, n = 1 1 2 0 T(n) is Θ(n ). 3 T(n) is neither Θ(n) nor Θ(n ). n n 0 Typical usage. Mergesort makes Θ(n log n) compares to sort n elements. 14Useful facts f(n) lim = c 0 Proposition. If , then f (n) is Θ(g(n)). n g(n) Pf. By definition of the limit, there exists n such such that for all n ≥ n 0 0 1 f(n) c 2c 2 g(n) Thus, f (n) ≤ 2 c g(n) for all n ≥ n , which implies f (n) is O(g(n)). 0 Similarly, f (n) ≥ ½ c g(n) for all n ≥ n , which implies f (n) is Ω(g(n)). 0 f(n) Proposition. If , then f (n) is O(g(n)). lim =0 n g(n) 15Asymptotic bounds for some common functions d d Polynomials. Let T(n) = a + a n + … + a n with a 0. Then, T(n) is Θ(n ). 0 1 d d d a +a n+...+a n 0 1 d lim = a 0 d Pf. d n n no need to specify base Logarithms. Θ(log n) is Θ(log n) for any constants a, b 0. a b (assuming it is a constant) d Logarithms and polynomials. For every d 0, log n is O(n ). d n Exponentials and polynomials. For every r 1 and every d 0, n is O(r ). d n lim =0 Pf. n n r 16Big-Oh notation with multiple variables Upper bounds. T(m, n) is O( f (m, n)) if there exist constants c 0, m ≥ 0, 0 and n ≥ 0 such that T(m, n) ≤ c · f (m, n) for all n ≥ n and m ≥ m . 0 0 0 2 3 Ex. T(m, n) = 32mn + 17mn + 32n . 2 3 3 T(m, n) is both O(mn + n ) and O(mn ). 3 2 T(m, n) is neither O(n ) nor O(mn ). Typical usage. Breadth-first search takes O(m + n) time to find the shortest path from s to t in a digraph. 172. ALGORITHM ANALYSIS computational tractability ‣ asymptotic order of growth ‣ survey of common running times ‣ SECTION 2.4Linear time: O(n) Linear time. Running time is proportional to input size. Computing the maximum. Compute maximum of n numbers a , …, a . 1 n max ← a 1 for i = 2 to n if (a max) i max ← a i 19Linear time: O(n) Merge. Combine two sorted lists A = a , a , …, a with B = b , b , …, b into sorted 1 2 n 1 2 n whole. i = 1, j = 1 while (both lists are nonempty) if (a ≤ b ) append a to output list and increment i i j i else(a ≤ b )append b to output list and increment j i j j append remainder of nonempty list to output list Claim. Merging two lists of size n takes O(n) time. Pf. After each compare, the length of output list increases by 1. 20Linearithmic time: O(n log n) O(n log n) time. Arises in divide-and-conquer algorithms. Sorting. Mergesort and heapsort are sorting algorithms that perform O(n log n) compares. Largest empty interval. Given n time-stamps x , …, x on which copies of a 1 n file arrive at a server, what is largest interval when no copies of file arrive? O(n log n) solution. Sort the time-stamps. Scan the sorted list in order, identifying the maximum gap between successive time-stamps. 21