Yioop - PHP Search Engine

-- Oct 16 In-Class Exercise Thread

Pseudo code

 input_list = [[5, 9], [8, 12], [15, 20], [1, 10], [9, 11], [3,8]]
 
 sorted_list = sort(input_list) based on the first element of each interval.
 for i in range (0, len(sorted_list))
	if sorted_list[i] = X then 
		continue
 	for j in range (1, len(sorted_list))
		if sorted_list[i][0] > sorted_list[j][0] and sorted_list[i][1] > sorted_list[j][1] then
			Replace sorted_list[i] with X
 
 GC_list = Delete X from the sorted_list

Runtime

For sorting - O(nlog(n))

For comparing the intervals - O(n^2)

Final runtime - O(n^2)

(Edited: 2019-10-21)

Pseudo code input_list = [[5, 9], [8, 12], [15, 20], [1, 10], [9, 11], [3,8]] sorted_list = sort(input_list) based on the first element of each interval. for i in range (0, len(sorted_list)) if sorted_list[i] = X then continue for j in range (1, len(sorted_list)) if sorted_list[i][0] > sorted_list[j][0] and sorted_list[i][1] > sorted_list[j][1] then Replace sorted_list[i] with X GC_list = Delete X from the sorted_list Runtime For sorting - O(nlog(n)) For comparing the intervals - O(n^2) Final runtime - O(n^2)

-- Oct 16 In-Class Exercise Thread

	
 GS (S[1], S[2],...,S[n]) {
	S' = sort (S, (a,b) -> a - b); // sort in ascending order

	for (i in range (1, S.length)) {
		for (j in range (1, S'.length)) {
			if (S'[j][1] >= S[i][1] && S'[j][2] <= S[j][1] ) {
				S.remove(S[j]);
			}
		}
	}
	
	return S;
 }

Time Complexity O(n^2) (Edited: 2019-10-21)

GS (S[1], S[2],...,S[n]) { S' = sort (S, (a,b) -> a - b); // sort in ascending order for (i in range (1, S.length)) { for (j in range (1, S'.length)) { if (S'[j][1] >= S[i][1] && S'[j][2] <= S[j][1] ) { S.remove(S[j]); } } } return S; } Time Complexity O(n^2)

-- Oct 16 In-Class Exercise Thread

global array : int set_arr={(1,10),(2,9),(5,8),(11,19)};

sort(set_arr);

for(int i=0; i<set_arr.length; i++) { $item=setarr[i]

   x=$item[0];
   y=$item[1];

   j=i+1;
   $itemJ=set_arr[j];

if($itemJ[0] >=x && $itemJ[1] <=y) {

   del($item)   //del the previous set from arr

void del($item) {

  $item -> NULL

}

Time Complexity: O(n*n)

(Edited: 2019-10-21)

global array : int set_arr={(1,10),(2,9),(5,8),(11,19)}; sort(set_arr); for(int i=0; i<set_arr.length; i++) { $item=setarr[i] x=$item[0]; y=$item[1]; j=i+1; $itemJ=set_arr[j]; if($itemJ[0] >=x && $itemJ[1] <=y) { del($item) //del the previous set from arr } void del($item) { $item -> NULL } } Time Complexity: O(n*n)

-- Oct 16 In-Class Exercise Thread

 getGS((S[1], S[2], ..., S[n])) { 
  
  #S[i] is representing an interval [u,v]
  
  S' = sort S by value of u in interval of the form [u,v]
  
  while i = 1 to S'.length
	if S'[i][u] >= S'[i-1][u] and S'[i][v] <= S'[i-1][v] then
		delete S'[i-1]
	
  return S'
 }

 time complexity : O(nlogn)

(Edited: 2019-10-21)

getGS((S[1], S[2], ..., S[n])) { #S[i] is representing an interval [u,v] S' = sort S by value of u in interval of the form [u,v] while i = 1 to S'.length if S'[i][u] >= S'[i-1][u] and S'[i][v] <= S'[i-1][v] then delete S'[i-1] return S' } time complexity : O(nlogn)

-- Oct 16 In-Class Exercise Thread

GS (S[1], S[2],...,S[n]) {

	sort (S, (a,b) -> a - b); // sort in ascending order
	
	Result_S[] = {};
	
	for (i in range (1, S.length)) {
		for (j in range (1, S.length)) {
			if (S[j][1] >= S[i][1] && S[j][2] <= S[j][1] ) {
				Result_S.append(S[j]);
			}
		}
	}
	
	return Result_S;
 }

GS (S[1], S[2],...,S[n]) { sort (S, (a,b) -> a - b); // sort in ascending order Result_S[] = {}; for (i in range (1, S.length)) { for (j in range (1, S.length)) { if (S[j][1] >= S[i][1] && S[j][2] <= S[j][1] ) { Result_S.append(S[j]); } } } return Result_S; }

-- Oct 16 In-Class Exercise Thread

GS (S[1], S[2],...,S[n]) {

       // Sort S based on the first term in the subinterval of S
	for (i in range (1, S.length)) {
		for (j in range (1, S'.length)) {
			if (S'[j][1] >= S[i][1] && S'[j][2] <= S[j][1] ) {
				S.remove(S[j]);
			}
		}
	}
	
	return S;
 }

GS (S[1], S[2],...,S[n]) { // Sort S based on the first term in the subinterval of S for (i in range (1, S.length)) { for (j in range (1, S'.length)) { if (S'[j][1] >= S[i][1] && S'[j][2] <= S[j][1] ) { S.remove(S[j]); } } } return S; }

-- Oct 16 In-Class Exercise Thread

Find_GC(list of length n) { list

(Edited: 2019-10-21)

<nowiki>Find_GC(list of length n) { list <- sort list by 1st parameter; for i in (1, length(list)) { for j in (i + 1, length(list)) { if list[i][1] <= list[i+1][1] { remove(list[i]) } } } } Time Complexity: Sorting: O(nlog(n)) Runtime: O(n*n) </nowiki>

-- Oct 16 In-Class Exercise Thread

GS (S[1], S[2],...,S[n]) {

	sort (S, (a,b) -> a - b); // sort in ascending order
	
	Result_S[] = {};
	
	for (i in range (1, S.length)) {
		for (j in range (1, S.length)) {
			if (S[j][1] >= S[i][1] && S[j][2] <= S[j][1] ) {
				Result_S.append(S[j]);
			}
		}
	}
	
	return Result_S;
 }

Time Complexity: O(n^2)

GS (S[1], S[2],...,S[n]) { sort (S, (a,b) -> a - b); // sort in ascending order Result_S[] = {}; for (i in range (1, S.length)) { for (j in range (1, S.length)) { if (S[j][1] >= S[i][1] && S[j][2] <= S[j][1] ) { Result_S.append(S[j]); } } } return Result_S; } Time Complexity: O(n^2)