Part 5: Discrete Mathematics and Algorithms

Part of the Mathematics for Programming 101 Series

The Performance Bug That Taught Me Discrete Math

I had a function to check for duplicates in a list. Simple enough:

def has_duplicates_v1(items):
    """Check if list has any duplicate elements"""
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

Worked perfectly in testing. Deployed to production.

Then user data came in. The function took 30 seconds for a list of 10,000 items. The entire endpoint timed out.

I rewrote it using sets (set theory from discrete math):

def has_duplicates_v2(items):
    """Check using set properties"""
    return len(items) != len(set(items))

Same functionality. 0.001 seconds.

That's when I realized: Discrete mathematics isn't theoretical—it's the difference between code that works and code that scales.

What is Discrete Mathematics?

Discrete mathematics deals with countable, distinct objects—not continuous quantities. It's the foundation of:

• Data structures (sets, graphs, trees)

• Algorithms (sorting, searching, optimization)

• Logic (Boolean operations, conditionals)

• Counting (combinations, permutations)

• Computational complexity (Big O notation)

Every time you choose a data structure or analyze algorithm performance, you're using discrete math.

Set Theory: Foundation of Data Structures

Basic Set Operations

# Sets: unordered collections of unique elements
A = {1, 2, 3, 4, 5}
B = {4, 5, 6, 7, 8}

# Union: elements in A or B (or both)
union = A | B
print(f"A ∪ B = {union}")  # {1, 2, 3, 4, 5, 6, 7, 8}

# Intersection: elements in both A and B
intersection = A & B
print(f"A ∩ B = {intersection}")  # {4, 5}

# Difference: elements in A but not in B
difference = A - B
print(f"A - B = {difference}")  # {1, 2, 3}

# Symmetric difference: elements in A or B but not both
sym_diff = A ^ B
print(f"A △ B = {sym_diff}")  # {1, 2, 3, 6, 7, 8}

# Subset check
C = {1, 2, 3}
is_subset = C <= A
print(f"C ⊆ A? {is_subset}")  # True

# Cardinality (size)
print(f"|A| = {len(A)}")  # 5

Real Application: Finding Common Elements

def find_common_interests(user1_interests, user2_interests):
    """
    Find common interests between two users
    Using set operations instead of nested loops
    """
    set1 = set(user1_interests)
    set2 = set(user2_interests)
    
    common = set1 & set2
    unique_to_user1 = set1 - set2
    unique_to_user2 = set2 - set1
    
    similarity = len(common) / len(set1 | set2) if set1 | set2 else 0
    
    return {
        'common': common,
        'unique_to_user1': unique_to_user1,
        'unique_to_user2': unique_to_user2,
        'similarity': similarity
    }

# Example
user1 = ["python", "javascript", "docker", "kubernetes", "aws"]
user2 = ["python", "golang", "docker", "terraform", "aws"]

result = find_common_interests(user1, user2)
print(f"Common interests: {result['common']}")
print(f"Similarity score: {result['similarity']:.2%}")

Set-Based Deduplication

def remove_duplicates_preserve_order(items):
    """Remove duplicates while preserving order"""
    seen = set()
    result = []
    
    for item in items:
        if item not in seen:
            seen.add(item)
            result.append(item)
    
    return result

# Example
data = [1, 2, 3, 2, 4, 1, 5, 3, 6]
unique = remove_duplicates_preserve_order(data)
print(f"Original: {data}")
print(f"Unique: {unique}")  # [1, 2, 3, 4, 5, 6]

Logic and Boolean Algebra

Truth Tables and Logic Gates

def truth_table(operation):
    """Generate truth table for boolean operation"""
    print(f"\n{operation.__name__.upper()} Truth Table:")
    print("A     B     | Result")
    print("-" * 22)
    
    for a in [False, True]:
        for b in [False, True]:
            result = operation(a, b)
            print(f"{str(a):5} {str(b):5} | {result}")

# Basic operations
def and_gate(a, b):
    return a and b

def or_gate(a, b):
    return a or b

def xor_gate(a, b):
    return a != b  # Exclusive OR

def nand_gate(a, b):
    return not (a and b)

# Generate truth tables
truth_table(and_gate)
truth_table(or_gate)
truth_table(xor_gate)

De Morgan's Laws

Critical for optimizing conditionals:

# De Morgan's Laws:
# not (A and B) = (not A) or (not B)
# not (A or B) = (not A) and (not B)

