2 A LGORITHM A NALYSIS 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 AM 2 A LGORITHM A NALYSIS computational tractability asymptotic order of growth survey of common running times SECTION 2 1 A 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 3 Brute force Brute force For many nontrivial problems there is a natural brute force search algorithm that checks every possible solution Typically takes 2n time or worse for inputs of size n Unacceptable in practice 4 Polynomial 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 on every input of size n its running time is bounded choose C 2d by c nd primitive computational steps von Neumann 1953 Nash 1955 G del 1956 Cobham 1964 Edmonds 1965 Rabin 1966 5 Polynomial 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 Map graphs in polynomial time Map graphs in polynomial time Q Which would you prefer 20 n100 vs n1 0 02 ln n Mikkel Thorup Department Mikkel Thorup of Computer Science University of Copenhagen Universitetsparken DK 2100 Copenhagen East Denmark Department of Computer Science University of1 Copenhagen mthorup diku dk Universitetsparken 1 DK 2100 Copenhagen East Denmark mthorup diku dk Abstract AbstractChen Grigni and Papadimitriou WADS 97 and STOC 98 have introduced a modified notion of planarity where two Chen Grigni and Papadimitriou WADS 97 and STOC 98 faces are considered adjacent if they share at least one point have introduced a modified notion of planarity where two The corresponding abstract graphs are called map graphs faces are considered adjacent if they share at least one point Chen et al raised the question of whether map graphs can be The corresponding abstract graphs are called map graphs recognized in polynomial time They showed that the decision Figure 1 Large cliques Chen et al raised the question ofproblem whetherismap graphs be in NP and can presented a polynomial time algorithm recognized in polynomial time They showed that the decision Figure 1 Large cliques in maps for the special case where we allow at most 4 faces to intersect problem is in NP and presented a polynomial time algorithm addition the hamantach may have at m in any point if only 3 are allowed to intersect in a point we for the special case where we allow at most 4 faces to intersect touching all three corners In 5 ther get the usual planar graphs addition the hamantach may have at most two triangle faces in any point if only 3 are allowed Chen to intersect in a point we all the different types of large cliques i et al conjectured that map graphs can be recognized touching all three corners In 5 there is a classification of graphs i get the usual planar graphs showed that recognizing map in polynomial time and in this paper their conjecture is settled all the different types of large cliques in maps et al in 5 Chen et al conjectured that map graphs can be recognized recognition canChen be done singly expo affirmatively showed that recognizing map graphs is in NP hence that the in polynomial time and in this paper their conjecture is settled they conjectured that in fact map grap recognition can be done in singly exponential time However affirmatively polynomial time They supported their they conjectured that in fact map graphs can be recognized in that if we allow at most 4 faces to meet 1 Introduction polynomial time They supportedresulting their conjecture by showing map graphs can be recognized that if we allow at most 4 faces tothis meet in any the conject paper wesingle settlepoint the general 1 Introduction Recently Chen Grigni and Papadimitriou 4 graphs 5 suggested resulting map can be recognized in polynomial time In a graph we can decide in polynomial ti the study of a modified notion of planarity basic the framethis paper The we settle general conjecture showing that given The algorithm can easily be modified to Recently Chen Grigni and Papadimitriou 4 5 assuggested work is the same that of planar graphs given a set a graph We weare can decide inof polynomial time if it is a map graph map if it exists the study of a modified notion ofnon overlapping planarity The basic facesframein the plane The each being a disc homeoalgorithm can easily be modified to draw a corresponding 6 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 7 Types of analyses Worst case Running time guarantee for any input of size n Ex Heapsort requires at most 2 n log2 n compares to sort n elements 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 8 Why it matters 9 2 A LGORITHM A NALYSIS computational tractability asymptotic order of growth survey of common running times SECTION 2 2 Big Oh notation
View Full Document
Unlocking...