Algorithms and Problem Solving

Warm-Up: The Sorting Race

Take your deck of numbered cards (or write numbers 1 through 20 on index cards, shuffle them well).

Round 1: Sort all 20 cards from lowest to highest as fast as possible. Time yourself. How did you do it? What was your strategy?

Round 2: Now try to sort them using only this rule: you may compare two cards side by side and swap them if they are in the wrong order. No picking up the whole pile and rearranging. How long does it take now?

---

Core Lesson: Algorithms, Search, and Big-O

What Is an Algorithm?

An algorithm is a precise, step-by-step procedure for solving a problem. You already use algorithms every day:

• A recipe is an algorithm for making food
• Long division is an algorithm for dividing numbers
• Google Maps uses algorithms to find the fastest route

In computer science, we care deeply about how efficient an algorithm is -- specifically, how the amount of work it does grows as the input gets larger.

Linear Search: The Obvious Way

Imagine you have a list of 1,000 names and you want to find "Zara." The simplest approach: start at the beginning and check each name one by one.

Check name 1: "Alice" -- nope
Check name 2: "Bob" -- nope
Check name 3: "Carlos" -- nope
...
Check name 997: "Zara" -- found it!

This is called linear search. In the worst case (the name is at the very end, or it is not in the list at all), you have to check every single item.

• 10 items --> up to 10 checks
• 1,000 items --> up to 1,000 checks
• 1,000,000 items --> up to 1,000,000 checks

The work grows proportionally with the input size. Double the list, double the work.

Binary Search: The Smart Way

Now imagine the list is sorted alphabetically (like a phone book). You can do something much smarter:

1. Open to the middle of the book.
2. Is the name you want before or after this page?
3. Eliminate half the remaining book.
4. Repeat.

Searching for "Zara" in 1,000 sorted names:

Step 1: Check middle (name 500): "Marcus" -- Zara is after this. Eliminate 1-500.
Step 2: Check middle of 501-1000 (name 750): "Rosa" -- Zara is after. Eliminate 501-750.
Step 3: Check middle of 751-1000 (name 875): "Tyler" -- Zara is after. Eliminate 751-875.
Step 4: Check middle of 876-1000 (name 938): "Wendy" -- Zara is after. Eliminate 876-938.
Step 5: Check middle of 939-1000 (name 969): "Yuki" -- Zara is after. Eliminate 939-969.
Step 6: Check middle of 970-1000 (name 985): "Zack" -- Zara is before. Eliminate 985-1000.
Step 7: Check middle of 970-984 (name 977): "Zane" -- Zara is after. Eliminate 970-977.
...found in about 10 steps!

Each step cuts the remaining possibilities in half. This is binary search.

Big-O Notation: Measuring Efficiency

Computer scientists use Big-O notation to describe how an algorithm's work grows with input size. Think of it as a "speed rating" that ignores small constant factors and focuses on the overall growth pattern.

| Big-O | Name | Example | 100 items | 1,000,000 items | |-------|------|---------|-----------|-----------------| | O(1) | Constant | Looking up an array element by index | 1 step | 1 step | | O(log n) | Logarithmic | Binary search | ~7 steps | ~20 steps | | O(n) | Linear | Linear search, finding max of unsorted list | 100 steps | 1,000,000 steps | | O(n log n) | Log-linear | Efficient sorting (merge sort, quicksort) | ~700 steps | ~20,000,000 steps | | O(n^2) | Quadratic | Bubble sort, insertion sort | 10,000 steps | 1,000,000,000,000 steps |

The key insight: logarithmic growth is incredibly slow. Every time you double the input, log n increases by only 1. That is why binary search is so powerful:

| Items | Linear search (worst case) | Binary search (worst case) | |-------|---------------------------|---------------------------| | 100 | 100 | 7 | | 1,000 | 1,000 | 10 | | 1,000,000 | 1,000,000 | 20 | | 1,000,000,000 | 1,000,000,000 | 30 |

---

Hands-On Lab: Racing Algorithms in Python

Program 1: Implement Linear Search and Binary Search

def linear_search(lst, target):
    """Search for target by checking every element one by one."""
    steps = 0
    for i in range(len(lst)):
        steps += 1
        if lst[i] == target:
            return i, steps  # Found it! Return index and step count
    return -1, steps  # Not found

def binary_search(lst, target):
    """Search for target by repeatedly halving the search space.
    Requires the list to be sorted!"""
    steps = 0
    low = 0
    high = len(lst) - 1

    while low <= high:
        steps += 1
        mid = (low + high) // 2

        if lst[mid] == target:
            return mid, steps  # Found it!
        elif lst[mid] < target:
            low = mid + 1  # Target is in the upper half
        else:
            high = mid - 1  # Target is in the lower half

    return -1, steps  # Not found

# Test both algorithms
sorted_list = list(range(1, 101))  # [1, 2, 3, ..., 100]
target = 73

index1, steps1 = linear_search(sorted_list, target)
index2, steps2 = binary_search(sorted_list, target)

print(f"Searching for {target} in a list of {len(sorted_list)} items:")
print(f"  Linear search: found at index {index1} in {steps1} steps")
print(f"  Binary search: found at index {index2} in {steps2} steps")

