Discrete Mathematics

Discrete Mathematics

What I Do

I provide comprehensive discrete mathematics tools including combinatorics, graph algorithms, logical reasoning, set operations, recurrence relations, and number theory operations essential for computer science and cryptography.

When to Use Me

• Algorithm analysis and design
• Cryptography and security
• Network and graph problems
• Counting and combinatorics
• Logic and proof techniques
• Optimization problems

Core Concepts

• Combinatorics: Permutations, combinations, binomial coefficients
• Graph Theory: Paths, cycles, connectivity, coloring
• Logic: Propositional logic, predicates, inference
• Set Theory: Operations, relations, functions
• Number Theory: Divisibility, primes, modular arithmetic
• Recurrence Relations: Linear recurrences, generating functions
• Proof Techniques: Induction, contradiction, direct proof
• Asymptotic Analysis: Big O, Omega, Theta notation

Code Examples

Combinatorics

from math import comb, perm, factorial
import numpy as np

n, k = 10, 3

combinations = comb(n, k)
permutations = perm(n, k)
factorial_n = factorial(n)

print(f"C(10,3) = {combinations}")
print(f"P(10,3) = {permutations}")
print(f"10! = {factorial_n}")

def multinomial(n_list):
    total = sum(n_list)
    result = factorial(total)
    for n in n_list:
        result //= factorial(n)
    return result

Graph Algorithms

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    order = []
    
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
print(f"BFS order: {bfs(graph, 'A')}")

Modular Arithmetic

def extended_gcd(a, b):
    if b == 0:
        return (a, 1, 0)
    else:
        g, x1, y1 = extended_gcd(b, a % b)
        x = y1
        y = x1 - (a // b) * y1
        return (g, x, y)

def mod_inverse(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        return None
    return x % m

print(f"Mod inverse of 17 mod 43: {mod_inverse(17, 43)}")

Recurrence Relations

from functools import lru_cache

@lru_cache(None)
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

print(f"Fibonacci(10): {fibonacci(10)}")

def solve_linear_recurrence(coeffs, initial, n):
    k = len(coeffs)
    dp = initial[:k]
    for i in range(k, n+1):
        next_val = sum(coeffs[j] * dp[i-j-1] for j in range(k))
        dp.append(next_val)
    return dp[n]

Set Operations

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

union = A | B
intersection = A & B
difference = A - B
symmetric_diff = A ^ B

print(f"Union: {union}")
print(f"Intersection: {intersection}")
print(f"A - B: {difference}")
print(f"Symmetric diff: {symmetric_diff}")

def cartesian_product(set1, set2):
    return {(a, b) for a in set1 for b in set2}

Best Practices

1. Memoization: Cache computed results for recursion
2. Graph Representation: Choose appropriate structure (adjacency list/matrix)
3. Modular Arithmetic: Use pow(a, -1, m) in Python 3.8+
4. Combinatorial Growth: Beware of factorial growth
5. Algorithm Complexity: Analyze time and space complexity

Common Patterns

# DFS with recursion
def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

# Topological sort (Kahn's algorithm)
def topological_sort(graph):
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1
    
    queue = deque([node for node in in_degree if in_degree[node] == 0])
    topo_order = []
    
    while queue:
        node = queue.popleft()
        topo_order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    return topo_order

Core Competencies

1. Combinatorics and counting
2. Graph algorithms and traversals
3. Modular arithmetic and number theory
4. Set operations and relations
5. Recurrence relations and dynamic programming