Discrete Mathematics

• "5 is greater than 3" -- this is true
• "The Earth is flat" -- this is false
• "2 + 2 = 4" -- this is true

Not propositions: "What time is it?" (question), "Close the door" (command), "x + 5 = 10" (depends on x -- this is a predicate, not a proposition).

# These two are equivalent:
if not (is_admin and is_logged_in):
    deny_access()

# Same as:
if (not is_admin) or (not is_logged_in):
    deny_access()

If A = {1, 2, 3}, then 2 ∈ A is true and 7 ∈ A is false.

Given A = {1, 2, 3, 4, 5} and B = {3, 4, 5, 6, 7}:

• A ∪ B = {1, 2, 3, 4, 5, 6, 7} -- everything from both
• A ∩ B = {3, 4, 5} -- only the overlap
• A \ B = {1, 2} -- in A but not B
• B \ A = {6, 7} -- in B but not A

A = {1, 2, 3, 4, 5}
B = {3, 4, 5, 6, 7}

print(A | B)   # Union:        {1, 2, 3, 4, 5, 6, 7}
print(A & B)   # Intersection: {3, 4, 5}
print(A - B)   # Difference:   {1, 2}
print(A ^ B)   # Symmetric difference (XOR): {1, 2, 6, 7}

print(3 in A)  # Membership: True
print(len(A))  # Cardinality: 5

Let A = {1, 2, 3} and B = {a, b}. The Cartesian product A × B is:

{(1,a), (1,b), (2,a), (2,b), (3,a), (3,b)}

A relation R might be: R = {(1,a), (2,b), (3,a)} -- this picks out specific connections.

f(x) = 2x from integers to integers:

• Injective? Yes -- different inputs give different outputs (if 2a = 2b then a = b).
• Surjective? No -- odd numbers like 3 are never output by f.
• Bijective? No -- not surjective.

f(x) = 2x + 3. To find f^-1, solve y = 2x + 3 for x:

x = (y - 3) / 2, so f^-1(y) = (y - 3) / 2

Check: f^-1(f(5)) = f^-1(13) = (13 - 3)/2 = 5. It works.

Claim: If n is even, then n² is even.

Proof:

1. Assume n is even. By definition, n = 2k for some integer k.
2. Then n² = (2k)² = 4k² = 2(2k²).
3. Since 2k² is an integer, n² = 2(integer), so n² is even. □

Claim: √2 is irrational.

Proof:

1. Assume √2 is rational. Then √2 = a/b where a, b are integers with no common factors.
2. Squaring both sides: 2 = a²/b², so a² = 2b².
3. This means a² is even, so a must be even. Write a = 2c.
4. Then (2c)² = 2b², so 4c² = 2b², so b² = 2c².
5. This means b² is even, so b is even.
6. Contradiction: Both a and b are even, so they share factor 2. But we said they have no common factors.
7. Therefore √2 is irrational. □

Claim: The sum 1 + 2 + 3 + ... + n = n(n+1)/2 for all n ≥ 1.

Base case (n = 1):

Left side: 1. Right side: 1(1+1)/2 = 1. They match. Base case holds.

Inductive hypothesis: Assume the formula holds for n = k:

Inductive step: Prove it holds for n = k + 1:

The formula holds for k + 1. By induction, it holds for all n ≥ 1. □

Claim: If n² is even, then n is even.

Contrapositive: If n is odd, then n² is odd.

