#--------------------------------topic: --------------------------------# #################################Slide 3####################################### def computeHonestPerson_SLOW_ITERATIVE(A, isHonest): n = len(A) if n == 1: return A[0] for j in range(0, len(A)): count = 0 for i in range(0, len(A)): if i != j and isHonest(A[i], A[j]): count += 1 if 2*count >= len(A)-1: return j #################################Slide 4####################################### def computeHonestPerson_SLOW_RECURSIVE(A, isHonest): n = len(A) if n == 1: return A[0] count = 0 for i in range(0, n-1): if isHonest(A[i], A[n-1]): count += 1 if 2*count >= len(A)-1: return A[n-1] else: return computeHonestPerson_SLOW_RECURSIVE(A[0:n-1],isHonest) #--------------------------------topic: --------------------------------# #################################Slide 29####################################### def findMajority(A): if len(A).bit_count() != 1: return None niveau = int( math.log2(len(A)) ) P = list(A) for j in range(1, niveau+1): m = len(A) // (2**j) N = [None]*m for i in range(0, m): count1, count2 = 0, 0 for k in range( (i)*(2**j), (i+1)*(2**j) ): if A[k] == P[2*i]: count1 += 1 if A[k] == P[2*i+1]: count2 += 1 if count1 > 2**j / 2: N[i] = P[2*i] elif count2 > 2**j / 2: N[i] = P[2*i+1] else: N[i] = None print(P, N) P = N return P[0] import math print( findMajority( [3,3,3,3,3,3,1,2,3,3,4,5,6,7,3,9] ) ) #################################Slide 30####################################### def findMajority(A): if len(A).bit_count() != 1: return None niveau = int( math.log2(len(A)) ) P = list(A) for j in range(1, niveau+1): m = len(A) // (2**j) N = [None]*m for i in range(0, m): count1, count2 = 0, 0 for k in range( (i)*(2**j), (i+1)*(2**j) ): if A[k] == P[2*i]: count1 += 1 if A[k] == P[2*i+1]: count2 += 1 if count1 > 2**j/2: N[i] = P[2*i] elif count2 > 2**j / 2: N[i] = P[2*i+1] else: N[i] = None print(P) P = N return P[0] import math print( findMajority( [3,3,3,3,3,3,1,2,3,3,4,5,6,7,3,9] ) ) #################################Slide 33####################################### def findMajority(A): n = len(A) if n == 0: return None if n == 1: return A[0] e1 = findMajority(A[:n//2]) e2 = findMajority(A[n//2:]) count1, count2 = 0, 0 for i in range(0, n): if A[i] == e1: count1 += 1 if A[i] == e2: count2 += 1 if count1 > n/2: return e1 if count2 > n/2: return e2 return None print( findMajority( [3,3,3,3,3,3,1,2,3,3,4,5,6,7,3,9] ) ) #################################Slide 36####################################### import math, time, random, matplotlib.pyplot as plt def findMajority_SLOW(A): n = len(A) sol = None for i in range(0, n): count = 0 for j in range(0, n): if A[i] == A[j]: count += 1 if count > n/2: sol = A[i] return sol def findMajority_FAST_RECURSIVE(A): n = len(A) if n == 0: return None if n == 1: return A[0] e1 = findMajority_FAST_RECURSIVE(A[:n//2]) e2 = findMajority_FAST_RECURSIVE(A[n//2:]) count1, count2 = 0, 0 for i in range(0, n): if A[i] == e1: count1 += 1 if A[i] == e2: count2 += 1 if count1 > n/2: return e1 if count2 > n/2: return e2 return None def findMajority_FAST_ITERATIVE(B): A = list(B) n = len(A) while len(A).bit_count() != 1: A.append(None) niveau = int( math.log2(len(A)) ) P = list(A) for j in range(1, niveau+1): m = len(A) // (2**j) N = [None]*m for i in range(0, m): total, count1, count2 = 0, 0, 0 for k in range( (i)*(2**j), (i+1)*(2**j) ): if k < n: total += 1 if A[k] == P[2*i]: count1 += 1 if A[k] == P[2*i+1]: count2 += 1 if count1 > total / 2: N[i] = P[2*i] elif count2 > total / 2: N[i] = P[2*i+1] else: N[i] = None P = N return P[0] N, S, FI, FR = [], [], [], [] for n in range(1000, 20000, 1000): A = [ random.choice( [2,3]) for j in range(0, n) ] N.append(n) print("n: ", n) s = time.time() print(findMajority_SLOW( A )) S.append(time.time()-s) s = time.time() print(findMajority_FAST_RECURSIVE( A )) FR.append(time.time()-s) s = time.time() print(findMajority_FAST_ITERATIVE( A )) FI.append(time.time()-s) print("\n" + "="*70) print(f"{'n':>10} {'SLOW (s)':>12} {'FAST ITER (s)':>14} {'FAST REC (s)':>14}") print("="*70) for n, s, fi, fr in zip(N, S, FI, FR): print(f"{n:10d} {s:12.6f} {fi:14.6f} {fr:14.6f}") print("="*70) plt.figure(figsize=(10, 6)) plt.plot(N, S, 'o-', label='SLOW (O(n²))', linewidth=2, markersize=8, color='red') plt.plot(N, FI, 's-', label='FAST ITERATIVE (O(n log n))', linewidth=2, markersize=8, color='blue') plt.plot(N, FR, '^-', label='FAST RECURSIVE (O(n log n))', linewidth=2, markersize=8, color='green') plt.xlabel('Input Size (n)', fontsize=12) plt.ylabel('Time (seconds)', fontsize=12) plt.title('Running Time Comparison: Majority Element Algorithms', fontsize=14) plt.legend(fontsize=11) plt.grid(True, alpha=0.3) plt.show() #################################Slide 38####################################### def merge(A, B): C = [] a, b = 0, 0 for i in range(0, len(A)+len(B)): if (b == len(B)) or (a < len(A) and A[a] <= B[b]): C.append(A[a]) a += 1 elif (a == len(A)) or (b < len(B) and B[b] <= A[a]): C.append(B[b]) b += 1 return C def mergeSort_RECURSIVE(A): if len(A) <= 1: return A mid = len(A) // 2 L = mergeSort_RECURSIVE(A[:mid]) R = mergeSort_RECURSIVE(A[mid:]) return merge(L, R) print( mergeSort_RECURSIVE([65,1,44,32,55] )) #################################Slide 39####################################### def merge(A, B): C = [] a, b = 0, 0 for i in range(0, len(A)+len(B)): if (b == len(B)) or (a < len(A) and A[a] <= B[b]): C.append(A[a]) a += 1 elif (a == len(A)) or (b < len(B) and B[b] <= A[a]): C.append(B[b]) b += 1 return C def mergeSort_ITERATIVE(A): s = 1 while s < len(A): i = 0 while (i < len(A)): A[i:i+2*s] = merge(A[i:i+s], A[i+s:i+2*s]) i += 2*s s = 2*s B = [9, 1, 53, 81, 16, 51, 12, 9] mergeSort_ITERATIVE(B) print(B)