What is the purpose of the backtrace() function for question 6.7? My understanding is that it’s supposed to get the minimum equivalence class that it can for the given index, but doesn’t the code under the “// Generate the weakest equivalence relation” comment do the same thing? Is it that it’s more efficient to update the weakest equivalence relation as you go instead of doing it all at the end (much like how path compression makes union-find more efficient)?
Question about 6.7 backtrace() function
Hey John,
The purpose of this problem is to let you solve a very common equivalence problem without the knowledge of disjoint set or union-find knowledge. Therefore, backtrace() is just trying to find the ultimate ancestor of a given index. Of course this can be improved by the idea of union-find. However, it is really hard to devise union-find like algorithm without studying that before. As a result, we just want to demonstrate how to solve this equivalence problem directly.
0 Likes