Topics in Algorithm Design - Lecture Notes for COMP 5703 Anil Maheshwari School of Computer Science Carleton University [email protected] November 9, 2015 2 Contents 1 Preliminaries 1 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Model of Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Asymptotics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3.1 O-notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3.2 Ω-notation (big-Omega) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3.3 Θ-notation (Big-Theta) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 How to analyze Recurrences? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.5 Strassen’s Matrix Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.5.1 Matrix Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.5.2 Strassen’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.6 Elementary stuff from probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.6.1 Chernoff Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2 Introduction to Graphs and their Representation 17 2.1 Introduction and Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2 How to represent graphs in a computer? . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3 Graph traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.3.1 Breadth-first search (BFS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.4 Topological sort and DFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.4.1 Topological Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.4.2 Depth First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.4.3 Computation of low(v). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.5 Biconnectivity. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.5.1 Equivalence Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.5.2 Biconnectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3 Minimum Spanning Trees 33 3.1 Minimum Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.2 Kruskal’s Algorithm for MST . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.3 Prim’s MST algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.4 Randomized Algorithms for Minimum Spanning Trees . . . . . . . . . . . . . . . . . 37 3.4.1 Boruvka’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 i 3.4.2 Heavy Edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.4.3 Randomized Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.5 MST Verification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.5.1 Overview of verification algorithms . . . . . . . . . . . . . . . . . . . . . . . . 41 3.5.2 Koml´os’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.5.3 Dixon et al.’s Technique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.5.4 King’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.5.5 Hagerup’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.5.6 Putting it all together . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.6 Bibliographic Notes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4 Network Flow 53 4.1 What is a Flow Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.2 Ford and Fulkerson’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.3 Edmonds-Karp Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.4 Applications of Network Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 5 Separators in a Planar Graph 63 5.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5.2 Proof of the Planar Separator Theorem . . . . . . . . . . . . . . . . . . . . . . . . . 64 5.3 Generalizations of the Planar Separator Theorem . . . . . . . . . . . . . . . . . . . . 67 5.3.1 Weighted Separators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 5.3.2 r-Divisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 5.3.3 Edge Separators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 6 Lowest Common Ancestor 73 6.1 LCA RMQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 → 6.2 Range Minima Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 6.2.1 A naive O(n2) algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 6.2.2 An O(nlogn) algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 6.2.3 An O(n) algorithm with 1 property . . . . . . . . . . . . . . . . . . . . . . 75 ± 6.3 RMQ LCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 → 6.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 6.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 7 Locality-Sensitive Hashing 79 7.1 Similarity of Documents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 7.2 Similarity-Preserving Summaries of Sets . . . . . . . . . . . . . . . . . . . . . . . . . 80 7.3 LSH for Minhash Signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 7.4 Theory of Locality Sensitive Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 84 7.5 LSH Families . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 7.5.1 Hamming Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 7.5.2 Cosine Distance. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 ii 7.5.3 Euclidean Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 7.5.4 Fingerprint Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 7.5.5 Image Similarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 7.6 Bibliographic Notes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 7.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 8 Dimensionality Reduction 97 8.1 Preliminaries: Metric spaces and embeddings . . . . . . . . . . . . . . . . . . . . . . 97 8.2 Embeddings into L -normed spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 ∞ 8.3 Embeddings into L -normed spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 p 8.4 Johnson and Lindenstrauss Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 8.5 Applications of Metric Embeddings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 8.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 9 Second moment method with applications 103 9.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 9.2 Cliques in a random graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 9.3 Thresholds for Random Geometric Graphs . . . . . . . . . . . . . . . . . . . . . . . . 106 9.3.1 The threshold for having a connected subgraph on k points . . . . . . . . . . 107 9.3.2 The threshold for G(n,r) to be plane. . . . . . . . . . . . . . . . . . . . . . . 112 9.3.3 The threshold for G(n,r) to be planar . . . . . . . . . . . . . . . . . . . . . . 115 9.3.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 9.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 10 Stable Matchings 117 10.1 Stable Marriages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 10.2 Hospitals/Residents (College Admissions) . . . . . . . . . . . . . . . . . . . . . . . . 120 10.3 Stable Roommates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 10.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 11 Additional Exercises 131 11.1 Random Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 iii Preface + Acknowledgments These notes extensively use material from the course notes of Lars Arge, David Mount, COMP 2805/3803 Notes of myself and Michiel Smid [69], CLRS book [21], Knuth’s Art of Computer Programming [61], Kleinberg and Tardos Algorithms book [60], Ullman et al’s book on Algorithms for Massive Data Sets [85]. These notes are updated occasionally. A substantial update was done in the Fall Term of 2013. Chapters on elementary probability, locality sensitive hashing, dimensionality reduction, and several exercises have been added. Moreover, as part of the offering of COMP 5703 in the Fall of 2013, several students have contributed significantly. Gregory Bint updated the chapter on the Minimum Spanning Trees, and has added a completely new Section 3.5 on the Spanning Tree Verification. Alexis Beingessner has provided Section 5.3 on extension of the planar separator theorem. Andrew Wylie has updated the chapter on Locality Sensitive Hashing and has added a Section 7.5.5 on Image Similarities and provided an extensive bibliography on locality sensitive hashing and its applications. Michael St. Jules has provided an entire chapter on Stable Matchings. I thank the Fall 2013 batch of COMP 5703 for providing valuable contributions. In Fall 2015 term I started to work on the Chapter on Second Moment Method. The addition of this chapter was inspired by a comment from one of the referees of our paper [8] in ALGOSENSORS 2015, where he/she mentioned that the paper is a good introduction to the Second Moment Method at graduate level. So I have pasted the whole paper in that chapter and added a section on Cliques. Over time, this chapter will evolve. I have used parts of this material for the graduate course COMP 5703 at Carleton. The aim of these notes is mainly to summarize the discussion in the lectures. They are not designed as stand alone chapters or a comprehensive coverage of a topic. The exercises are from numerous sources and most of them have been asked in either an exam or in an assignment! Since these chapters have been written over time, and many of the TeX tools weren’t available in olden times, you will see that the initial chapters don’t have elegant figures or texts. Hopefully, volunteers in future will modernize this part! If you spot any errors, or have suggestion which can help me to improve, I will be glad to hear them. If you wish to add material to these notes, including exercises, please do get in touch. Thanks in advance! Anil Maheshwari [email protected] iv Chapter 1 Preliminaries 1.1 Introduction • Class is about designing and analyzing algorithms – Algorithm: ∗ Mis-spelled logarithm!. ∗ The first most popular algorithm is the Euclid’s algorithm for computing the GCD of two numbers. ∗ A well-defined procedure that transfers an input to an output. ∗ Not a program (but often specified like it): An algorithm can often be implemented in several ways. ∗ Knuth’s, Art of Computer Programming, vol.1, is a good resource on the history of algorithms!. He says that an algorithm is a finite set of rules that gives a sequence of operations for solving a specific type of problem. Algorithm has five important features: Finiteness: must terminate after finite number of steps. Definiteness: each step is precisely described. Input: algorithm has zero or more inputs. Output: has at least one output!. Effectiveness: Each operation should be sufficiently basic such that they can be done in finite amount of time using pencil and paper. – Design: The focus of this course is on how to design good algorithms and how to analyze their efficiency. We will study methods/ideas/tricks for developing fast and efficient algorithms. – Analysis: Abstract/mathematical comparison of algorithms (without actually imple- menting, prototyping and testing them). • This course will require proving the correctness of algorithms and analyzing the algorithms. Therefore MATH is the main tool. Math is needed in three ways: – Formal specification of problem – Analysis of correctness 1 – Analysis of efficiency (time, memory use,...) Pleasereviewmathematicalinduction,whatisaproof?, logarithms, sumofseries,elementary number theory, permutations, factorials, binomial coefficients, harmonic numbers, Fibonacci numbers and generating functions [Knuth vol 1. or his book Concrete Mathematics is an excellent resource]. • Hopefully the course will show that algorithms matter! 1.2 Model of Computation • Predict the resources used by the algorithm: running time and the space. • To analyze the running time of an algorithm, we need a mathematical model of a computer: Random-access machine (RAM) model: – Memory consists of an infinite array of cells. – Eachcellcanstoreatmostonedataitem(bit,byte, a record, ..). – Any memory cell can be accessed in unit time. – Instructions are executed sequentially – All basic instructions take unit time: ∗ Load/Store ∗ Arithmetic’s (e.g. +, , ,/) − ∗ ∗ Logic (e.g. >) • Running time of an algorithm is the number of RAM instructions it executes. • RAM model is not realistic, e.g. – memory is finite (even though we often imagine it to be infinite when we program) – not all memory accesses take the same time (cache, main memory, disk) – not all arithmetic operations take the same time (e.g. multiplications are expensive) – instruction pipelining – other processes • But RAM model often is enough to give relatively realistic results (if we don’t cheat too much). 1.3 Asymptotics We do not want to compute a detailed expression of the run time of the algorithm, but rather will like to get a feel of what it is like? We will like to see the trend - i.e. how does it increase when the size of the input is increased - is it linear in the size of the input? or quadratic? or exponential? 2 or who knows? The asymptotics essentially capture the rate of growth of the underlying functions describing the run-time. Asymptotic analysis assumes that the input size is large (since we are interested how the running time increases when the problem size grows) and ignores the constant factors (which are usually dependent on the hardware, programming smartness or tricks, compile- time-optimizations). David Mount suggests the following simple definitions based on the limits for functions describ- ing the running time of algorithms. We will describe the formal definitions from [21] later. Let f(n) and g(n) be two positive functions of n. What does it mean when we say that both f and g grow at roughly the same rate for large n (ignoring the constant factors), i.e. f(n) lim = c, n→∞ g(n) where c is a constant and is neither 0 or . We say that f(n) θ(g(n)), i.e. they are ∞ ∈ asymptotically equivalent. What about f(n) does not grow significantly faster than g(n) or grows significantly faster? Here is the table of definitions from David Mount. Asymptotic Form Relationship Definition f(n) f(n) Θ(g(n)) f(n) g(n) 0 < lim < ∈ ≡ n→∞ g(n) ∞ f(n) f(n) O(g(n)) f(n) g(n) 0 lim < ∈ ≤ ≤ n→∞ g(n) ∞ f(n) f(n) Ω(g(n)) f(n) g(n) 0 < lim ∈ ≥ n→∞ g(n) f(n) f(n) o(g(n)) f(n) < g(n) lim = 0 ∈ n→∞ g(n) f(n) f(n) ω(g(n)) f(n) > g(n) lim = ∈ n→∞ g(n) ∞ Example: T(n) = (cid:80)n x2 Θ(n3). Why? x=1 ∈ T(n) (n3+3n2+2n)/6 lim = lim = 1/6, n→∞ n3 n→∞ n3 and 0 < 1/6 < . ∞ Just for fun show that T(n) O(n4) or T(n) = n3/3+O(n2). ∈ 1.3.1 O-notation O(g(n)) = f(n) : c,n > 0 such that f(n) cg(n) n n 0 0 { ∃ ≤ ∀ ≥ } • O( ) is used to asymptotically upper bound a function. · • O( )isusedtoboundworst-caserunningtime(seeFigure · 1.1). • Examples: – 1/3n2 3n O(n2) because 1/3n2 3n cn2 if c 1/3 3/n which holds for c = 1/3 − ∈ − ≤ ≥ − and n > 1. – Let p(n) = (cid:80)d a ni be a polynomial of degree d and assume that a > 0. Then i=0 i d p(n) O(nk), where k d is a constant. What are c and n for this? 0 ∈ ≥ 3 cg(n) f(n) n 0 Figure 1.1: Illustration of O() notation. • Note: – When we say “the running time is O(n2)”, we mean that the worst-case running time is O(n2) — best case might be better. – We often abuse the notation: ∗ We write f(n) = O(g(n)) instead of f(n) O(g(n))! ∈ ∗ We often use O(n) in equations: e.g. 2n2 +3n+1 = 2n2 +O(n) (meaning that 2n2+3n+1 = 2n2+f(n) where f(n) is some function in O(n)). ∗ We use O(1) to denote a constant. 1.3.2 Ω-notation (big-Omega) Ω(g(n)) = f(n) : c,n > 0 such that cg(n) f(n) n n 0 0 { ∃ ≤ ∀ ≥ } • Ω( ) isusedto asymptoticallylower bounda function(see · Figure 1.2). • Examples: – 1/3n2 3n = Ω(n2) because 1/3n2 3n cn2 if c 1/3 3/n which is true if c = 1/6 − − ≥ ≤ − and n > 18. – Let p(n) = (cid:80)d a ni be a polynomial of degree d and assume that a > 0. Then i=0 i d p(n) Ω(nk), where k d is a constant. What are c and n for this? 0 ∈ ≤ – Prove or disprove: g(n) = Ω(f(n)) if and only if f(n) = O(g(n)). • Note: – When we say “the running time is Ω(n2)”, we mean that the best case running time is Ω(n2) — the worst case might be worse. 4