Exercises: Algorithms and Problem-Solving Strategies

These exercises progress from concept checks through Big-O analysis to implementing and comparing algorithm strategies. All coding exercises use Python 3.12+.

Difficulty Guide: - ⭐ Foundational (5-10 min each) - ⭐⭐ Intermediate (10-20 min each) - ⭐⭐⭐ Challenging (20-40 min each) - ⭐⭐⭐⭐ Advanced/Research (40+ min each)

Part A: Big-O Conceptual Understanding ⭐

A.1. In your own words, explain why Big-O notation drops constants. Why is O(3n) the same as O(n)?

A.2. Rank the following complexity classes from fastest to slowest for large inputs: O(n²), O(1), O(n log n), O(log n), O(n).

A.3. An algorithm takes 0.001 seconds to process 1,000 items. Estimate how long it would take for 1,000,000 items if the algorithm is: - a) O(n) - b) O(n²) - c) O(log n)

A.4. Explain the difference between time complexity and space complexity. Give an example of a situation where you might accept worse time complexity to save memory.

A.5. Why does Big-O typically describe the worst case? Describe a scenario where knowing the best case would also be useful.

A.6. A friend says: "My program has two nested loops, so it must be O(n²)." Is this always true? Give a counterexample.

Part B: Big-O Analysis ⭐⭐

B.1. Determine the Big-O time complexity of each function:

# Function 1
def func1(n: int) -> int:
    total = 0
    for i in range(n):
        total += i
    for j in range(n):
        total *= 2
    return total

# Function 2
def func2(n: int) -> int:
    total = 0
    for i in range(n):
        for j in range(n):
            total += i * j
    return total

# Function 3
def func3(n: int) -> int:
    total = 0
    for i in range(n):
        for j in range(5):
            total += i + j
    return total

# Function 4
def func4(n: int) -> int:
    total = 0
    i = n
    while i > 0:
        total += i
        i //= 2
    return total

B.2. What is the Big-O of Python's in operator for: - a) A list - b) A set - c) A dict

Explain why they differ.

B.3. Elena has a list of 10,000 donation records. She needs to find all donors who gave more than $100. She considers two approaches:

# Approach A
big_donors = []
for donor in donors:
    if donor["amount"] > 100:
        big_donors.append(donor)

# Approach B
big_donors = [d for d in donors if d["amount"] > 100]

What is the Big-O of each? Is one meaningfully faster than the other? Explain.

B.4. Analyze the complexity of this function and explain your reasoning:

def mystery(items: list) -> list:
    result = []
    for item in items:
        if item not in result:
            result.append(item)
    return result

(Hint: What is the Big-O of item not in result when result is a list?)

B.5. Dr. Patel has a function that processes DNA sequences:

def process_sequences(sequences: list[str]) -> dict:
    counts = {}
    for seq in sequences:                    # n sequences
        for char in seq:                     # each sequence has length m
            counts[char] = counts.get(char, 0) + 1
    return counts

What is the Big-O in terms of both n (number of sequences) and m (average length of each sequence)?

Part C: Algorithm Implementation ⭐⭐

C.1. Write a function find_min_max(numbers) that returns both the minimum and maximum of a list in a single pass (O(n)). Do not use the built-in min() or max() functions.

def find_min_max(numbers: list[int]) -> tuple[int, int]:
    """Return (minimum, maximum) in a single pass."""
    # Your code here
    pass

# Test:
print(find_min_max([38, 27, 43, 3, 9, 82, 10]))  # Expected: (3, 82)
print(find_min_max([5]))                            # Expected: (5, 5)
print(find_min_max([7, 7, 7]))                     # Expected: (7, 7)

C.2. Write a function that determines whether a list is sorted in ascending order. What is its Big-O?

def is_sorted(items: list) -> bool:
    """Return True if items are in ascending order. O(?)."""
    # Your code here
    pass

# Test:
print(is_sorted([1, 3, 5, 7]))    # True
print(is_sorted([1, 5, 3, 7]))    # False
print(is_sorted([]))               # True
print(is_sorted([42]))             # True

C.3. Write two versions of a function that checks if a string is a palindrome (reads the same forward and backward). Version A should use O(n) extra space; Version B should use O(1) extra space. Both should be O(n) time.

C.4. Write a function two_sum(numbers, target) that returns the indices of two numbers that add up to target. Write both an O(n²) brute-force version and an O(n) version using a dictionary.

def two_sum_brute(numbers: list[int], target: int) -> tuple[int, int]:
    """O(n²) brute force."""
    # Your code here
    pass

