1Algorithms and Data Structures Princeton University Fall 2005Kevin Wayne2OverviewWhat is COS 226?! Intermediate-level survey course.! Programming and problem solving with applications.! Algorithm: method for solving a problem.! Data structure: method to store information.TopicsortingsearchinggraphsData Structures and Algorithmsquicksort, mergesort, heapsort, radix sortshash table, BST, red-black tree, B-treeDFS, Prim, Kruskal, Dijkstra, Ford-Fulkersonstrings KMP, Rabin-Karp, TST, Huffman, LZWgeometry Graham scan, k-d tree, Voronoi diagramdata types stack, queue, list, union-find, priority queueA misperception: algiros [painful] + arithmos [number].3Impact of Great AlgorithmsInternet. Packet routing, Google, Akamai.Biology. Human genome project, protein folding.Computers. Circuit layout, file system, compilers.Secure communications. Cell phones, e-commerce.Computer graphics. Hollywood movies, video games.Multimedia. CD player, DVD, MP3, JPG, DivX, HDTV.Transportation. Airline crew scheduling, map routing.Physics. N-body simulation, particle collision simulation.Information processing. Database search, data compression.. . ."For me, great algorithms are the poetry of computation.Just like verse, they can be terse, allusive, dense, andeven mysterious. But once unlocked, they cast a brilliantnew light on some aspect of computing." - Francis Sullivan4Why Study Algorithms?Using a computer?! Want it to go faster? Process more data?! Want it to do something that would otherwise be impossible?Algorithms as a field of study.! Old enough that basics are known.! New enough that new discoveries arise.! Burgeoning application areas.! Philosophical implications.5The Usual SuspectsLectures. Kevin Wayne (Kevin)! MW 11-12:20, Bowen 222.Precepts. Harlan Yu (Harlan), Keith Morley (Keith)! T 12:30, Friend 110.! T 3:30, Friend 111.! Clarify programming assignments, exercises, lecture material.! First precept meets 9/20.6Coursework and GradingRegular programming assignments: 45%! Due 11:59pm, starting 9/26.! More details next lecture.Weekly written exercises: 15%! Due at beginning of Thursday lecture, starting 9/22.Exams:! Closed book with cheatsheet.! Midterm. 15%! Final. 25%Staff discretion. Adjust borderline cases.7Course MaterialsCourse web page. http://www.princeton.edu/~cos226! Syllabus.! Exercises.! Lecture slides.! Programming assignments.Algorithms in Java, 3rd edition.! Parts 1-4. (sorting, searching)! Part 5. (graph algorithms)Algorithms in C, 2nd edition.! Strings and geometry handouts.Robert Sedgew ick and Kevin Wayne • Copyright © 2005 • http://www .Pri nceton.EDU/~cos226Union FindReference: Chapter 1, Algorithms in Java, 3rd Edition, Robert Sedgewick.22Network Connectivity in out evidence 3 4 3 4 4 9 4 9 8 0 8 0 2 3 2 3 5 6 5 6 2 9 (2–3–4-9) 5 9 5 9 7 3 7 3 4 8 4 8 5 6 (5-6) 0 2 (2–3-4–8-0) 6 1 6 10 72 3846 5 9123An Example Problem: Network ConnectivityNetwork connectivity.! Nodes at grid points.! Add connections between pairs of nodes.! Is there a path from node A to node B?AB24Union-Find AbstractionWhat are critical operations we need to support?! Objects.! Disjoint sets of objects.! Find: are objects 2 and 9 in the same set?! Union: merge sets containing 3 and 8.0 1 2-3-9 5-6 7 4-80 1 2-3-4-8-9 7 8-40 1 2-3-9 5-6 7 4-8add a connection betweentwo grid pointssubsets of connected grid pointsare two grid points connected?0 1 2 3 4 5 6 7 8 9grid points25Union-Find AbstractionWhat are critical operations we need to support?! Objects.! Disjoint sets of objects.! Find: are two objects in the same set?! Union: replace sets containing two items by their union.Goal. Design efficient data structure for union and find.! Number of operations M can be huge.! Number of objects N can be huge.26ObjectsApplications involve manipulating objects of all types.! Variable name aliases.! Pixels in a digital photo.! Computers in a network.! Web pages on the Internet.! Transistors in a computer chip.! Metallic sites in a composite system.When programming, convenient to name them 0 to N-1.! Details not relevant to union-find.! Integers allow quick-access to object-related info (array indices).28Quick-Find [eager approach]Data structure.! Integer array id[] of size N.! Interpretation: p and q are connected if they have the same id.Find. Check if p and q have the same id.Union. To merge components containing p and q,change all entries with id[p] to id[q]. i 0 1 2 3 4 5 6 7 8 9id[i] 0 1 9 9 9 6 6 7 8 95 and 6 are connected2, 3, 4, and 9 are connectedunion of 3 and 62, 3, 4, 5, 6, and 9 are connected i 0 1 2 3 4 5 6 7 8 9id[i] 0 1 6 6 6 6 6 7 8 6id[3] = 9; id[6] = 63 and 6 not connectedmany values can change29Quick-Find3-4 0 1 2 4 4 5 6 7 8 94-9 0 1 2 9 9 5 6 7 8 98-0 0 1 2 9 9 5 6 7 0 92-3 0 1 9 9 9 5 6 7 0 95-6 0 1 9 9 9 6 6 7 0 95-9 0 1 9 9 9 9 9 7 0 97-3 0 1 9 9 9 9 9 9 0 94-8 0 1 0 0 0 0 0 0 0 06-1 1 1 1 1 1 1 1 1 1 130Quick-Find: Java Implementation1 operationN operationsset id of eachobject to itselfpublic class QuickFind { private int[] id; public QuickFind(int N) { id = new int[N]; for (int i = 0; i < N; i++) id[i] = i; } public boolean find(int p, int q) { return id[p] == id[q]; } public void unite(int p, int q) { int pid = id[p]; for (int i = 0; i < id.length; i++) if (id[i] == pid) id[i] = id[q]; }}31Problem Size and Computation TimeRough standard for 2000.! 109 operations per second.! 109 words of main memory.! Touch all words in approximately 1 second. [unchanged since 1950!]Ex. Huge problem for quick find.! 1010 edges connecting 109 nodes.! Quick-find might take 1020 operations. [10 ops per query]! 3,000 years of computer time!Paradoxically, quadratic algorithms get worse with newer equipment.! New computer may be 10x as fast.! But, has 10x as much memory so problem may be 10x bigger.! With quadratic algorithm, takes 10x as long!33Quick-UnionData structure.! Integer array id[] of size N.! Interpretation: id[x] is parent of x.! Root of x is id[id[id[...id[x]...]]].Find. Check if p and q have the same root.Union. Set the id of q's root to the id of p's root.keep going until it doesn't change i 0 1 2 3 4 5 6 7 8 9id[i] 0 1 9 4 9 6 6 7 8 947350 1 9 6 823's root is 9; 5's root is 63 and 5 are not connected i 0 1 2 3 4 5 6 7 8
View Full Document
Unlocking...