Discrete Mathematics

Set Theory

• Basic Notation: Set $A = \{1, 2, 3\}$
• Operations:
  • Union: $A \cup B$
  • Intersection: $A \cap B$
  • Difference: $A \setminus B$
  • Complement: $A^c$
• Set Properties:
  • De Morgan’s Laws:
    • $(A \cup B)^c = A^c \cap B^c$
    • $(A \cap B)^c = A^c \cup B^c$

Logic

• Logical Operators:
  • AND ($\land$)
  • OR ($\lor$)
  • NOT ($\neg$)
  • Implies ($\implies$)
  • Equivalent ($\iff$)
• Truth Tables:
  • $p \land q \equiv \neg(\neg p \lor \neg q)$

Number Theory

• Division Algorithm: $a = bq + r$ where $0 \leq r < b$
• GCD: $\gcd(a,b) = \gcd(b, a \bmod b)$
• Prime Numbers: Numbers with exactly two factors
• Modular Arithmetic: $(a \bmod n)$

Linear Algebra

Vectors

• Vector Operations:
  • Addition: $\vec{a} + \vec{b}$
  • Scalar Multiplication: $c\vec{a}$
  • Dot Product: $\vec{a} \cdot \vec{b} = \sum_{i=1}^n a_ib_i$

Matrices

• Matrix Operations:
  • Addition: $(A + B)_{ij} = A_{ij} + B_{ij}$
  • Multiplication: $(AB)_{ij} = \sum_k A_{ik}B_{kj}$
• Special Matrices:
  • Identity Matrix: $I_n$
  • Transpose: $A^T$
  • Inverse: $A^{-1}$

Calculus

Derivatives

• Basic Rules:
  • Power Rule: $\frac{d}{dx}x^n = nx^{n-1}$
  • Product Rule: $\frac{d}{dx}(fg) = f'g + fg'$
  • Chain Rule: $\frac{d}{dx}f(g(x)) = f'(g(x))g'(x)$

Integrals

• Definite Integral: $\int_a^b f(x)dx$
• Fundamental Theorem: $\int_a^b f(x)dx = F(b) - F(a)$

Probability & Statistics

Probability

• Basic Probability: $P(A) = \frac{\text{favorable outcomes}}{\text{total outcomes}}$
• Conditional Probability: $P(A|B) = \frac{P(A \cap B)}{P(B)}$
• Bayes’ Theorem: $P(A|B) = \frac{P(B|A)P(A)}{P(B)}$

Statistics

• Mean: $\mu = \frac{1}{n}\sum_{i=1}^n x_i$
• Variance: $\sigma^2 = \frac{1}{n}\sum_{i=1}^n (x_i - \mu)^2$
• Standard Deviation: $\sigma = \sqrt{\sigma^2}$

Graph Theory

Basic Concepts

• Graph: $G = (V, E)$
• Degree: Number of edges incident to a vertex
• Path: Sequence of vertices connected by edges

Important Theorems

• Handshaking Lemma: $\sum_{v \in V} \deg(v) = 2|E|$
• Euler’s Formula: For planar graphs: $V - E + F = 2$

Computational Complexity

Big-O Notation

• $O(1)$ - Constant
• $O(\log n)$ - Logarithmic
• $O(n)$ - Linear
• $O(n \log n)$ - Linearithmic
• $O(n^2)$ - Quadratic
• $O(2^n)$ - Exponential

Space Complexity

• Stack Space: $O(n)$ for recursive calls
• Heap Space: Dynamic memory allocation

Boolean Algebra

Laws

• Commutative: $a + b = b + a$
• Associative: $(a + b) + c = a + (b + c)$
• Distributive: $a(b + c) = ab + ac$
• Identity: $a + 0 = a$, $a \cdot 1 = a$
• Complement: $a + \bar{a} = 1$, $a \cdot \bar{a} = 0$

Numerical Methods

Root Finding

• Newton’s Method: $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$
• Bisection Method: Binary search for roots

Interpolation

• Linear: $y = y_0 + \frac{y_1-y_0}{x_1-x_0}(x-x_0)$
• Lagrange: $P(x) = \sum_{i=0}^n y_i \prod_{j\neq i} \frac{x-x_j}{x_i-x_j}$

Note: This cheat sheet covers fundamental mathematical concepts essential for computer science. For deeper understanding, always refer to detailed resources and practice problems.