2 votes 2 votes 1. What is equivalence relation? 2. How can u represent equivalence. relation with a data structure? 3. Which data structure? how efficient? How can u test for. equivalence efficiently? Interview Questions data-structures + – Rajesh Pradhan asked Feb 22, 2016 Rajesh Pradhan 1.6k views answer comment Share Follow See 1 comment See all 1 1 comment reply Arjun commented Mar 17, 2016 reply Follow Share no answer :O 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Can't we use directed graphs for representing equivalence relations? SnehaK answered Mar 21, 2016 SnehaK comment Share Follow See all 19 Comments See all 19 19 Comments reply Arjun commented Mar 21, 2016 reply Follow Share possible. But do we need direction? 0 votes 0 votes Arjun commented Mar 21, 2016 reply Follow Share equivalence relation is symmetric- i.e., if A -> B, then B -> A. So, no need of directed graph. undirected is enough. 0 votes 0 votes abhilashpanicker29 commented Mar 21, 2016 reply Follow Share I was wondering if we could use union-find disjoint set data structure. Because, basically equivalence relation can be divided into equivalence classes(or partitions) and partitions can be stored using union-find disjoint set. But is it the most efficient one? 1 votes 1 votes Arjun commented Mar 21, 2016 reply Follow Share lets proceed like a research interview :P So, how you compare the efficiency of both union-find and graph approaches for checking equivalence? 0 votes 0 votes abhilashpanicker29 commented Mar 21, 2016 i edited by abhilashpanicker29 Mar 21, 2016 reply Follow Share Given the ordered pairs of the relations:- A)Graph approach:- We need to check 3 properties 1. Reflexivity 2. Symmetric 3. Transitive We assume adjacency matrix representation, because that will make things easier while taking transpose and transitive closure.. 1. Reflexivity is easy to do - we need to just check the self loops on each element of set(node of graph) - this will take O(V) time for adjacency matrix representation - just need to check A[i,i]=1. If reflexive, proceed to step 2. 2. Symmetric we can do a. First form the transpose of the matrix and check whether transpose is equal to the original matrix. this will take O(V2) time. If symmetric, proceed to step 3. 3. Transitive closure can be formed using Warshall's algorithm which takes O(V3) time.. and we can check whether the original matrix and transitive closure ones are same.. If this also passes then, equivalence relation.. this will take O(V3) time. So Overall this makes it O(V3). I will write the union set part in the next comment :P Not 100% sure for the approach of that yet.. 1 votes 1 votes abhilashpanicker29 commented Mar 21, 2016 reply Follow Share For union set, i am not sure how can we check whether the given relation is equivalence or not.. We cannot represent other relations using union-set method unlike the graph method.. I mean once we know a given relation is equivalence, we can efficiently represent it using the union-set data structure. But to check whether the given relation is equivalence, i think we need to go through the similar procedure given above first.. 0 votes 0 votes Arjun commented Mar 21, 2016 reply Follow Share symmetry requires $O(V^3)$? And guess the question assumes given relation is an equivalence relation. And checking for equivalence should be for a new element. 0 votes 0 votes abhilashpanicker29 commented Mar 21, 2016 i edited by abhilashpanicker29 Mar 21, 2016 reply Follow Share Ohh, sorry.. My mistake. Symmetry takes O(V2).. Will edit that above.. Suppose if we are only concerned with the representing part, given an equivalence relation, then the union-set is good, as it stores minimal data unlike the graph method.. Also, checking which equivalence class an element belongs is much efficient in union set, by just using the Find function - which has amortized time O(α(V)).. We can easily build the whole union-set for the given relation in O(E * α(V)) time (just confirm this once, not 100% sure) But if suppose we are given a set of ordered pairs, and need to check first that it is equivalence relation or not, i think we need to use the procedure i mentioned above first and then convert it to union set for representing. 1 votes 1 votes Arjun commented Mar 21, 2016 reply Follow Share Union-find - how many such data structures are required for an equivalence relation? 0 votes 0 votes abhilashpanicker29 commented Mar 21, 2016 reply Follow Share Dint get you sir, "Union-find - how many such data structures are required for an equivalence relation?" 0 votes 0 votes Arjun commented Mar 21, 2016 reply Follow Share you are considering an equivalence relation. I'm considering a set :) Suppose e consider Integer set and let the relation be "congruent to mod n". 0 votes 0 votes abhilashpanicker29 commented Mar 21, 2016 reply Follow Share For "congruent to mod n" the number of equivalence classes would be n for remainders 0,1,2,...,n-1. You are right, number of sets will be equal to number of equivalence classes.. but what i got confused was "how many data structures" you asked.. http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2012/lecture-notes/MIT6_046JS12_lec16.pdfRecall from Lecture 4 that a disjoint-set data structure is a data structure representing a dynamic collection of sets S = {S1,...,Sr}. Given an element u, we denote by Su the set containing u. The data structure is a collection of sets in itself.. So, data structure would be one only, right. 1 votes 1 votes Arjun commented Mar 21, 2016 reply Follow Share yes.. Sorry, I was referring to each set. So for each partition we have a set. 1 votes 1 votes abhilashpanicker29 commented Mar 21, 2016 reply Follow Share Yup, one set for each partition.. Can be stored either as an array or a linked list.. that might be implementation dependent. if sets represents integers like in the "congruent modulo n", it will be good idea to use arrays.. in other cases linked lists might be useful.. 1 votes 1 votes Arjun commented Mar 21, 2016 reply Follow Share So, time complexity same for disjoint-set and graph? 0 votes 0 votes abhilashpanicker29 commented Mar 21, 2016 reply Follow Share :P Forgot that.. 1. yes for "checking an equivalence relation" part, according to me time complexity would be same.. 2. But for representing the equivalence and using operation on that only such as finding which partition the element belongs, the disjoint-set is more efficient than the graph one.. 1 votes 1 votes Arjun commented Mar 21, 2016 reply Follow Share In a graph representation each element of the set will be a vertex and each equivalent class correspond to a strongly connected component rt? Usually for interviews questions go like this - they tell us answer and take our feedback too :) 0 votes 0 votes abhilashpanicker29 commented Mar 21, 2016 reply Follow Share Again, to make it clear, 1. If we are already given that the input relation is equivalence relation, then the strongly connected component would give the correct partition.. we can find using DFS numbering method - i think it has complexity O(V+E) for adjacency lists, and O(V2) for adjacency matrix, in any case less efficient than the disjoint set DS. 2. but for general case of a relation, this might not be true.. Strongly connected component need not necessarily imply partitions i think.. Take this graph for example.. 1 votes 1 votes Arjun commented Mar 21, 2016 reply Follow Share yes, I meant the first case.. 1 votes 1 votes Please log in or register to add a comment.