Proof: If n is odd, then n = 2k + 1. So n² = (2k+1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd. □

A restaurant has 3 appetizers and 5 entrees. How many different meals (one appetizer + one entree) can you order?

3 × 5 = 15 meals

In CS terms: A 4-bit number has 2 × 2 × 2 × 2 = 2⁴ = 16 possible values. An 8-character password using 26 lowercase letters has 26⁸ = 208 billion possibilities.

How many ways can 3 students win gold, silver, and bronze medals from a class of 10?

P(10, 3) = 10! / 7! = 10 × 9 × 8 = 720 ways

Order matters because gold-silver-bronze is a different outcome than bronze-silver-gold.

How many ways can you pick a committee of 3 people from 10?

C(10, 3) = 10! / (3! × 7!) = 720 / 6 = 120 ways

Order doesn't matter because {Alice, Bob, Carol} is the same committee as {Carol, Alice, Bob}.

• In any group of 367 people, at least two share a birthday (366 possible days + 1).
• If you have 5 pairs of socks in a dark room and grab 6, you must have at least one matching pair.
• CS application: If a hash function maps to 2³² values, then with 2³² + 1 inputs, at least two must collide (same hash). This is why hash collisions are inevitable.

How many ways can you put 10 identical balls into 4 different boxes?

C(10 + 4 - 1, 4 - 1) = C(13, 3) = 286 ways

Visualization: Imagine 10 balls in a row: ○○○○○○○○○○. Adding 3 dividers creates 4 groups. We're choosing where to place 3 dividers among 13 positions.

In a class of 100 students, 60 take Math, 50 take Physics, and 20 take both. How many take at least one?

|Math ∪ Physics| = 60 + 50 - 20 = 90 students

The -20 removes those who were counted twice (in both classes).

How many ways can you arrange the letters in "MISSISSIPPI"?

Total: 11 letters. M: 1, I: 4, S: 4, P: 2

11! / (1! × 4! × 4! × 2!) = 39,916,800 / (1 × 24 × 24 × 2) = 34,650 arrangements

An ice cream shop has 5 flavors. How many ways can you choose 3 scoops (repeats allowed)?

C(5 + 3 - 1, 3) = C(7, 3) = 35 ways

This includes choices like (chocolate, chocolate, vanilla) or (strawberry, strawberry, strawberry).

5 people put their hats in a pile and randomly pick one. How many ways can NO ONE get their own hat?

D(5) = 5! × (1 - 1 + 1/2 - 1/6 + 1/24 - 1/120)

= 120 × (0 + 0.5 - 0.167 + 0.042 - 0.008)

= 120 × 0.367 = 44 derangements

Fun fact: As n gets large, approximately 1/e (≈ 36.8%) of all permutations are derangements.

= C(4,0)x⁴ + C(4,1)x³y + C(4,2)x²y² + C(4,3)xy³ + C(4,4)y⁴

= x⁴ + 4x³y + 6x²y² + 4xy³ + y⁴

Pascal's Triangle: The coefficients (1, 4, 6, 4, 1) form row 4 of Pascal's triangle!

# Graph: A--B, A--C, B--C
#     A  B  C
# A [ 0, 1, 1 ]
# B [ 1, 0, 1 ]
# C [ 1, 1, 0 ]

matrix = [
    [0, 1, 1],
    [1, 0, 1],
    [1, 1, 0]
]

Space: O(V²). Edge lookup: O(1). Best for dense graphs.

# Same graph: A--B, A--C, B--C
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C'],
    'C': ['A', 'B']
}

Space: O(V + E). Edge lookup: O(degree). Best for sparse graphs (most real-world graphs).

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    while queue:
        vertex = queue.popleft()
        print(vertex, end=' ')
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=' ')
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

This is the problem that founded graph theory. The city of Konigsberg had 7 bridges connecting 4 land masses. Euler proved it was impossible to walk across every bridge exactly once because more than two vertices had odd degree.

Find GCD(252, 105):

• GCD(252, 105): 252 mod 105 = 42, so GCD(105, 42)
• GCD(105, 42): 105 mod 42 = 21, so GCD(42, 21)
• GCD(42, 21): 42 mod 21 = 0, so GCD = 21

Compute (987654321 × 123456789) mod 1000000007 without overflow:

# Instead of computing the huge product first:
a = 987654321 % 1000000007
b = 123456789 % 1000000007
result = (a * b) % 1000000007
print(result)  # Safe from overflow in languages with fixed-width integers

Simplify: F = AB + A¬B + ¬AB

• F = A(B + ¬B) + ¬AB    // Factor out A
• F = A(1) + ¬AB    // Complement law: B + ¬B = 1
• F = A + ¬AB    // Identity law: A · 1 = A
• F = A + B    // Absorption: A + ¬AB = A + B

We reduced a complex expression to A + B (just an OR gate).

A half adder adds two single-bit numbers. It needs two outputs: the sum and the carry.

This is literally how your CPU adds numbers -- chains of logic gates.

def get_first(arr):
    return arr[0]  # Always one operation, regardless of array size

