IITM2012

Question

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?

Comments

no answer :O

Answer 1

Can't we use directed graphs for representing equivalence relations?

Comments

possible. But do we need direction?

---

equivalence relation is symmetric- i.e., if A -> B, then B -> A. So, no need of directed graph. undirected is enough.

---

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? 

---

lets proceed like a research interview :P So, how you compare the efficiency of both union-find and graph approaches for checking equivalence?

---

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(V²) time.
If symmetric, proceed to step 3.
3. Transitive closure can be formed using Warshall's algorithm which takes O(V³) 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(V³) time.

So Overall this makes it O(V³).
I will write the union set part in the next comment :P Not 100% sure for the approach of that yet..
 

---

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..

---

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.

---

Ohh, sorry.. My mistake. Symmetry takes O(V²).. 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.

---

Union-find - how many such data structures are required for an equivalence relation?

---

Dint get you sir,

"Union-find - how many such data structures are required for an equivalence relation?"

---

---

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".

---

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.pdf

Recall 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.
 

---

yes.. Sorry, I was referring to each set. So for each partition we have a set.

---

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..

---

So, time complexity same for disjoint-set and graph?

---

: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..

---

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 :)

---

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(V²) 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..

---

yes, I meant the first case..