Run this and compare the step counts. Try changing the target to different values. When is linear search's step count high? Low?

Program 2: Time Them on Large Lists

import time
import random

def linear_search(lst, target):
    for i in range(len(lst)):
        if lst[i] == target:
            return i
    return -1

def binary_search(lst, target):
    low, high = 0, len(lst) - 1
    while low <= high:
        mid = (low + high) // 2
        if lst[mid] == target:
            return mid
        elif lst[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

# Test on different list sizes
sizes = [1000, 10000, 100000, 1000000, 10000000]

print(f"{'List Size':<15} {'Linear (sec)':<15} {'Binary (sec)':<15} {'Speedup':<10}")
print("-" * 55)

results = []

for size in sizes:
    sorted_list = list(range(size))
    target = size - 1  # Worst case: target is the last element

    # Time linear search
    start = time.time()
    linear_search(sorted_list, target)
    linear_time = time.time() - start

    # Time binary search
    start = time.time()
    binary_search(sorted_list, target)
    binary_time = time.time() - start

    # Avoid division by zero
    speedup = linear_time / binary_time if binary_time > 0 else float('inf')

    results.append((size, linear_time, binary_time))
    print(f"{size:<15,} {linear_time:<15.6f} {binary_time:<15.6f} {speedup:<10.0f}x")

Program 3: Graph the Results with Matplotlib

import time
import matplotlib.pyplot as plt

def linear_search(lst, target):
    for i in range(len(lst)):
        if lst[i] == target:
            return i
    return -1

def binary_search(lst, target):
    low, high = 0, len(lst) - 1
    while low <= high:
        mid = (low + high) // 2
        if lst[mid] == target:
            return mid
        elif lst[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

# Collect timing data
sizes = [100, 500, 1000, 5000, 10000, 50000, 100000, 500000, 1000000]
linear_times = []
binary_times = []

for size in sizes:
    sorted_list = list(range(size))
    target = size - 1  # Worst case

    # Time linear search (average of 3 runs)
    total = 0
    for _ in range(3):
        start = time.time()
        linear_search(sorted_list, target)
        total += time.time() - start
    linear_times.append(total / 3)

    # Time binary search (average of 3 runs)
    total = 0
    for _ in range(3):
        start = time.time()
        binary_search(sorted_list, target)
        total += time.time() - start
    binary_times.append(total / 3)

# Create the graph
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(14, 5))

# Left plot: both on same scale
ax1.plot(sizes, linear_times, 'ro-', label='Linear Search O(n)', linewidth=2)
ax1.plot(sizes, binary_times, 'bs-', label='Binary Search O(log n)', linewidth=2)
ax1.set_xlabel('List Size')
ax1.set_ylabel('Time (seconds)')
ax1.set_title('Linear vs Binary Search')
ax1.legend()
ax1.grid(True, alpha=0.3)

# Right plot: log scale to see both clearly
ax2.plot(sizes, linear_times, 'ro-', label='Linear Search O(n)', linewidth=2)
ax2.plot(sizes, binary_times, 'bs-', label='Binary Search O(log n)', linewidth=2)
ax2.set_xlabel('List Size')
ax2.set_ylabel('Time (seconds)')
ax2.set_title('Same Data — Log Scale')
ax2.set_xscale('log')
ax2.set_yscale('log')
ax2.legend()
ax2.grid(True, alpha=0.3)

plt.tight_layout()
plt.savefig('search_comparison.png', dpi=150)
plt.show()
print("Graph saved as search_comparison.png")

---

Challenge: Powers of Two and Bubble Sort

Part 1: The Power of Halving

Answer these questions. They all come down to the same math: how many times can you halve a number before reaching 1?

Part 2: Implement Bubble Sort and See O(n^2)

import time

def bubble_sort(lst):
    """Sort a list by repeatedly swapping adjacent elements.
    This is simple but slow -- O(n^2)."""
    arr = lst.copy()  # Don't modify the original
    n = len(arr)
    comparisons = 0

    for i in range(n):
        for j in range(n - 1 - i):
            comparisons += 1
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # Swap!

    return arr, comparisons

# Test it
import random

sizes = [100, 500, 1000, 2000, 5000, 10000]

print(f"{'List Size':<12} {'Comparisons':<15} {'Time (sec)':<12} {'n^2':<15}")
print("-" * 54)

for size in sizes:
    random_list = random.sample(range(size * 10), size)

    start = time.time()
    sorted_list, comps = bubble_sort(random_list)
    elapsed = time.time() - start

    print(f"{size:<12,} {comps:<15,} {elapsed:<12.4f} {size**2:<15,}")

# Verify it actually sorted correctly
test = random.sample(range(100), 20)
result, _ = bubble_sort(test)
print(f"\nVerification: {result == sorted(test)}")
print(f"Original:  {test}")
print(f"Sorted:    {result}")

---

Resources

• VisuAlgo -- animated visualizations of algorithms and data structures
• Big-O Cheat Sheet -- quick reference for common algorithm complexities
• Khan Academy: Intro to Algorithms -- step-by-step lessons on search and sort
• Python Time Module Docs -- reference for timing code
• Sorting Algorithms Animations -- compare sorting algorithms side by side
• CS50 Lecture on Algorithms (Harvard) -- David Malan's excellent lecture on search and sort