Popcorn Hack 1 Graph Data Strcuture

  4   A ------- B   |         | \  2|         |5 \2   |         |   \   C ------- D --- E
 \10     8

Homework Hack Graph

Q1: In which of the configurations is it possible to have redundant routing between devices Q and V?

A) Configuration I only
B) Configuration II only
✅ C) Both configuration I and configuration II
D) Neither configuration I nor configuration II

Q2: In configuration I, what is the minimum number of connections that must be broken or removed before device T can no longer communicate with device U?

A) One
B) Two
✅ C) Three
D) Four

Popcorn Hack 2

def greedy_coin_change(amount, coins):
    count = 0
    used_coins = []
    for coin in coins:
        while amount >= coin:
            amount -= coin
            used_coins.append(coin)
            count += 1
    return count, used_coins

# Test amount
amount = 63

# Normal greedy: largest to smallest
greedy_coins = [25, 10, 5, 1]
greedy_count, greedy_used = greedy_coin_change(amount, greedy_coins)

# Reversed greedy: smallest to largest
reversed_coins = list(reversed(greedy_coins))
reversed_count, reversed_used = greedy_coin_change(amount, reversed_coins)

print("Normal Greedy Strategy:")
print(f"Coins used: {greedy_used}")
print(f"Total coins: {greedy_count}\n")

print("Reversed Greedy Strategy:")
print(f"Coins used: {reversed_used}")
print(f"Total coins: {reversed_count}")

Homework Hack 2 Wrap-Up on Heuristics

Changing the order of coins affected the number of coins used.
The original greedy algorithm (largest coin first) used fewer coins.
Greedy algorithms work well with U.S. coins, but they can fail with custom coin systems.
Reversing the coin order showed that greedy isn’t always efficient or optimal.

📝 Summary:

Changing the order of coins helped me see how greedy algorithms make quick decisions that can be efficient but not always perfect. I learned that greedy works best when the system is designed for it, and one small change can make a big difference.

Popcorn and Homework Hack 3

Popcorn Hack #2: Practice from College Board

#1. An algorithm can be used to solve an undecidable problem

False

Details:

By definition, undecidable problems cannot be solved by any algorithm in all cases. No algorithm can provide a guaranteed correct answer for every possible input.

#2. If a programmer encounters an undecidable problem, they can just use an algorithm that works most of the time.

True

Details:

While undecidable problems can’t be perfectly solved, heuristic algorithms can be used to produce useful results in some cases, even if they don’t work for every input.

HOMEWORK hack 3

Part 1: Identify the Problem Type

“Is this number divisible by 2?”
Decidable – We can write an algorithm to check divisibility by 2 and it will always give a correct answer.

“Will this program stop or run forever?”
Undecidable – This is the Halting Problem, which has been proven to have no general solution.

“Does this sentence contain the word ‘banana’?”
Decidable – We can search through the sentence and check if “banana” exists.

“Will this AI ever become sentient?”
Undecidable – Sentience is not clearly defined or measurable, and we can’t determine the future behavior of AI with certainty.

Part 2: Algorithm Detective

Algorithm 1:

Step 1: Input a number
Step 2: If the number is even, say “Yes.” If not, say “No.”
Decidable – This has a clear yes/no answer based on an easily computed condition.

Algorithm 2:

Step 1: Input any program
Step 2: Predict if it will ever stop running
Step 3: Output “Yes” if it will stop, “No” if it will run forever
Undecidable – This is the Halting Problem; there’s no algorithm that works for all programs.

Part 3: Real-Life Connection

Real-life example:
Deciding if a friendship will last forever.

Details:

You can’t predict the future of a relationship with certainty—you have to go through the experience to find out.

import time
import random

# Generate a large sorted list
data_size = 10000000
sorted_data = sorted(random.sample(range(100000000), data_size))

# Target to find (worst case for linear search)
target = sorted_data[-1]  # Last element

# O(n) - Linear Search
def linear_search(arr, target):
    for i, element in enumerate(arr):
        if element == target:
            return i
    return -1

# O(log n) - Binary Search
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

# Compare performance
print("Testing with data size:", data_size)

start = time.time()
linear_result = linear_search(sorted_data, target)
linear_time = time.time() - start
print(f"Linear search: {linear_time:.6f} seconds")

start = time.time()
binary_result = binary_search(sorted_data, target)
binary_time = time.time() - start
print(f"Binary search: {binary_time:.6f} seconds")

print(f"Binary search is approximately {linear_time/binary_time:.0f}x faster")

  

Questions + Answers

What is the time complexity of each algorithm? Linear Search: O(n) and Binary Search: O(log n)
How many times faster is binary search than linear search? When data_size = 10,000,000, Binary search is about 100x to 1000x faster than linear search in practice.
What happens if you increase data_size to 20000000? Linear search: Takes about 2x longer. Binary search: Takes only a tiny bit longer (still very fast).

Homework Hack 1

import random
import time

# Bubble Sort Function
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 Function
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
original_list = [random.randint(1, 1000) for _ in range(100)]

# Time Bubble Sort
bubble_list = original_list[:]
start_bubble = time.time()
bubble_sort(bubble_list)
end_bubble = time.time()
bubble_time = end_bubble - start_bubble

# Time Merge Sort
merge_list = original_list[:]
start_merge = time.time()
merge_sort(merge_list)
end_merge = time.time()
merge_time = end_merge - start_merge

# Output the results
print(f"Bubble Sort Time: {bubble_time:.6f} seconds")
print(f"Merge Sort Time: {merge_time:.6f} seconds")

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

Final Question Answer

Why does Merge Sort consistently outperform Bubble Sort? Merge Sort uses a split up and try approach with O(n log n) time complexity, while Bubble Sort has a much slower O(n^2) complexity. As the dataset grows, Bubble Sort takes a lot more time due to repeated comparisons and swaps.

Homework Hack 2

import random

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

# Binary Search Function
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

# Create a sorted list of 100,000 numbers
data = list(range(1, 100001))

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

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

# Print results
print(f"Target Number: {target}")
print(f"Linear Search Comparisons: {linear_comparisons}")
print(f"Binary Search Comparisons: {binary_comparisons}")

Final Questions

Which search algorithm is faster, and why? Binary Search is faster because it divides the list in half each time (O(log n)) while Linear Search checks one element at a time (O(n)).
What happens if you run both searches on an unsorted list? Binary Search won’t work correctly because it relies on the list being sorted. Linear Search still works because it just checks each element one by one.