def find_max(arr):
    max_val = arr[0]
    for num in arr:       # Loops through n elements
        if num > max_val:
            max_val = num
    return max_val       # O(n) -- one loop over the data

def has_duplicate(arr):
    for i in range(len(arr)):         # n iterations
        for j in range(i + 1, len(arr)):  # n iterations (roughly)
            if arr[i] == arr[j]:
                return True
    return False                       # O(n^2) -- nested loop

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1           # Eliminate half the data
        else:
            hi = mid - 1           # Eliminate half the data
    return -1                       # O(log n) -- halving each step

Why log n? If you halve n repeatedly: n → n/2 → n/4 → ... → 1. How many halves until you reach 1? That's log₂(n). This is the *inverse* of exponential growth.

def all_pairs(arr1, arr2):
    """Find all pairs from two arrays"""
    pairs = []
    for a in arr1:          # N iterations (arr1 has N elements)
        for b in arr2:      # M iterations (arr2 has M elements)
            pairs.append((a, b))
    return pairs             # O(N × M) -- every element of arr1 pairs with every element of arr2

# If arr1 has 100 elements and arr2 has 50 elements: 100 × 50 = 5,000 pairs

def process_both(arr1, arr2):
    """Process both arrays separately"""
    total = 0
    for a in arr1:           # N iterations
        total += a
    for b in arr2:           # M iterations (after arr1 loop finishes)
        total += b
    return total              # O(N + M) -- sequential, not nested!

# If arr1 has 100 elements and arr2 has 50 elements: 100 + 50 = 150 operations

If both arrays have the same size n, then O(N×M) = O(n×n) = O(n²). That's why nested loops over the same array are O(n²).

def same_array_pairs(arr):
    for i in arr:       # n iterations
        for j in arr:   # n iterations
            print(i, j)  # O(n²) because N = M = n

def merge_sorted(arr1, arr2):
    """Merge two sorted arrays into one sorted array"""
    result = []
    i, j = 0, 0

    # Each element is visited at most once
    while i < len(arr1) and j < len(arr2):
        if arr1[i] <= arr2[j]:
            result.append(arr1[i])
            i += 1
        else:
            result.append(arr2[j])
            j += 1

    # Add remaining elements
    result.extend(arr1[i:])
    result.extend(arr2[j:])
    return result
    # Total: each element from arr1 and arr2 processed once = O(N + M)

Key insight: Total iterations ≤ N + M because we increment i or j each time, and they can only reach N and M respectively.

def sum_matrix(matrix):
    """Matrix with N rows and M columns"""
    total = 0
    for row in matrix:           # N rows
        for val in row:          # M columns per row
            total += val
    return total                  # O(N × M) or O(rows × cols)

For a square matrix where N = M, this is O(n²). For a 100×3 matrix, it's O(100 × 3) = O(300) = O(N × M).

def check_windows(arr, k):
    """Check all windows of size k in array of size n"""
    for i in range(len(arr) - k + 1):  # N - K + 1 ≈ N windows
        for j in range(k):              # K elements per window
            print(arr[i + j])
    # O(N × K) total
    # If K is a constant (like 3), this simplifies to O(N)
    # If K could be as large as N, worst case is O(N²)

def triangular_loop(n):
    for i in range(n):
        for j in range(i):  # j goes from 0 to i-1
            print(i, j)
    # Iterations: 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 = O(n²)

Even though the inner loop varies, the total is the sum of 0 + 1 + 2 + ... + (n-1), which equals n(n-1)/2. Using the formula for arithmetic series (covered in Sequences and Series), this is O(n²).

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)
    # Calls: factorial(n) → factorial(n-1) → ... → factorial(1)
    # That's n calls, each doing O(1) work
    # Total: O(n)

Recurrence: T(n) = T(n-1) + O(1), which solves to T(n) = O(n)

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)
    # Each call spawns TWO more calls!
    # Call tree grows exponentially: 1 → 2 → 4 → 8 → ...
    # Total calls ≈ 2ⁿ, so O(2ⁿ)

Recurrence: T(n) = T(n-1) + T(n-2) + O(1). The solution is O(φⁿ) where φ ≈ 1.618 (golden ratio), but we approximate as O(2ⁿ).

Why this is terrible: For n=50, this makes about 10¹⁵ calls. Dynamic programming fixes this to O(n)!