def two_sum_fast(numbers: list[int], target: int) -> tuple[int, int]:
    """O(n) using a dict."""
    # Your code here
    pass

# Test:
nums = [2, 7, 11, 15]
print(two_sum_brute(nums, 9))   # (0, 1) because 2 + 7 = 9
print(two_sum_fast(nums, 9))    # (0, 1)

C.5. Implement a greedy algorithm for the activity selection problem: given a list of activities with start and end times, find the maximum number of non-overlapping activities.

def max_activities(activities: list[tuple[int, int]]) -> list[tuple[int, int]]:
    """Select maximum non-overlapping activities (greedy).

    activities: list of (start_time, end_time) tuples
    """
    # Hint: sort by end time, then greedily select
    # Your code here
    pass

# Test:
acts = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
selected = max_activities(acts)
print(f"Selected {len(selected)} activities: {selected}")
# Expected: 4 activities, e.g., [(1,4), (5,7), (8,11), (12,16)]

Part D: Timing and Measurement ⭐⭐⭐

D.1. Write a script that empirically verifies the Big-O of Python's list append() vs. list insert(0, ...) (inserting at the beginning). Time both operations for n = 1,000, 10,000, and 100,000 elements. What complexity class does each exhibit?

D.2. Time the difference between searching for an element in a list vs. a set for increasing sizes (1,000 to 1,000,000). Create a simple table showing the results. What Big-O pattern do you observe for each?

D.3. Write a function that finds the k most frequent elements in a list. Implement it two ways:

# Version A: Sort-based — sort by frequency, take first k
# Version B: Dict-based — count frequencies, extract top k

Time both for a list of 100,000 random integers. Which is faster? What is each one's Big-O?

Part E: Problem-Solving Strategies ⭐⭐⭐

E.1. Brute Force Challenge: Given a list of integers, find the contiguous subarray with the maximum sum. Implement the O(n³) brute-force solution (try every possible start and end index, compute the sum).

def max_subarray_brute(nums: list[int]) -> int:
    """Find max contiguous subarray sum. O(n³) brute force."""
    # Your code here
    pass

print(max_subarray_brute([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # Expected: 6

Then look up Kadane's Algorithm online and implement the O(n) solution. Compare their running times on a list of 10,000 random integers.

E.2. Greedy Challenge: A gas station problem. You're driving along a road with gas stations at positions [0, 100, 200, 375, 500, 650, 700]. Your car can travel 250 miles on a full tank. Starting at position 0 with a full tank, write a greedy algorithm that determines the minimum number of stops needed to reach position 700 (or reports that it's impossible).

E.3. Divide and Conquer Challenge: Write a function that counts the number of occurrences of a target value in a sorted list using divide and conquer. Your solution should be faster than O(n) for sorted input.

Part F: Pseudocode and Tracing ⭐⭐

F.1. Write pseudocode for an algorithm that finds the second-smallest element in a list. Then trace your algorithm on the input [5, 3, 8, 1, 9, 2], showing variable values at each step.

F.2. Trace the following algorithm by hand on the input [4, 2, 7, 1, 5]. Show the state of result after each iteration of the outer loop:

def mystery_sort(items: list) -> list:
    result = list(items)
    for i in range(len(result)):
        min_idx = i
        for j in range(i + 1, len(result)):
            if result[j] < result[min_idx]:
                min_idx = j
        result[i], result[min_idx] = result[min_idx], result[i]
    return result

What sorting algorithm is this? What is its Big-O?

F.3. Write pseudocode for a function that merges two sorted lists into a single sorted list without using Python's sorted(). What is the Big-O if the lists have lengths m and n?

Part G: Integration and Extension ⭐⭐⭐⭐

G.1. TaskFlow Optimization Project: In your TaskFlow application, implement a keyword index — a dictionary that maps each word in task titles to the set of task indices containing that word. Analyze: - What is the Big-O of building the index? - What is the Big-O of searching with the index vs. without? - What is the space trade-off? - When does the index "pay for itself" (i.e., how many searches justify the build cost)?

G.2. Algorithm Comparison Report: Choose a real problem (e.g., finding all anagrams in a word list, scheduling meetings, or finding the shortest path in a grid). Implement at least two different algorithmic approaches, analyze their Big-O for both time and space, and time them on realistic input sizes. Write a short report (1-2 paragraphs) recommending which approach to use and why.

G.3. Reflection: Dr. Patel's original O(n²) script worked fine during development on 100 test files. It only failed when deployed on 10,000 real files. What development practices could catch this kind of problem earlier? Consider at least: testing with realistic data sizes, benchmarking, Big-O analysis during code review, and automated performance tests.