def demonstrate_de_morgan():
    """Verify De Morgan's laws"""
    for a in [False, True]:
        for b in [False, True]:
            # Law 1: not (A and B) = (not A) or (not B)
            law1_left = not (a and b)
            law1_right = (not a) or (not b)
            assert law1_left == law1_right
            
            # Law 2: not (A or B) = (not A) and (not B)
            law2_left = not (a or b)
            law2_right = (not a) and (not b)
            assert law2_left == law2_right
    
    print("✓ De Morgan's Laws verified!")

demonstrate_de_morgan()

# Practical application: Simplifying conditions
def bad_condition(user):
    """Complicated, hard to read"""
    if not (user.is_active and user.is_verified):
        return False
    return True

def good_condition(user):
    """Applying De Morgan's law"""
    if (not user.is_active) or (not user.is_verified):
        return False
    return True

# Even better: direct logic
def best_condition(user):
    """Most readable"""
    return user.is_active and user.is_verified

Combinatorics: Counting Possibilities

Permutations (order matters)

from math import factorial

def permutations(n, r):
    """
    Number of ways to arrange r items from n items
    P(n,r) = n! / (n-r)!
    
    Example: How many ways to arrange 3 people in 5 chairs?
    """
    return factorial(n) // factorial(n - r)

# Example: Password of 4 digits, no repeats
n_digits = 10  # 0-9
password_length = 4
possible_passwords = permutations(n_digits, password_length)
print(f"Possible 4-digit passwords (no repeats): {possible_passwords:,}")

# Generate all permutations
from itertools import permutations as iter_perms

items = ['A', 'B', 'C']
all_perms = list(iter_perms(items))
print(f"\nAll permutations of {items}:")
for p in all_perms:
    print(''.join(p))

