Report

29-Jan-00 CPSC 212: Data Structures and Algorithms Instructor: Harry Plantinga 29-Jan-00 Computer Science 212 Data Structures and Algorithms The Heart of Computer Science Data structures Study of important algorithms Algorithm analysis Algorithm design techniques Plus GUIs and a GUI toolkit Intelligent systems Course Information: http://cs.calvin.edu/CS/212/ 29-Jan-00 Why study DS & Algorithms? Some problems are difficult to solve and good solutions are known Some “solutions” don’t always work Some simple algorithms don’t scale well Data structures and algorithms make good tools for addressing new problems Why not just get a faster computer? Esthetic beauty! 29-Jan-00 Asymptotic Analysis What does it mean to say that an algorithm has runtime O(n log n)? n: Problem size Big-O: upper bound over all inputs of size n “Ignore constant factor” (why?) “as n grows large” g(n) is said to be O(f(n)) if there exist constants c0 and n0 such that g(n) < c0 f(n) for all n > n0 Most algorithms we study will have runtimes of O(1), O(log n), O(n), O(n log n), O(n2), O(n3), O(2n) 29-Jan-00 Connectivity Building railroads across America Dutch Bingo IC connectivity Telephone network Given an edge from A to B, print it out unless previous edges already connect A and B n edges are added 29-Jan-00 Example 3-4 4-9 8-0 2-3 5-6 2-9 5-9 7-3 4-8 5-6 0-2 6-1 3-4 4-9 8-0 2-3 5-6 [2-3-4-9] 5-9 7-3 4-8 [5-6] [0-8-4-3-2] 6-1 29-Jan-00 Abstract Data Types What is an abstract data type? A collection of data A set of operations on that data What abstract data type do we need? Data: Sets of elements Operations: Find(x) – what set is x in? Union(A,B) – merge sets A and B 29-Jan-00 Algorithm How to solve the railroads problem? For road (x,y) if find(x) != find(y) union(find(x),find(y)) print “x – y” How to implement the Union-Find ADT? 29-Jan-00 Quick Find For each city, keep a pointer to the “capital” of the set Find(x): return the set name for x Runtime: O(1) 10^8 items, 10^9 unions, 100 mips: 10sec Union(A,B): change all sets named A (=Find(x)) in the array to B (=Find(y)) O(n) Runtime: 10^8 items, 10^9 unions, 31 yrs Can we do faster unions? 29-Jan-00 Quick Union To do a Unite(X,Y) (where X and Y are sets), just point X to Y Union runtime: O(1) Find runtime: O(n) Total time for adding n roads? Can we do better? 29-Jan-00 Weighted Union Keep track of the number of cities in each set Insert the smaller set into the larger Runtime for Unite(A,B): O(1) O(?) Runtime for Find(x): What’s the worst-case tree height? 29-Jan-00 Weighted Union Worst case What sequence of inputs gives the tallest trees? How tall are the trees? <= log n (prove by induction) What is the runtime for find? O(log n) What is the runtime for n unions? O(n log n) Better still: average O(1) per union! 29-Jan-00 Path Compression When you do a find, make every city on the path to the “capital” point to the capital Runtime? O(n log* n) 29-Jan-00 What difference does it make? Small problem: use the simplest algorithm Large problem: use the best algorithm! N M 1000 6206 10000 83857 100000 1545119 qf 14 1216 qu 25 4577 wqu 6 91 1071 pc 5 73 1106 A better algorithm is much more advantageous than a faster computer. 29-Jan-00 Lessons Start with simple algorithm Need a good algorithm for big problems Higher level of abstraction (tree) is helpful Strive for worst-case performance guarantees Average-case is better than nothing Identify fundamental abstraction Show me your code—you’ll have to explain your DS Show me your DS—I don’t need to see your code