Big O and Algorithm Efficiency

def greedy_coin_change(amount, coins=[25, 10, 5, 1]):
    change = []
    for coin in coins:
        while amount >= coin:
            amount -= coin
            change.append(coin)
    return change

# Example usage:
amount = 63
result = greedy_coin_change(amount)
print(f"Change for {amount}¢: {result}")
print(f"Total coins used: {len(result)}")

Change for 63¢: [25, 25, 10, 1, 1, 1]
Total coins used: 6

Popcorn Hacks

Popcorn Hack 1: The most efficient strategies are checking the last digit and then using the modulus operator to check if the remainder when divided by 2 is 0. This is because these methods both implement the O(1) operator, and options 2 and 3 only require one step. When checking the last number, it’s only one step, and there are only 5 options to check from. As for the modulus, this operation is also one step since it immediately gives back the result of whether the number is 0 or not.

Popcorn Hack 2:

• The Linear search is 0.483965 seconds.
• The Binary search is 0.000038 seconds. It is 12687x faster than the linear search. If you increase the data set, the time it takes to run is longer, but the Binary search is still a lot faster than the linear searching algorithm. Linear search: 0.700474 seconds. Binary search: 0.000023 seconds. Binary search is approximately 30604x faster

Challenge: For a performance-critical application, I would choose the Speed-Optimized Method (s[::-1]):

• Speed Matters most in Performance-Critical Apps
• Memory tade-off is efficient, and does not lead to loss.
• The graph will show quickly and will be scaled linear/ reasonably.

Homework Hacks

Homework Hack 1

The merge sort is consistantly faster than the bubble sort because it splits up the values rather than tackling each one induvidually. By dividing and conquering, merge sorting reduces the number of comparisons need to run the algorithm. Bubble sort has a larger time complexity since it has to manually switch each value that is next to the starting item.

• Therefore, O(n log n) is better than O(n²).

import random
import time

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]

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
random_list = [random.randint(1, 1000) for _ in range(100)]
list_for_bubble = random_list.copy()
list_for_merge = random_list.copy()

# Time Bubble Sort
start_bubble = time.time()
bubble_sort(list_for_bubble)
end_bubble = time.time()

# Time Merge Sort
start_merge = time.time()
merge_sort(list_for_merge)
end_merge = time.time()

# Output times
bubble_time = end_bubble - start_bubble
merge_time = end_merge - start_merge

print(f"Bubble Sort took: {bubble_time:.6f} seconds")
print(f"Merge Sort took: {merge_time:.6f} seconds")

if bubble_time < merge_time:
    print("Bubble Sort is faster.")
else:
    print("Merge Sort is faster.")

Bubble Sort took: 0.000171 seconds
Merge Sort took: 0.000093 seconds
Merge Sort is faster.

Homework Hack 2

1. Binary searching is a lot faster than Linear searching because it uses a lot less comparisons. It cuts down the list in half each time, causing the algortihm to be more efficient and work faster compared to the linear search that makes comparisons at each item given in a list. This is why the Linear search is given by O(n).
2. On an unsorted list, the Linear searching algorithm would still work since it does not rely on if the list is sorted or not. However, the binary search would break down as it needs a sorted list to function. In this case, it would be more efficient for a programmer to use linear searching with unsorted lists.

import random

def linear_search(arr, target):
    count = 0
    for i in range(len(arr)):
        count += 1
        if arr[i] == target:
            return count
    return -1

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

# Generate sorted list
arr = list(range(1, 100001))

# Pick a random target from the list
target = random.choice(arr)

# Perform searches
linear_comparisons = linear_search(arr, target)
binary_comparisons = binary_search(arr, target)

# Output results
print(f"Target: {target}")
print(f"Linear Search comparisons: {linear_comparisons}")
print(f"Binary Search comparisons: {binary_comparisons}")

Target: 18274
Linear Search comparisons: 18274
Binary Search comparisons: 16