2019-10-15
Oct 16 In-Class Exercise Thread.
Post your solutions to the Oct 16 In-class Exercise to this thread.
Best,
Chris
(Edited: 2019-10-20) Post your solutions to the Oct 16 In-class Exercise to this thread.
Best,
Chris
inp = [[5, 9], [8, 12], [15, 20], [1, 10], [9, 11]]
inp.sort(key=lambda x: x[0])
i = 0
for ele in inp:
for ep in inp[i + 1:]:
if (ep[0] > ele[1]):
break
if (ep[1] <= ele[1] and ep[0] > ele[0]):
inp.remove(ele)
break
print(inp)
=> O(n^2)
(Edited: 2019-10-16) inp = [[5, 9], [8, 12], [15, 20], [1, 10], [9, 11]]
inp.sort(key=lambda x: x[0])
i = 0
for ele in inp:
for ep in inp[i + 1:]:
if (ep[0] > ele[1]):
break
if (ep[1] <= ele[1] and ep[0] > ele[0]):
inp.remove(ele)
break
print(inp)
=> O(n^2)
class Node:
def __init__(self,key):
self.left = None
self.right = None
self.val = key
# Check if pair2 is superset of pair1
def is_super_set(pair1, pair2):
if pair2[0] > pair1[0] and pair2[1] < pair1[1]:
return True
return False
# Check if pair2 is on left side of pair1 (even if overlaps)
def is_on_left(pair1, pair2):
if pair2[0] < pair1[0]:
return True
return False
# Check if pair2 is on right side of pair1 (even if overlaps)
def is_on_right(pair1, pair2):
if pair2[1] > pair1[1]:
return True
return False
# Insert node to tree if it follows G(S)
def insert_pair_to_tree(root, node):
if is_super_set(root.val, node.val):
return
if is_on_right(root.val,node.val):
if root.right is None:
root.right = node
result.append(node.val)
else:
insert_pair_to_tree(root.right, node)
elif is_on_left(root.val, node.val):
if root.left is None:
root.left = node
result.append(node.val)
else:
insert_pair_to_tree(root.left, node)
l = [[5, 9], [8, 12], [15, 20], [1, 10], [10, 11], [4, 6], [10, 20]]
l.sort(key = lambda x: abs(x[1] - x[0]), reverse = True) # O(nlogn)
# Sort by width of pair so wide pairs are processed first
result = []
#Widest pair will not be superset of any other pair
result.append(l[0])
root = Node(l[0])
for i in range(1, len(l)): #(O(n))
curr_node = Node(l[i])
insert_pair_to_tree(root, curr_node) # O(log(n))
# Final time complexity of above loop O(nlogn)
print(result)
(Edited: 2019-10-16) class Node:
def __init__(self,key):
self.left = None
self.right = None
self.val = key
# Check if pair2 is superset of pair1
def is_super_set(pair1, pair2):
if pair2[0] > pair1[0] and pair2[1] < pair1[1]:
return True
return False
# Check if pair2 is on left side of pair1 (even if overlaps)
def is_on_left(pair1, pair2):
if pair2[0] < pair1[0]:
return True
return False
# Check if pair2 is on right side of pair1 (even if overlaps)
def is_on_right(pair1, pair2):
if pair2[1] > pair1[1]:
return True
return False
# Insert node to tree if it follows G(S)
def insert_pair_to_tree(root, node):
if is_super_set(root.val, node.val):
return
if is_on_right(root.val,node.val):
if root.right is None:
root.right = node
result.append(node.val)
else:
insert_pair_to_tree(root.right, node)
elif is_on_left(root.val, node.val):
if root.left is None:
root.left = node
result.append(node.val)
else:
insert_pair_to_tree(root.left, node)
l = [[5, 9], [8, 12], [15, 20], [1, 10], [10, 11], [4, 6], [10, 20]]
l.sort(key = lambda x: abs(x[1] - x[0]), reverse = True) # O(nlogn)
# Sort by width of pair so wide pairs are processed first
result = []
#Widest pair will not be superset of any other pair
result.append(l[0])
root = Node(l[0])
for i in range(1, len(l)): #(O(n))
curr_node = Node(l[i])
insert_pair_to_tree(root, curr_node) # O(log(n))
# Final time complexity of above loop O(nlogn)
print(result)
2019-10-17
Pseudo-code:
getGS((S[1], S[2], ..., S[n])) { # each S[i] is a tuple representing an interval
S' = sort (S[1], S[2], ..., S[n]) by value of (S[i][2]-S[i][1])
for i := 1 to n do {
if (S[i][1] < S'[i][1]) {
S[i]= () # make S[i] an empty tuple
}
}
filter(lambda a: a != (), S); // remove all empty tuples in S
sort (S) by S[1];
return S
}
Example:
S= [(1,10),(2, 8),(3, 5), (4,11), (6,17)]
violation: (2, 8) and (3, 5) are subsets of (1, 10)
(3, 5) is a subset of (2,8)
S[1]-S[2]= [9, 6, 2, 7, 11], so
S'= [(6,17),(1,10),(4,11), (2, 8), (3,5 )]
i=1: 1<6, so S[1]= ();
i=2: 2>1, so keep S[2];
i=3: 3<4, so S[3]= ();
i=4: 4>2, so keep S[4];
i=5: 6>3, so keep S[5];
Now S= [(), (2, 8), (), (4,11), (6,17)]
filter out (), gives result
S= [(2,8),(4,11),(6,17)]
Run-time:
(Edited: 2019-10-17) sorting step: O(nlog(n)), looping: O(n) total: O(nlog(n))
Pseudo-code:
getGS((S[1], S[2], ..., S[n])) { # each S[i] is a tuple representing an interval
S' = sort (S[1], S[2], ..., S[n]) by value of (S[i][2]-S[i][1])
for i := 1 to n do {
if (S[i][1] < S'[i][1]) {
S[i]= () # make S[i] an empty tuple
}
}
filter(lambda a: a != (), S); // remove all empty tuples in S
sort (S) by S[1];
return S
}
Example:
S= [(1,10),(2, 8),(3, 5), (4,11), (6,17)]
violation: (2, 8) and (3, 5) are subsets of (1, 10)
(3, 5) is a subset of (2,8)
S[1]-S[2]= [9, 6, 2, 7, 11], so
S'= [(6,17),(1,10),(4,11), (2, 8), (3,5 )]
i=1: 1<6, so S[1]= ();
i=2: 2>1, so keep S[2];
i=3: 3<4, so S[3]= ();
i=4: 4>2, so keep S[4];
i=5: 6>3, so keep S[5];
Now S= [(), (2, 8), (), (4,11), (6,17)]
filter out (), gives result
S= [(2,8),(4,11),(6,17)]
Run-time:
sorting step: O(nlog(n)),
looping: O(n)
total: O(nlog(n))
find_GC_list(list) {
// list contains n pairs
sort the list in increasing order of the first parameter of pairs O(nlogn)
for i = 1 to n do
for j = i+1 to n do
if list[i][1] <= list[i+1][1] then
remove(list[i])
}
Runtime : O(n*n-1) = O(n^2)(Edited: 2019-10-18)
find_GC_list(list) {
// list contains n pairs
sort the list in increasing order of the first parameter of pairs O(nlogn)
for i = 1 to n do
for j = i+1 to n do
if list[i][1] <= list[i+1][1] then
remove(list[i])
}
Runtime : O(n*n-1) = O(n^2)
2019-10-20
def resetarray(arr):
fill array with 0s
arr <- 0
return arr
def G(gc):
gc = sorted(gc,key=lambda x :x[0])
arr = resetarray(arr)
for (x,y) in gc:
if arr[x] == 1 and arr[y] == 1:
//get the start and end index of array and the remove pair
//reset array
//otherwise
//overlap
//fill the arr indes
for i in range(x,y+1):
arr[i] = 1
gc = [[1,10],[5,9],[8,12],[15,20],[12,15]]
G(gc)
def resetarray(arr):
fill array with 0s
arr <- 0
return arr
def G(gc):
gc = sorted(gc,key=lambda x :x[0])
arr = resetarray(arr)
for (x,y) in gc:
if arr[x] == 1 and arr[y] == 1:
//get the start and end index of array and the remove pair
//reset array
//otherwise
//overlap
//fill the arr indes
for i in range(x,y+1):
arr[i] = 1
gc = [[1,10],[5,9],[8,12],[15,20],[12,15]]
G(gc)
public void FindGClist(String[] inputlist)
{
// Sort inputlist by the first element of the interval
String[] GClist = new GClist();
String [] temparray1 = new temparray();
String [] temparray2 = new temparray();
int GClistindex = 0;
for (int i =0; i <inputlist.length; i++)
{
int counter = 0;
int LC1 = Get the first element from inputlist[i];
int UC1 = Get the second element from inputlist[i];
for (int j =0; j<inputlist.length; j++)
{
if(i!=j)
{
int LC2 = Get the first element from inputlist[j];
int UC2 = Get the second element from inputlist[j];
if(LC2>=LC1 && UC2<=UC1)
{
counter++
break;
}
}
}
if(counter == 0)
{
GClist[GClistindex] = inputlist[i];
GClistindex++;
}
}
for (int k=0; k <GClist.length; k++)
{
System.out.println(GClist[k]);
}
}
String [] inputlist = {"[1 10]","[8 12]","[15 20]","[2 10]","[3 5]","[12 15]","[1,8]"};
FindGClist(inputlist);(Edited: 2019-10-21) public void FindGClist(String[] inputlist)
{
// Sort inputlist by the first element of the interval
String[] GClist = new GClist();
String [] temparray1 = new temparray();
String [] temparray2 = new temparray();
int GClistindex = 0;
for (int i =0; i <inputlist.length; i++)
{
int counter = 0;
int LC1 = Get the first element from inputlist[i];
int UC1 = Get the second element from inputlist[i];
for (int j =0; j<inputlist.length; j++)
{
if(i!=j)
{
int LC2 = Get the first element from inputlist[j];
int UC2 = Get the second element from inputlist[j];
if(LC2>=LC1 && UC2<=UC1)
{
counter++
break;
}
}
}
if(counter == 0)
{
GClist[GClistindex] = inputlist[i];
GClistindex++;
}
}
for (int k=0; k <GClist.length; k++)
{
System.out.println(GClist[k]);
}
}
String [] inputlist = {"[1 10]","[8 12]","[15 20]","[2 10]","[3 5]","[12 15]","[1,8]"};
FindGClist(inputlist);
compute_GS(S[1], S[2], S[3], … S[n]) Sort the list S[1], S[2], S[3], … S[n] by the first value and save in sorted_list for i in size(sorted_list) do: for j in size(sorted_list + 1) do: if i[0] < j[0] and i[1] >= j[1] then: remove sorted_list[i] return sorted_list
Runtime: 0(n^2)
compute_GS(S[1], S[2], S[3], … S[n])
Sort the list S[1], S[2], S[3], … S[n] by the first value and save in sorted_list
for i in size(sorted_list) do:
for j in size(sorted_list + 1) do:
if i[0] < j[0] and i[1] >= j[1] then:
remove sorted_list[i]
return sorted_list
Runtime: 0(n^2)
Input: S[1],S[2],S[3],....S[n]
Get_gs(input)
Sort the input list
i = 0
for x in input[i]:
for y in input[i+1]:
if (y[0]>x[1]):
break
if( y[1] <= x[1] and y[0] > x[0]):
remove x from input list
return input list
Runtime: O(n^2)
Input: S[1],S[2],S[3],....S[n]
Get_gs(input)
Sort the input list
i = 0
for x in input[i]:
for y in input[i+1]:
if (y[0]>x[1]):
break
if( y[1] <= x[1] and y[0] > x[0]):
remove x from input list
return input list
Runtime: O(n^2)
Store intervals in a class Interval that has start and end paramters u, v.
list gc = [Intervals].
Sort gc list based on the first value u.
start = gc[0].u
end = gc[0].v
create empty result list.
for interval in gc:
if interval.u > end || (interval.u != start && interval.v > end):
add new Interval(start, end) to result list
start = interval.u
end = interval.v
else if interval.u <= end:
if interval.u == start && interval.v > end:
end = interval.v
add last interval(start, end) to result list.
return result list.
(Edited: 2019-10-21)
Runtime O(n)
Store intervals in a class Interval that has start and end paramters u, v.
list gc = [Intervals].
Sort gc list based on the first value u.
start = gc[0].u
end = gc[0].v
create empty result list.
for interval in gc:
if interval.u > end || (interval.u != start && interval.v > end):
add new Interval(start, end) to result list
start = interval.u
end = interval.v
else if interval.u <= end:
if interval.u == start && interval.v > end:
end = interval.v
add last interval(start, end) to result list.
return result list.
Runtime O(n)
(c) 2024 Yioop - PHP Search Engine