Find the union of the sets

union and find algorithms in daa ppt and also form a union for the following sets and how do you find the union of two sets
Dr.AlexanderTyler Profile Pic
Dr.AlexanderTyler,India,Teacher
Published Date:21-07-2017
Your Website URL(Optional)
Comment
ROBERT SEDGEWICK KEVIN WAYNE Algorithms 1.5 UNION-FIND dynamic connectivity ‣ quick find ‣ quick union ‣ Algorithms FOUR TH EDITION improvements ‣ applications ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduSubtext of today’s lecture (and this course) Steps to developing a usable algorithm. Model the problem. Find an algorithm to solve it. Fast enough? Fits in memory? If not, figure out why not. Find a way to address the problem. Iterate until satisfied. The scientific method. Mathematical analysis. 21.5 UNION-FIND dynamic connectivity ‣ quick find ‣ quick union ‣ Algorithms improvements ‣ applications ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduDynamic connectivity problem Given a set of N objects, support two operation: Connect two objects. Is there a path connecting the two objects? connect 4 and 3 connect 3 and 8 0 1 2 3 4 connect 6 and 5 connect 9 and 4 connect 2 and 1 5 6 7 8 9 are 0 and 7 connected? 𐄂 ✔ are 8 and 9 connected? connect 5 and 0 connect 7 and 2 connect 6 and 1 connect 1 and 0 ✔ are 0 and 7 connected? 4A larger connectivity example Q. Is there a path connecting p and q ? p q A. Yes. 5Modeling the objects Applications involve manipulating objects of all types. Pixels in a digital photo. Computers in a network. Friends in a social network. Transistors in a computer chip. Elements in a mathematical set. Variable names in a Fortran program. Metallic sites in a composite system. When programming, convenient to name objects 0 to N – 1. Use integers as array index. Suppress details not relevant to union-find. can use symbol table to translate from site names to integers: stay tuned (Chapter 3) 6Modeling the connections We assume "is connected to" is an equivalence relation: Reflexive: p is connected to p. Symmetric: if p is connected to q, then q is connected to p. Transitive: if p is connected to q and q is connected to r, then p is connected to r. Connected component. Maximal set of objects that are mutually connected. 0 1 2 3 4 5 6 7 0 1 4 5 2 3 6 7 3 connected components 7Implementing the operations Find. In which component is object p ? Connected. Are objects p and q in the same component? Union. Replace components containing objects p and q with their union. 0 1 2 0 1 2 3 3 union(2, 5) 4 5 6 4 5 6 7 7 0 1 4 5 2 3 6 7 0 1 2 3 4 5 6 7 3 connected components 2 connected components 8Union-find data type (API) Goal. Design efficient data structure for union-find. Number of objects N can be huge. Number of operations M can be huge. Union and find operations may be intermixed. public class public class public class UF UF UF initialize union-find data structure UF(int N) with N singleton objects (0 to N – 1) void union(int p, int q) add connection between p and q int find(int p) component identifier for p (0 to N – 1) boolean connected(int p, int q) are p and q in the same component? public boolean connected(int p, int q) return find(p) == find(q); 1-line implementation of connected() 9Dynamic-connectivity client Read in number of objects N from standard input. Repeat: – read in pair of integers from standard input – if they are not yet connected, connect them and print out pair % more tinyUF.txt public static void main(String args) 10 4 3 int N = StdIn.readInt(); 3 8 UF uf = new UF(N); 6 5 while (StdIn.isEmpty()) 9 4 2 1 int p = StdIn.readInt(); 8 9 int q = StdIn.readInt(); 5 0 if (uf.connected(p, q)) 7 2 already connected 6 1 uf.union(p, q); 1 0 StdOut.println(p + " " + q); 6 7 101.5 UNION-FIND dynamic connectivity ‣ quick find ‣ quick union ‣ Algorithms improvements ‣ applications ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduQuick-find eager approach Data structure. if and only if Integer array id of length N. Interpretation: idp is the id of the component containing p. 0 1 2 3 4 5 6 7 8 9 0, 5 and 6 are connected 1, 2, and 7 are connected id 0 1 1 8 8 0 0 1 8 8 3, 4, 8, and 9 are connected 0 1 2 3 4 5 6 7 8 9 12Quick-find eager approach Data structure. Integer array id of length N. Interpretation: idp is the id of the component containing p. 0 1 2 3 4 5 6 7 8 9 id 0 1 1 8 8 0 0 1 8 8 id6 = 0; id1 = 1 Find. What is the id of p? 6 and 1 are not connected Connected. Do p and q have the same id? Union. To merge components containing p and q, change all entries whose id equals idp to idq. 0 1 2 3 4 5 6 7 8 9 after union of 6 and 1 id 1 1 1 8 8 1 1 1 8 8 problem: many values can change 13Quick-find demo 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 id 0 1 2 3 4 5 6 7 8 9 14Quick-find demo 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 id 1 1 1 8 8 1 1 1 8 8Quick-find: Java implementation public class QuickFindUF private int id; public QuickFindUF(int N) id = new intN; set id of each object to itself for (int i = 0; i N; i++) (N array accesses) idi = i; return the id of p public int find(int p) (1 array access) return idp; public void union(int p, int q) int pid = idp; int qid = idq; change all entries with idp to idq for (int i = 0; i id.length; i++) (at most 2N + 2 array accesses) if (idi == pid) idi = qid; 16Quick-find is too slow Cost model. Number of array accesses (for read or write). algorithm initialize union find connected N N 1 1 quick-find order of growth of number of array accesses quadratic 2 Union is too expensive. It takes N array accesses to process a sequence of N union operations on N objects. 17Quadratic algorithms do not scale Rough standard (for now). a truism (roughly) 9 10 operations per second. since 1950 9 10 words of main memory. Touch all words in approximately 1 second. Ex. Huge problem for quick-find. 9 9 10 union commands on 10 objects. 18 Quick-find takes more than 10 operations. 30+ years of computer time time quadratic 64T Quadratic algorithms don't scale with technology. New computer may be 10x as fast. 32T But, has 10x as much memory ⇒ want to solve a problem that is 10x as big. 16T linearithmic With quadratic algorithm, takes 10x as long 8T linear size 1K 2K 4K 8K 181.5 UNION-FIND dynamic connectivity ‣ quick find ‣ quick union ‣ Algorithms improvements ‣ applications ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduQuick-union lazy approach Data structure. Integer array id of length N. keep going until it doesn’t change (algorithm ensures no cycles) Interpretation: idi is parent of i. Root of i is ididid...idi.... 0 1 9 6 7 8 0 1 2 3 4 5 6 7 8 9 2 4 5 id 0 1 9 4 9 6 6 7 8 9 3 parent of 3 is 4 root of 3 is 9 20