2021-04-06
Apr 7 In-Class Exercise Thread.
Please post your solutions to the Apr 7 In-Class Exercise to this thread.
Best,
Chris
Please post your solutions to the Apr 7 In-Class Exercise to this thread.
Best,
Chris
2021-04-07
declare boolean value "wrap"
declare and initialize empty list "res"
For each ordered pair P in S:
initialize wrap to false
For each ordered pair Q in S:
if (P is not Q) and (P.first <= Q.first) and (P.second >= Q.second):
set wrap to true
break
if wrap is false:
add P to res
return res
The total runtime for this code will be quadratic i.e O(n^2). Super naive implementation :D
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
(Edited: 2021-04-07)
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
compute_G(pairs S) {
G = [ first pair of S ] // initialize GC-list
foreach pair p in S {
foreach pair g in G {
if (g.u = p.v) // p ⊂ g
G ignores p
else
G appends p
}
}
return G
}
Code Runtime: Θ = N²
<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.
(Edited: 2021-04-07) 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.
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]
(Edited: 2021-04-08) <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>
2021-04-10
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(Edited: 2021-04-10)
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
2021-04-11
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)
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).
Sorting (e.g. merge sort) will take O(n log n).
Worst Case: sorting + loop w/ array.remove = n log n + n^2 = O(n^2)
Best Case: sorting + loop w/ linkedlist.remove = n log n + n = O(n log n)
(Edited: 2021-04-11) 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).
Sorting (e.g. merge sort) will take O(n log n).
Worst Case: sorting + loop w/ array.remove = n log n + n^2 = O(n^2)
Best Case: sorting + loop w/ linkedlist.remove = n log n + n = O(n log n)
<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:
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
Time complexity = Sorting + for loop to find subinterval + for loop to remove super intervals
(Edited: 2021-04-12)
= O(n logn) + O(n) + O(n)
= O(n logn)
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
(Edited: 2021-04-12) 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
(c) 2024 Yioop - PHP Search Engine