Quiz 1 -- Princeton Algorithm

Social network connectivity. Given a social network containing n members and a log file containing m timestamps at which times pairs of members formed friendships, design an algorithm to determine the earliest time at which all members are connected (i.e., every member is a friend of a friend of a friend ... of a friend). Assume that the log file is sorted by timestamp and that friendship is an equivalence relation. The running time of your algorithm should be mlogn or better and use extra space proportional to n.

Hint: union−find.

so it's to find the earliest time there is only one connected components. At the beginning, there are n connected components. When a pair of members formed friendship, and if they are in different connected components , then the number of connected components is subtracted 1. For each union operation , the time complexity is log n ( using weighted union find ). During the union if we find the root of each member is different, we subtract 1 from the number of connected components until it's 1. So at most m union operation. That'll be m log n.  And extra space is the array of length n to maintain the size of each connected components rooted at i.

Union-find with specific canonical element. Add a method 𝚏𝚒𝚗𝚍() to the union-find data type so that 𝚏𝚒𝚗𝚍(𝚒) returns the largest element in the connected component containing i. The operations, 𝚞𝚗𝚒𝚘𝚗(), 𝚌𝚘𝚗𝚗𝚎𝚌𝚝𝚎𝚍(), and 𝚏𝚒𝚗𝚍() should all take logarithmic time or better.

For example, if one of the connected components is {1,2,6,9}, then the 𝚏𝚒𝚗𝚍() method should return 9 for each of the four elements in the connected components.

Hint: maintain an extra array to the weighted quick-union data structure that stores for each root 𝚒 the large element in the connected component containing 𝚒.

Just add an array max of length n to maintain the largest element rooted at i. During the union, if root(p) point to root(q) then max[q] should updated to the max of max[q] and max[p]. find (i) just return max[root(i)]

Successor with delete. Given a set of N integers S={0,1,...,n−1} and a sequence of requests of the following form:

• Remove x from S
• Find the successor of x: the smallest y in S such that y≥x.

design a data type so that all operations (except construction) take logarithmic time or better in the worst case.

Hint: use the modification of the union−find data discussed in the previous question.

This problem can be a variation of the second problem. Say for all the integers with same successor are connected. So we have an array "connected" of length n to indicate the set of integers who have the same successor in S. And connected[i] is initialized to i meaning integer in S has different successor (itself) in S initially.  Meanwhile we have another array "max" of length n. max[i] indicates the max value of the connected components rooted at i.When element i is removed from S, that means a union operation of i and i + 1, because the successor of i is now the successor of i + 1 and successor of all the elements whose successor was i is now the successor of i + 1 too. So  the successor of x is the value of max[root(x)]. One special case needs to be handled is when n-1 is removed. then we mark the max[root(n-1)] as -1 , and when a component with max value as -1 is connected to another component, then the resulted connected component should have max value as -1 too.