Algorithm Design by Éva Tardos and Jon Kleinberg • Copyright © 2005 Addison Wesley • Slides by Kevin Wayne (modified by Neil Rhodes)Day 2: Basic of Algorithms Analysis"For me, great algorithms are the poetry of computation. Just like verse, they can be terse, allusive, dense, and even mysterious. But once unlocked, they cast a brilliant new light on some aspect of computing." - Francis Sullivan2Computational Tractability Charles Babbage (1864)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 BabbageAnalytic Engine (schematic)3Computational TractabilityWorst case running time. Obtain bound on largest possible running time of algorithm on input of a given size N, and see how this scales with N.Generally captures efficiency in practice.Draconian view, but hard to find effective alternative.Desirable scaling property. When the input size increases by a factor of 2, the algorithm should only slow down by some constant factor C. Def. An algorithm is efficient if it has polynomial running time.Justification. It really works in practice!There exists constants c > 0 and d > 0 such that on every input of size N, its running time is bounded by c Nd steps.4Why It Matters1000Time tosolve aproblemof size10,000100,000million10 million1.3 seconds22 minutes15 days41 years41 millennia9203,60014,00041,0001,000Run time innanoseconds -->1.3 N3secondMax sizeproblemsolvedin oneminutehourday10 msec1 second1.7 minutes2.8 hours1.7 weeks10,00077,000600,0002.9 million10010 N20.4 msec6 msec78 msec0.94 seconds11 seconds1 million49 million2.4 trillion50 trillion10+47 N log2N0.048 msec0.48 msec4.8 msec48 msec0.48 seconds21 million1.3 billion76 trillion1,800 trillion1048 NN multiplied by 10,time multiplied byReference: More Programming Pearls by Jon Bentley5Orders of Magnitude10-10Meters PerSecond10-810-610-410-211021.2 in / decadeImperialUnits1 ft / year3.4 in / day1.2 ft / hour2 ft / minute2.2 mi / hour220 mi / hourContinental driftExampleHair growingGlacierGastro-intestinal tractAntHuman walkPropeller airplane104106108370 mi / min620 mi / sec62,000 mi / secSpace shuttleEarth in galactic orbit1/3 speed of light1Seconds10210310410510610710810910101 secondEquivalent1.7 minutes17 minutes2.8 hours1.1 days1.6 weeks3.8 months3.1 years3.1 decades3.1 centuriesforever1017age ofuniverse210thousand220million230billion. . .10 10 secondsPowersof 2Reference: More Programming Pearls by Jon Bentley6Asymptotic Order of GrowthUpper bounds. T(n) is O(f(n)) if there exist constants c > 0 and n0 ≥ 0 such that for all n ≥ n0 we have T(n) ≤ c · f(n).Lower bounds. T(n) is Ω(f(n)) if there exist constants c > 0 and n0 ≥ 0 such that for all n ≥ n0 we have T(n) ≥ c · f(n).Tight bounds. T(n) is Θ(f(n)) if T(n) is both O(f(n)) and Ω(f(n)).Ex: T(n) = 32n2 + 17n + 32.T(n) is O(n2), O(n3), Ω(n2), Ω(n), and Θ(n2) .T(n) is not O(n), Ω(n3), Θ(n), or Θ(n3), .Slight abuse of notation. T(n) = O(f(n)).Vacuous statement. Any comparison-based sorting algorithm requires at least O(n log n) comparisons.7PropertiesTransitivity. If f = O(g) and g = O(h) then f = O(h).Additivity. If f = O(h) and g = O(h) then f + g = O(h).8Asymptotic Bounds for Some Common FunctionsPolynomials. a0 + a1n + … + adnd is Θ(nd) if ad > 0. Polynomial time. Running time is O(nd) for some constant d independent of the input size n.Logarithms. O(log a n) = O(log b n) for any constants a, b > 0.Logarithms. For every x > 0, log n = O(nx).Exponentials. For every r > 1 and every d > 0, nd = O(rn).every exponential grows faster than every polynomialcan avoid specifying the base, assuming it is a constantlog grows slower than every polynomial9Linear Time: O(n)Linear time. Running time is at most a constant factor times the size of the input. Computing the maximum. Compute maximum of n numbers a1, …, an.max ← a1for i = 2 to n { if (ai > max) max ← ai}10Linearithmic Time: O(n log n)Linearathmic time. Arises in divide-and-conquer algorithms.Sorting. Mergesort and heapsort are sorting algorithms that perform O(n log n) comparisons.Largest empty interval. Given n time-stamps x1, …, xn on which copies of a file arrive at a server, what is largest interval of time when no copies of the 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.11Quadratic Time: O(n2)Quadratic time. Enumerate all pairs of elements.Closest pair of points. Given a list of n points in the plane (x1, y1), …, (xn, yn), find the pair that is closest.O(n2) solution. Try all pairs of points.Remark. Ω(n2) seems inevitable, but this is just an illusion.min ← (x1 - x2)2 + (y1 - y2)2for i = 1 to n { for j = i+1 to n { d ← (xi - xj)2 + (yi - yj)2 if (d < min) min ← d }}don't need totake square rootsChapter 512Cubic Time: O(n3)Cubic time. Enumerate all triples of elements.Set disjointness. Given n sets S1, …, Sn each of which is a subset of1, 2, …, n, is there some pair of these which are disjoint?O(n3) solution. For each pairs of sets, determine if they are disjoint.foreach set Si { foreach other set Sj { foreach element p of Si { determine whether p also belongs to Sj } if (no element of Si belongs to Sj) report that Si and Sj are disjoint }}13Polynomial Time: O(nk) TimeIndependent set of size k. Given a graph, are there k nodes such that no two are joined by an edge?O(nk) solution. Enumerate all subsets of k nodes.Check whether S is an independent set = O(k2).Number of k element subsets = O(k2 nk / k!) = O(nk).foreach subset S of k nodes { check whether S in an independent set if (S is an independent set) report S is an independent set }}assuming k is a constant14Exponential TimeIndependent set. Given a graph, what is maximum size of an independent set?O(n2 2n) solution. Enumerate all subsets.S* ← φforeach subset S of nodes { check whether S in an independent set if (S is largest independent set seen so far) update S* ← S }}Two Key Types of AlgorithmsIterative AlgorithmsRecursive AlgorithmsAlgorithms:Precondition(s): what is true when the algorithm starts–If it isn’t true, the algorithm can do