Princeton Alogorithm COS 226 Wee

union find is also called disjoint set. when people want to check if is there a path connect two point, and the edge is undirected. we can use union find to solve.

image.png

there are a lot of real life example which could be modeled as union find. For example, Friends in a social network, computers in a network, pixels in a digit photo.

when programming, convenient to name objects 0 to N-1. then we can use integers as array index, suppress details not relevant to union find.

the union find set, have 3 features. reflexive, symmetric, transitive.
it expose 3 interface, find, union, connected.

image.png

if we use quick find, we will got O(n) slow union.

image.png

if we use quick union, we will got O(n) slow find. and in union find root is O(n)

image.png

to balance these operation. we have below improvement.

first, weighting

the thought behind it, is to modify quick union to avoid tall trees

image.png

second, path compression

the thought behind it, we can flatten the tree after computing the root of p.

image.png image.png

Quiz analysis

Q1

image.png

Solution: use weighted union find, and for each log from earliest to oldest, union the two people, check if all the union find count is 1.

Q2

image.png

Solution: add extra max array to record in the connected set, what is the max value. so we need to update it when union. we should use max from two set's max number. to find it, first find the root for the set, then get max value from the max array.

Q3

image.png

Solution: use Q2 data structure, when we remove x, we need to union x and x+1, then next time we check x, we can get the maximum in the remove x set until find the max not removed element.

Project Percolation

https://coursera.cs.princeton.edu/algs4/assignments/percolation/specification.php

The hard point, the back-wash.

Teacher introduce the method how to solve the top line and the bottom line have connected. in this method, we need to add two point, one is virtual top point, it take care of the first line, and another is virtual bottom point.
But when we need to check one percolate cell is full or not. there is a question of backwash.

we can see the seven grid which in red circle, should not be full. But it connected with virtual bottom point, and at the same time, virtual bottom point is connected to top virtual point. so the code check they are full.

image.png

how to fix it.

Solution 1. we use 2 union find, one if for check does the system percolate, another is without bottom virtual point check if is full

but the memory usage is twice.
but u can get 100 hundred score by this method.

Bonus

this project have a bonus, if u can only use 1 union find to solve this problem correctly.
so the question become how to use 1 union find to solve the backwash problem.
the hint is take advantage of find and another state.
as previous design, we only use 0 record block site, 1 record open site.

because two point will cause backwash, one point is hard to know if it is percolate. so we need to find a solution how to break one of them.

use second is easier. because backwash is solved. and another is how to know it is percolate without virtual bottom line.
we need to know is there a cell connect any point in bottom line. so when open a block site, we set 1 value, if it bottom line we set 2 value on it.

now the definition of open still is value > 0. and we need to check percolate only need check the root status is 2 or not. so what we need do is when union, if there is a set have 2 parent, we set new parent with 2.

course quiz and project : https://github.com/yixuaz/algorithm4-princeton-cos226