Combinations (order doesn't matter)

from math import comb

def combinations(n, r):
    """
    Number of ways to choose r items from n items
    C(n,r) = n! / (r! * (n-r)!)
    
    Example: How many ways to choose 3 team members from 5 candidates?
    """
    return comb(n, r)

# Example: Lottery - choose 6 numbers from 49
lottery_combinations = combinations(49, 6)
print(f"Lottery combinations: {lottery_combinations:,}")
print(f"Odds of winning: 1 in {lottery_combinations:,}")

# Generate all combinations
from itertools import combinations as iter_combs

team_candidates = ['Alice', 'Bob', 'Charlie', 'David', 'Eve']
team_size = 3

print(f"\nAll possible teams of {team_size} from {team_candidates}:")
for team in iter_combs(team_candidates, team_size):
    print(team)

Real Application: Testing Combinations

def test_all_input_combinations(function, test_cases):
    """
    Test function with all combinations of input cases
    Useful for thorough testing
    """
    from itertools import product
    
    # Generate all combinations
    all_combinations = list(product(*test_cases))
    
    print(f"Testing {len(all_combinations)} combinations...")
    
    for inputs in all_combinations:
        try:
            result = function(*inputs)
            print(f"✓ {function.__name__}{inputs} = {result}")
        except Exception as e:
            print(f"✗ {function.__name__}{inputs} raised {type(e).__name__}: {e}")

# Example: Test division function
def safe_divide(a, b):
    if b == 0:
        raise ValueError("Division by zero")
    return a / b

test_values_a = [10, 0, -5]
test_values_b = [2, 0, -1]

test_all_input_combinations(safe_divide, [test_values_a, test_values_b])

Recurrence Relations and Recursion

Understanding Recurrence

A recurrence relation defines a sequence based on previous terms.

# Fibonacci: F(n) = F(n-1) + F(n-2)
def fibonacci_recursive(n):
    """Classic recursive Fibonacci (inefficient!)"""
    if n <= 1:
        return n
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

# Memoized version
def fibonacci_memoized(n, memo={}):
    """Fibonacci with memoization (efficient)"""
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    
    memo[n] = fibonacci_memoized(n - 1, memo) + fibonacci_memoized(n - 2, memo)
    return memo[n]

# Iterative version (most efficient)
def fibonacci_iterative(n):
    """Fibonacci using iteration"""
    if n <= 1:
        return n
    
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    
    return b

# Benchmark
import time

n = 35

start = time.time()
result1 = fibonacci_recursive(n)
time1 = time.time() - start

start = time.time()
result2 = fibonacci_memoized(n)
time2 = time.time() - start

start = time.time()
result3 = fibonacci_iterative(n)
time3 = time.time() - start

print(f"Recursive: {result1} in {time1:.4f}s")
print(f"Memoized: {result2} in {time2:.6f}s ({time1/time2:.0f}x faster)")
print(f"Iterative: {result3} in {time3:.6f}s ({time1/time3:.0f}x faster)")

Solving Recurrence Relations

def tower_of_hanoi(n, source, destination, auxiliary):
    """
    Recurrence: T(n) = 2*T(n-1) + 1
    Solution: T(n) = 2^n - 1
    
    Moves n disks from source to destination using auxiliary
    """
    if n == 1:
        print(f"Move disk 1 from {source} to {destination}")
        return 1
    
    # Move n-1 disks to auxiliary
    moves = tower_of_hanoi(n - 1, source, auxiliary, destination)
    
    # Move largest disk to destination
    print(f"Move disk {n} from {source} to {destination}")
    moves += 1
    
    # Move n-1 disks from auxiliary to destination
    moves += tower_of_hanoi(n - 1, auxiliary, destination, source)
    
    return moves

# Example
n_disks = 3
total_moves = tower_of_hanoi(n_disks, 'A', 'C', 'B')
print(f"\nTotal moves for {n_disks} disks: {total_moves}")
print(f"Formula: 2^{n_disks} - 1 = {2**n_disks - 1}")

Algorithm Complexity Analysis

Big O Notation

Measuring algorithm efficiency using discrete math:

import time
import matplotlib.pyplot as plt

def measure_time_complexity():
    """Empirically measure time complexity"""
    
    # Different algorithms with different complexities
    def constant(n):
        """O(1) - Constant time"""
        return n * 2
    
    def logarithmic(n):
        """O(log n) - Logarithmic time"""
        count = 0
        while n > 1:
            n //= 2
            count += 1
        return count
    
    def linear(n):
        """O(n) - Linear time"""
        total = 0
        for i in range(n):
            total += i
        return total
    
    def linearithmic(n):
        """O(n log n) - Linearithmic time"""
        # Merge sort complexity
        if n <= 1:
            return []
        arr = list(range(n))
        return sorted(arr)
    
    def quadratic(n):
        """O(n²) - Quadratic time"""
        total = 0
        for i in range(n):
            for j in range(n):
                total += 1
        return total
    
    # Measure execution times
    sizes = [10, 50, 100, 500, 1000, 2000]
    
    algorithms = {
        'O(1)': constant,
        'O(log n)': logarithmic,
        'O(n)': linear,
        'O(n log n)': linearithmic,
        'O(n²)': quadratic
    }
    
    results = {name: [] for name in algorithms}
    
    for n in sizes:
        for name, func in algorithms.items():
            start = time.time()
            func(n)
            elapsed = time.time() - start
            results[name].append(elapsed)
    
    # Print results
    print("Algorithm Complexity Benchmark:")
    print(f"{'Size':>6} | {'O(1)':>10} | {'O(log n)':>10} | {'O(n)':>10} | "
          f"{'O(n log n)':>12} | {'O(n²)':>10}")
    print("-" * 75)
    
    for i, n in enumerate(sizes):
        times = [f"{results[name][i]*1000:.4f}ms" for name in algorithms]
        print(f"{n:>6} | {times[0]:>10} | {times[1]:>10} | {times[2]:>10} | "
              f"{times[3]:>12} | {times[4]:>10}")

measure_time_complexity()

Analyzing Your Own Code

def analyze_complexity(func, test_sizes):
    """
    Analyze time complexity by running with different input sizes
    and observing how runtime scales
    """
    times = []
    
    for size in test_sizes:
        start = time.time()
        func(size)
        elapsed = time.time() - start
        times.append(elapsed)
    
    # Check growth pattern
    print(f"\nComplexity Analysis for {func.__name__}:")
    print(f"{'Size':>8} | {'Time':>12} | {'Ratio':>8}")
    print("-" * 35)
    
    for i, (size, t) in enumerate(zip(test_sizes, times)):
        if i > 0:
            ratio = t / times[i-1]
            size_ratio = size / test_sizes[i-1]
            print(f"{size:>8} | {t*1000:>10.4f}ms | {ratio:>8.2f}x")
            
            # Guess complexity
            if i == len(times) - 1:
                if abs(ratio - 1) < 0.2:
                    print("\nLikely O(1) - constant time")
                elif abs(ratio - size_ratio) < 0.2:
                    print("\nLikely O(n) - linear time")
                elif abs(ratio - size_ratio**2) < 0.5:
                    print("\nLikely O(n²) - quadratic time")
                elif abs(ratio - size_ratio * np.log2(size_ratio)) < 0.3:
                    print("\nLikely O(n log n) - linearithmic time")
        else:
            print(f"{size:>8} | {t*1000:>10.4f}ms | {'--':>8}")

# Test a function
def bubble_sort(n):
    """O(n²) algorithm"""
    arr = list(range(n, 0, -1))
    for i in range(len(arr)):
        for j in range(len(arr) - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

analyze_complexity(bubble_sort, [100, 200, 400, 800])

Choosing the Right Data Structure

class DataStructureComparison:
    """Compare operations on different data structures"""
    
    @staticmethod
    def compare_search():
        """Compare search operations"""
        import time
        
        n = 10000
        data = list(range(n))
        
        # List search: O(n)
        start = time.time()
        result = 5000 in data
        list_time = time.time() - start
        
        # Set search: O(1) average
        data_set = set(data)
        start = time.time()
        result = 5000 in data_set
        set_time = time.time() - start
        
        # Dict search: O(1) average
        data_dict = {x: x for x in data}
        start = time.time()
        result = 5000 in data_dict
        dict_time = time.time() - start
        
        print("Search Performance (n=10,000):")
        print(f"List (O(n)):     {list_time*1e6:.2f} μs")
        print(f"Set (O(1)):      {set_time*1e6:.2f} μs ({list_time/set_time:.0f}x faster)")
        print(f"Dict (O(1)):     {dict_time*1e6:.2f} μs ({list_time/dict_time:.0f}x faster)")
    
    @staticmethod
    def compare_insertion():
        """Compare insertion operations"""
        import time
        
        n = 5000
        
        # List append: O(1) amortized
        start = time.time()
        lst = []
        for i in range(n):
            lst.append(i)
        list_append_time = time.time() - start
        
        # List insert at beginning: O(n)
        start = time.time()
        lst = []
        for i in range(n):
            lst.insert(0, i)
        list_insert_time = time.time() - start
        
        # Set add: O(1) average
        start = time.time()
        s = set()
        for i in range(n):
            s.add(i)
        set_add_time = time.time() - start
        
        print("\nInsertion Performance (n=5,000):")
        print(f"List append (O(1)):      {list_append_time*1000:.2f} ms")
        print(f"List insert 0 (O(n)):    {list_insert_time*1000:.2f} ms")
        print(f"Set add (O(1)):          {set_add_time*1000:.2f} ms")

# Run comparisons
DataStructureComparison.compare_search()
DataStructureComparison.compare_insertion()

Pigeonhole Principle

If you have more pigeons than holes, at least one hole must have multiple pigeons.

def demonstrate_pigeonhole_principle():
    """
    Real application: Birthday paradox
    In a room of 23 people, >50% chance two share a birthday
    """
    import random
    
    def birthday_collision(n_people, n_trials=10000):
        """Simulate birthday collisions"""
        collisions = 0
        
        for _ in range(n_trials):
            birthdays = [random.randint(1, 365) for _ in range(n_people)]
            if len(birthdays) != len(set(birthdays)):
                collisions += 1
        
        return collisions / n_trials
    
    print("Birthday Paradox (Pigeonhole Principle):")
    print(f"{'People':>8} | {'Collision Probability':>25}")
    print("-" * 36)
    
    for n in [10, 20, 23, 30, 40, 50]:
        prob = birthday_collision(n)
        print(f"{n:>8} | {prob:>24.1%}")

demonstrate_pigeonhole_principle()

Key Takeaways

• Set theory provides efficient data structure operations

• Logic and Boolean algebra optimize conditionals and circuits

• Combinatorics counts possibilities and tests edge cases

• Recurrence relations solve recursive problems mathematically

• Big O notation analyzes algorithm efficiency

• Choosing the right data structure can improve performance by orders of magnitude

• Discrete math is the foundation of algorithm design

What's Next

In the next article, we'll explore number theory and cryptography—the mathematics behind hashing, encryption, and secure systems.

You'll learn:

• Modular arithmetic in practice

• Prime numbers and factorization

• Cryptographic functions

• Building secure authentication

Continue to Part 6: Number Theory and Cryptography →

---

Navigation

• ← Part 4: Probability and Statistics

• Back to Series Overview

• Part 6: Number Theory and Cryptography →