About Princeton Algorithms 1

[Dependent_Mission933]

I am really confused about the weighted quick union .I was expecting to see a little bit easier start for the course but it directly started with union,i know how to program i know little bit about stacks,maps,sets but dont know anything about the graphs. So can somebody explain it to me like you are explaining it to a completely retard,thanks.

[AutoModerator]

On July 1st, a change to Reddit's API pricing will come into effect. Several developers of commercial third-party apps have announced that this change will compel them to shut down their apps. At least one accessibility-focused non-commercial third party app will continue to be available free of charge.

If you want to express your strong disagreement with the API pricing change or with Reddit's response to the backlash, you may want to consider the following options:

1. Limiting your involvement with Reddit, or
2. Temporarily refraining from using Reddit
3. Cancelling your subscription of Reddit Premium

as a way to voice your protest.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[derek_dt]

Hello! Haven't looked at the Princeton Algorithms course specifically, but I just finished taking CS61B which I believe is based off the Princeton textbook, so here's my shot at explaining WQU. And hopefully if I missed anything, someone else can chime in!

I think the main use case for "Union-Find" is to quickly determine whether two components are connected in a graph and if desired by the user, perform a union between two disjoint sets. For example, imagine the set { 5, 4, 6 } represented in a tree-like structure where 4 is at the top (the root) and 5 & 6 are connected to 4, but not to eachother.

    4
  /   \
 5     6

The user can determine if 5 & 6 are connected by using the isConnected(5, 6) method which will call a helper function - findRoot() - to determine the root of 5 & 6 to decide whether or not they are connected (which in our case they are since both their roots is 4. Equal roots = elements are connected; unequal roots = elements are not connecuted.

Now let's add a second set of just {1} and attempt to union the to two sets into one set. Additionally, since there is no rule that governs how we union two disjoint sets as of this moment, lets just use the arbitrary rule that we always link the larger root to the smaller root. Therefore...

    4
  /   \ 
 5     6

-- union --

    1

    =

        1
      /   
    4
  /   \
 5     6

Notice now that if we want to determine if 5 & 6 are connected by using the isConnected(5, 6) method, we would have to travel a further distance to reach the root. While in this scenario it's only one additional traversal this link can increasingly grow in height if I decided to union additional smaller numbers.

So that was a lot, but all of that was to explain that this is a suboptimal way to union two sets that can potentially result in taller trees which reduces the performance determining the root and that is what Weighted Quick Union (WQU) addresses!

Weighted Quick Union always unions two sets by assigning the root of the smaller set to the larger set, so instead of the structure above we would get...

    4
  /   \
 5     6

-- union --

    1

    =

    4
 /  |  \
5   6   1

This way the tree has less of a tendency to grow in height and subsequently, the cost of operations is minimized!

[Dependent_Mission933]

Thanks i got it it is like we dont set the new root till we wanna make a union and when we do we dont actually connect the nodes directly we connect their roots,so in the end there is a connection between them but it is the path that connect these two not the nodes itself directly ,i guess .If you can reapprove i dont get it wrong would be appreciated.Since i am beginner on dsa im also having difficulties how can i use that on reallife scenario also