Given an int N specifying the total number of sites (indexed 0 through N - 1), the dynamic connectivity problem specifies the following API describing the basic operations that we need. connect(int p, int q): Add a connection between sites p and g. isConnected (int p, int q): Returns true if and only if sites p and q are in the same component. The connect and isConnected operations model an equivalence relation, which means that it is: Reflexive: p is connected to p. Symmetric: If p is connected to q, then q is connected to p. Transitive: If p is connected to q and q is connected to r, then p is connected to r. You may introduce 2 arrays of size N. Hint: Consider initializing each index of an array to the value of the corresponding site, e.g. initialize array index 17 to the value 17. For each of the following conditions, give a crisp and concise English description of a dynamic connectivity algorithm that meets the requirements. 1 Runtime for connect is in O(N) while isConnected is in 0(1). 2 Runtime for connect is in O(log N) while isConnected is in O(log N). Try first designing an algorithm that runs in O(N) for both operations. Then, add an invariant to ensure efficient connection of two components and eliminate worst-case linear-time array state. Given an int N specifying the total number of sites (indexed 0 through N - 1), the dynamic connectivity problem specifies the following API describing the basic operations that we need. connect(int p, int q): Add a connection between sites p and g. isConnected (int p, int q): Returns true if and only if sites p and q are in the same component. The connect and isConnected operations model an equivalence relation, which means that it is: Reflexive: p is connected to p. Symmetric: If p is connected to q, then q is connected to p. Transitive: If p is connected to q and q is connected to r, then p is connected to r. You may introduce 2 arrays of size N. Hint: Consider initializing each index of an array to the value of the corresponding site, e.g. initialize array index 17 to the value 17. For each of the following conditions, give a crisp and concise English description of a dynamic connectivity algorithm that meets the requirements. 1 Runtime for connect is in O(N) while isConnected is in 0(1). 2 Runtime for connect is in O(log N) while isConnected is in O(log N). Try first designing an algorithm that runs in O(N) for both operations. Then, add an invariant to ensure efficient connection of two components and eliminate worst-case linear-time array state