def binary_search_recursive(arr, target, lo, hi):
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, hi)
    else:
        return binary_search_recursive(arr, target, lo, mid - 1)
    # Each call halves the search space
    # n → n/2 → n/4 → ... → 1 = log₂(n) calls
    # O(log n)

Recurrence: T(n) = T(n/2) + O(1), which solves to T(n) = O(log n)

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])     # T(n/2)
    right = merge_sort(arr[mid:])    # T(n/2)
    return merge(left, right)         # O(n) to merge

    # Recurrence: T(n) = 2T(n/2) + O(n)
    # By Master Theorem: O(n log n)

Visual intuition: We split the array log(n) times (levels of recursion). At each level, we do O(n) total work merging. So: O(n) × O(log n) = O(n log n).

• factorial(n): Depth is n, each frame is O(1) → O(n) space
• binary_search: Depth is log(n), each frame is O(1) → O(log n) space
• merge_sort: Depth is log(n), but we also create new arrays → O(n) space
• naive fib: Maximum depth is n (following one branch) → O(n) space

def merge_sort(arr):
    if len(arr) <= 1:                  # T(1) = 1  (base case)
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])        # T(n/2)    (first recursive call)
    right = merge_sort(arr[mid:])       # T(n/2)    (second recursive call)
    return merge(left, right)            # + O(n)    (combining step)
    # Total: T(n) = 2T(n/2) + n

This is like factorial's call structure: one recursive call, O(1) work each time.

• T(n) = T(n-1) + 1
• = [T(n-2) + 1] + 1 = T(n-2) + 2
• = [T(n-3) + 1] + 2 = T(n-3) + 3
• Pattern spotted: T(n) = T(n-k) + k
• Base case when n-k = 1, so k = n-1:
• T(n) = T(1) + (n-1) = 1 + (n-1) = n = O(n)

This is like selection sort: one recursive call, but O(n) work each time (shrinking).

• T(n) = T(n-1) + n
• = [T(n-2) + (n-1)] + n = T(n-2) + (n-1) + n
• = T(n-3) + (n-2) + (n-1) + n
• Pattern: T(n) = T(1) + 2 + 3 + ... + n
• = 1 + (2 + 3 + ... + n) = n(n+1)/2 = O(n²)

See how the recurrence naturally produced an arithmetic series? That's the summation 1+2+...+n from the sequences page!

This is the most important one. Let's unroll it carefully:

• T(n) = 2T(n/2) + n
• = 2[2T(n/4) + n/2] + n = 4T(n/4) + n + n = 4T(n/4) + 2n
• = 4[2T(n/8) + n/4] + 2n = 8T(n/8) + n + 2n = 8T(n/8) + 3n
• Pattern: After k expansions: T(n) = 2^k × T(n/2^k) + kn
• Base case when n/2^k = 1, so k = log₂(n):
• T(n) = n × T(1) + n × log₂(n) = n + n log n = O(n log n)

Intuition: There are log₂(n) levels of recursion. At each level, the total work across all calls is n. So total work = n × log n.

• T(n) = T(n/2) + 1
• = T(n/4) + 1 + 1 = T(n/4) + 2
• = T(n/8) + 3
• Pattern: T(n) = T(n/2^k) + k
• Base case when n/2^k = 1, so k = log₂(n):
• T(n) = T(1) + log₂(n) = 1 + log n = O(log n)

Intuition: Each call halves the problem and does O(1) work. How many halvings until size 1? log₂(n).

Merge sort: T(n) = 2T(n/2) + O(n). a=2, b=2, d=1.

log₂(2) = 1 = d → Case 2 → T(n) = O(n¹ log n) = O(n log n)

Binary search: T(n) = T(n/2) + O(1). a=1, b=2, d=0.

log₂(1) = 0 = d → Case 2 → T(n) = O(n⁰ log n) = O(log n)

Karatsuba multiplication: T(n) = 3T(n/2) + O(n). a=3, b=2, d=1.

log₂(3) ≈ 1.58 > 1 = d → Case 3 → T(n) = O(n^1.58)

Strassen's matrix multiply: T(n) = 7T(n/2) + O(n²). a=7, b=2, d=2.

log₂(7) ≈ 2.81 > 2 = d → Case 3 → T(n) = O(n^2.81)