Popcorn Hack 1
- Use the modulus operator (%) to check if the remainder when divided by 2 is 0
- Check if the last digit is 0, 2, 4, 6, or 8 manually
These two methods are O(1) operations — they run in constant time regardless of the size of the number. The modulus operator is a direct mathematical approach, while checking the last digit is a quick shortcut that works for base-10 numbers (especially when dealing with strings or user input).
Popcorn hack 2
import time
import bisect
data_size = 1000000
data = list(range(data_size))
target = data_size - 1
# Linear Search
start = time.time()
for i in range(len(data)):
if data[i] == target:
break
end = time.time()
linear_time = end - start
print(f"Linear search time: {linear_time:.6f} seconds")
# Binary Search
start = time.time()
index = bisect.bisect_left(data, target)
if index != len(data) and data[index] == target:
pass
end = time.time()
binary_time = end - start
print(f"Binary search time: {binary_time:.6f} seconds")
# Performance ratio
if binary_time > 0:
print(f"Binary search is {linear_time / binary_time:.2f} times faster.")
else:
print("Binary search was too fast to measure accurately.")
HW hack
import time
import random
# Bubble Sort
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
# Merge Sort
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
merge_sort(left)
merge_sort(right)
i = j = k = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1
k += 1
while i < len(left):
arr[k] = left[i]
i += 1
k += 1
while j < len(right):
arr[k] = right[j]
j += 1
k += 1
# Generate random list
data = [random.randint(1, 1000) for _ in range(100)]
# Copy for both algorithms
data_bubble = data.copy()
data_merge = data.copy()
# Time Bubble Sort
start = time.time()
bubble_sort(data_bubble)
end = time.time()
bubble_time = end - start
print(f"Bubble Sort Time: {bubble_time:.6f} seconds")
# Time Merge Sort
start = time.time()
merge_sort(data_merge)
end = time.time()
merge_time = end - start
print(f"Merge Sort Time: {merge_time:.6f} seconds")
# Compare
if merge_time < bubble_time:
print("✅ Merge Sort is faster.")
else:
print("✅ Bubble Sort is faster (surprising, but possible with small random data).")
Hw Hack 2
import random
# Linear Search
def linear_search(arr, target):
count = 0
for i in range(len(arr)):
count += 1
if arr[i] == target:
return count
return -1 # not found
# Binary Search
def binary_search(arr, target):
left, right = 0, len(arr) - 1
count = 0
while left <= right:
count += 1
mid = (left + right) // 2
if arr[mid] == target:
return count
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 # not found
# Generate sorted list
arr = list(range(1, 100001)) # 1 to 100,000
# Pick a random number from the list
target = random.choice(arr)
print(f"Target number: {target}")
# Run both searches
linear_comparisons = linear_search(arr, target)
binary_comparisons = binary_search(arr, target)
# Results
print(f"Linear Search comparisons: {linear_comparisons}")
print(f"Binary Search comparisons: {binary_comparisons}")