Please post your solutions to the Apr 7 In-Class Exercise to this thread.

Best,

Chris

declare boolean value "wrap"<br>
declare and initialize empty list "res"<br>
For each ordered pair P in S:<br>
	initialize wrap to false<br>
	For each ordered pair Q in S:<br>
		if (P is not Q) and (P.first <= Q.first) and (P.second >= Q.second):<br>
			set wrap to true<br>
			break<br>
	if wrap is false:<br>
		add P to res<br>
return res<br>

<br> The total runtime for this code will be quadratic i.e O(n^2). Super naive implementation :D<br>

foreach pairA in S { foreach pairB in S{ if pairA contains pairB { //ie elementA[0] <= pairB[0] && pairA[1] >= pairB[1] delete pairA from S break from the inner loop } } }

Big O is n^2

<nowiki> compute_G(pairs S) { G = [ first pair<u,v> of S ] // initialize GC-list foreach pair<u,v> p in S { foreach pair<u,v> g in G { if (g.u <= p.u and g.v >= p.v) // p<u,v> g<u,v> G ignores p else G appends p } } return G }

Code Runtime: = N

</nowiki>

Assumption: The list of intervals is sorted by first position, then by second position.

i = 0 // position in list

while i < len(S) - 1:

a = S[i]

b = S[i + 1]

if a[0] == b[0] and a[1] == b[1]:

	S.remove(a)

elif a[0] == b[0] and a[1] < b[1]:

	S.remove(b)

elif a[0] < b[0] and a[1] == b[1]:

	S.remove(a)

elif a[0] < b[0] and a[1] > b[1]:

	S.remove(a)

else:

	i += 1

If the above assumption does not hold, we can sort the list so that it does. In either case, the runtime is O(n^2) since remove() takes O(n) time.

<nowiki> for i in range(0,len(S)): for j in range(i, len(S)): if S[i][0] >= S[j][0] and S[i][1] <= S[j][1]: flag S[i] for removal

O(N): N^2 </nowiki>

pairs_past = [] //Pairs checked

GC = [] //Final Generalized Concordance list

for each pair A in S: Add A to pairs_past for each pair B in S - pairs_past: if B is not subset of A: Add B to GS

O(N): N^2

<nowiki> G(S): // S = [ [u1, v1], [u2, v2] ]

sort(S) // by position u

i = 0
while i+1 < len(S):

	u = s[i][0]
	v = s[i][1]

	uprime = s[i+1][0]
	vprime = s[i+1][1]

	// case 1: no overlap
	if v < uprime:
		i++

	// case 2: overlap but not strict sub-interval
	else if v >= uprime and vprime > v:
		i++

	// case 3: overlap and fully contained
	else if v >= uprime and v >= vprime:
		S.remove(i+1)

</nowiki> Time Complexity

If S is an array then the remove operation will have linear time complexity O(n). This can be reduced by using a different data structure like a linked list with a cost of O(1). <br><br> Sorting (e.g. merge sort) will take O(n log n). <br><br> Worst Case: sorting + loop w/ array.remove = n log n + n^2 = O(n^2) <br> Best Case: sorting + loop w/ linkedlist.remove = n log n + n = O(n log n)

Given list of ordered pairs, 'S'.

'''Pseudo code''' to form a G out of it is:

<nowiki> def G(S): # sort by the first interval value, if ties exist then use second value S_sorted = quick_sort(S)

to_remove = []
for j in (0, len(S_sorted)-1):
    current = S_sorted[j]
    next = S_sorted[j+1]

    # strict sub interval
    if (current[0] < next[0] and current[1] > next[1]):    
          to_remove.append(current)

gc = []
for pair in S:
    if pair not in to_remove:  gc.append(pair)

return gc

</nowiki>

'''Time complexity''' = Sorting + for loop to find subinterval + for loop to remove super intervals = O(n logn) + O(n) + O(n) = O(n logn)

S = given list of ordered pairs G = initialize it with S

for i in range(0 to length of S): for j in range(i+1 to length of S): if S[i][0] >= s[j][0] and S[i][1] <= S[j][i] then remove it from GC list (G) return G (final GC list)

Time Complexity O(N): N^2