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 Sullivan Algorithm Design by va Tardos and Jon Kleinberg Copyright 2005 Addison Wesley Slides by Kevin Wayne modified by Neil Rhodes Computational Tractability 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 Charles Babbage 1864 Analytic Engine schematic 2 Computational Tractability Worst 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 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 Def An algorithm is efficient if it has polynomial running time Justification It really works in practice 3 Why It Matters Run time in nanoseconds Time to solve a problem of size Max size problem solved in one 1 3 N3 10 N2 47 N log2N 48 N 1000 1 3 seconds 10 msec 0 4 msec 0 048 msec 10 000 22 minutes 1 second 6 msec 0 48 msec 100 000 15 days 1 7 minutes 78 msec 4 8 msec million 41 years 2 8 hours 0 94 seconds 48 msec 10 million 41 millennia 1 7 weeks 11 seconds 0 48 seconds second 920 10 000 1 million 21 million minute 3 600 77 000 49 million 1 3 billion hour 14 000 600 000 2 4 trillion 76 trillion day 41 000 2 9 million 50 trillion 1 800 trillion 1 000 100 10 10 N multiplied by 10 time multiplied by Reference More Programming Pearls by Jon Bentley 4 Orders of Magnitude Seconds Equivalent 1 1 second 10 10 seconds 10 2 1 7 minutes 10 3 17 minutes 10 4 2 8 hours 10 5 1 1 days 10 6 1 6 weeks 10 7 3 8 months 10 8 3 1 years 10 9 3 1 decades 10 3 1 centuries 10 forever 10 age of universe 17 Meters Per Second Imperial Units Example 10 10 1 2 in decade Continental drift 10 8 1 ft year Hair growing 10 6 3 4 in day Glacier 10 4 1 2 ft hour Gastro intestinal tract 10 2 2 ft minute Ant 1 2 2 mi hour Human walk 102 220 mi hour Propeller airplane 104 370 mi min Space shuttle 106 620 mi sec Earth in galactic orbit 108 62 000 mi sec 1 3 speed of light Powers of 2 210 thousand 220 million 230 billion Reference More Programming Pearls by Jon Bentley 5 Asymptotic Order of Growth Upper 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 6 Properties Transitivity 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 7 Asymptotic Bounds for Some Common Functions Polynomials 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 can avoid specifying the base assuming it is a constant Logarithms For every x 0 log n O nx log grows slower than every polynomial Exponentials For every r 1 and every d 0 nd O rn every exponential grows faster than every polynomial 8 Linear 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 a1 for i 2 to n if ai max max ai 9 Linearithmic 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 10 Quadratic 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 min x1 x2 2 y1 y2 2 for 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 to take square roots Remark n2 seems inevitable but this is just an illusion Chapter 5 11 Cubic Time O n3 Cubic time Enumerate all triples of elements Set disjointness Given n sets S1 Sn each of which is a subset of 1 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 12 Polynomial Time O nk Time Independent 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 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 Check whether S is an independent set O k2 Number of k element subsets O k2 nk k O nk assuming k is a constant 13 Exponential Time Independent set Given a graph what is maximum size of an independent set O n2 2n solution Enumerate all …