The following algorithm solves this problem:
INPUT: n: number of sets S0, ..., Sn-1, where Si is a SUBSET of {0,1,...,n-1}. OUTPUT: True, if there is a pair of the input sets Si and Sj that are disjoint (in this case, i and j are printed). False, otherwise. ALGORITHM:
cost of each instruction | # of times instruction will be repeated | |
for each set Si: for each other set Sj: disjoint = true for each element k of Si: if k belongs to Sj: disjoint = false if disjoint == true print 'Sets ',i,j,' are disjoint' return(true) return(false) |
T(n) will be affected also by how you implement the "for each other set Sj" instruction. Note that it is enough to consider j > i only. [Hint: Studying the runtime analysis of InsertionSort in section 2.2 of the textbook will help you think of ideas to express the number of iterations of the instructions in the algorithm above.]
[[2, 3, 0], [4, 2], [1, 4, 3, 0], [2], []]
[[1, 0, 1, 1, 0], [0, 0, 1, 0, 1], [1, 1, 0, 1, 1], [0, 0, 1, 0, 0], [0, 0, 0, 0, 0]]
def DisjointSetsVersion1(L): ... def DisjointSetsVersion2(L): ...
Submit your code on myWPI.
anProvide a detailed, rigorous proof of each part of your solution.
na
ana
loga(n)
aa*n
nloga(n)where a is a constant greater than 1.
Transitivity of Big-O: If f(n) = O(g(n)) and g(n) = O(h(n)) then f(n) = O(h(n)).
import sys sys.setrecursionlimit(12000)I include here the skeleton of a Python program that I wrote which satisfies the requirements below.
[n-1, n-2, ..., 2, 1, 0]
Submit your Python program on myWPI.