Laplace Transform Properties

The Laplace Transform Definition

• Defined for real numbers $t \geq 0$.
• Denoted as $F(s) = \mathcal{L} {f(t)} = \int_{0}^{\infty} e^{-st} f(t) dt$.
• $s$ is a complex number frequency parameter where $s = \sigma + j\omega$.

Region of Convergence (ROC)

• Exists when the defining integral converges.
• Convergence occurs when $Re(s) > a$ for some real number $a$.
• Region of convergence is given by $Re(s) > a$.

Linearity

• The Laplace transform of a linear combination of functions is the linear combination of their Laplace transforms.
• $\mathcal{L} {af(t) + bg(t)} = a\mathcal{L} {f(t)} + b\mathcal{L} {g(t)}$.

Time Scaling

• $\mathcal{L} {f(at)} = \frac{1}{|a|} F(\frac{s}{a})$.

Time Shifting

• $\mathcal{L} {f(t - a)u(t - a)} = e^{-as}F(s)$.
• $u(t)$ is the Heaviside step function.

Shifting in the s-Domain

• $\mathcal{L} {e^{at}f(t)} = F(s - a)$.

Differentiation in the Time Domain

• First derivative: $\mathcal{L} {\frac{d}{dt}f(t)} = sF(s) - f(0)$.
• Second derivative: $\mathcal{L} {\frac{d^2}{dt^2}f(t)} = s^2F(s) - sf(0) - f'(0)$.
• nth derivative: $\mathcal{L} {\frac{d^n}{dt^n}f(t)} = s^nF(s) - s^{n-1}f(0) - s^{n-2}f'(0) -... - f^{(n-1)}(0)$.

Integration in the Time Domain

• $\mathcal{L} {\int_{0}^{t} f(\tau) d\tau} = \frac{F(s)}{s}$.

Differentiation in the s-Domain

• $\mathcal{L} {tf(t)} = -\frac{d}{ds}F(s)$.
• $\mathcal{L} {t^nf(t)} = (-1)^n \frac{d^n}{ds^n}F(s)$.

Convolution

• $\mathcal{L} {(f * g)(t)} = F(s)G(s)$.
• $(f * g)(t) = \int_{0}^{t} f(\tau)g(t - \tau) d\tau$.

Initial Value Theorem

• $\lim_{t \to 0} f(t) = \lim_{s \to \infty} sF(s)$.

Final Value Theorem

• $\lim_{t \to \infty} f(t) = \lim_{s \to 0} sF(s)$.

Common Laplace Transforms

Unit Impulse

• $f(t) = \delta(t)$.
• $F(s) = 1$.
• ROC: All s.

Unit Step

• $f(t) = u(t)$.
• $F(s) = \frac{1}{s}$.
• ROC: $Re(s) > 0$.

Ramp

• $f(t) = t$.
• $F(s) = \frac{1}{s^2}$.
• ROC: $Re(s) > 0$.

Exponential

• $f(t) = e^{at}$.
• $F(s) = \frac{1}{s - a}$.
• ROC: $Re(s) > Re(a)$.

Sine

• $f(t) = \sin(\omega t)$.
• $F(s) = \frac{\omega}{s^2 + \omega^2}$.
• ROC: $Re(s) > 0$.

Cosine

• $f(t) = \cos(\omega t)$.
• $F(s) = \frac{s}{s^2 + \omega^2}$.
• ROC: $Re(s) > 0$.

Hyperbolic Sine

• $f(t) = \sinh(at)$.
• $F(s) = \frac{a}{s^2 - a^2}$.
• ROC: $Re(s) > |a|$.

Hyperbolic Cosine

• $f(t) = \cosh(at)$.
• $F(s) = \frac{s}{s^2 - a^2}$.
• ROC: $Re(s) > |a|$.

Damped Sine

• $f(t) = e^{-at}\sin(\omega t)$.
• $F(s) = \frac{\omega}{(s + a)^2 + \omega^2}$.
• ROC: $Re(s) > -a$.

Damped Cosine

• $f(t) = e^{-at}\cos(\omega t)$.
• $F(s) = \frac{s + a}{(s + a)^2 + \omega^2}$.
• ROC: $Re(s) > -a$.

t to the power of n

• $f(t) = t^n$.
• $F(s) = \frac{n!}{s^{n+1}}$.
• ROC: $Re(s) > 0$.

Physics: Vectors

Vector Sum - Graphical Method

• Place vectors A and B sequentially, keeping magnitude, direction, and sense.
• Resultant R is from the origin of the first to the end of the last vector.

Vector Sum - Analytical Method

• Formulas for rectangular components of a vector.
• $A_x = A \cos \theta$.
• $A_y = A \sin \theta$.
• Sum by components:
  • $R_x = A_x + B_x +...$
  • $R_y = A_y + B_y +...$
  • $R = \sqrt{R_x^2 + R_y^2}$.
  • $\theta = \arctan \frac{R_y}{R_x}$.

Dot Product (Scalar)

• Represented as $\vec{A} \cdot \vec{B} = AB \cos \theta = A_x B_x + A_y B_y + A_z B_z$.
• The result is a scalar.

Cross Product (Vector)

• Represented as $\vec{A} \times \vec{B} = AB \sin \theta \hat{n}$.
• Calculated as the determinant with unit vectors i, j, k:
• $\vec{A} \times \vec{B} = \begin{vmatrix} \hat{i} & \hat{j} & \hat{k} \ A_x & A_y & A_z \ B_x & B_y & B_z \end{vmatrix} = (A_y B_z - A_z B_y)\hat{i} + (A_z B_x - A_x B_z)\hat{j} + (A_x B_y - A_y B_x)\hat{k}$.
• The result is a vector, perpendicular to the plane formed by vectors A and B, sense determined by the right-hand rule.

Semiconductor Energy Bands and Charge Carriers

Energy Bands

• E vs. k Diagram: Solutions to Schrödinger's equation in a crystal lattice.
• Metals: Fermi level within an allowed band (partially filled).
• Semiconductors: Fermi level in a band gap (full valence, empty conduction).
• Insulators: Fermi level in a large band gap.

Intrinsic Semiconductor

• Perfect crystal, no impurities or defects.
• Silicon (Si) and Germanium (Ge) are Group IV elements, covalently bonded to four neighbors.
• At $T = 0K$, valence band is full, conduction band is empty.
• Intrinsic Carrier Concentration: $n = p = n_i$ at $T > 0K$ (electron-hole pairs).
• $n_i$ increases exponentially with temperature.
• Fermi level ($E_F$) is near the middle of the band gap ($E_g$).
• $n_i = \sqrt{N_c N_v} e^{-E_g / 2kT}$
  • $N_c$ is the effective density of states in the conduction band.
  • $N_v$ is the effective density of states in the valence band.
  • $E_g$ is the band gap energy.
  • $k$ is Boltzmann's constant.
  • $T$ is the temperature in Kelvin.

Extrinsic Semiconductor

• Doping: Intentionally adding impurities to control electrical properties.
• n-type: Doped with donor impurities (more valence electrons), $n > n_i$, $E_F$ closer to $E_c$.
• p-type: Doped with acceptor impurities (fewer valence electrons), $p > n_i$, $E_F$ closer to $E_v$.
• Compensation: Both donors and acceptors present; conductivity type determined by higher concentration.

Carrier Transport Phenomena

• Drift: Motion of carriers due to an electric field.
• $J_{drift} = \sigma E = q(n\mu_n + p\mu_p)E$
  • $\sigma$ is the conductivity.
  • $E$ is the electric field.
  • $q$ is the elementary charge.
  • $n$ and $p$ are electron and hole concentrations.
  • $\mu_n$ and $\mu_p$ are electron and hole mobilities.
• Diffusion: Movement from high to low concentration.
• $J_{diffusion} = qD_n \frac{dn}{dx} - qD_p \frac{dp}{dx}$
  • $D_n$ and $D_p$ are electron and hole diffusion coefficients.
  • $\frac{dn}{dx}$ and $\frac{dp}{dx}$ are electron and hole concentration gradients.
• Einstein Relation: $\frac{D_n}{\mu_n} = \frac{D_p}{\mu_p} = \frac{kT}{q}$.
  • $k$ is Boltzmann's constant.
  • $T$ is the temperature in Kelvin.
  • $q$ is the elementary charge.

Algorithmic Complexity

Purpose

• The ability to quantify the resources that an algorithm requires, like time or memory.
• The ability to compare efficiencies between algorithms.
• The ability to predict how an algorithm will behave given scaling input sizes.

Uses

• Can assist in choosing the correct algorithm.
• Can help optimize code.
• Helps to understand the limits of computation.

Understanding Big-O Notation

• The variable $f(n) = O(g(n))$ if there are constants $c$ and $n_0$ such that $f(n) \le cg(n)$ when $n \ge n_0$.
• It is that $f(n)$ does not grow any faster than $g(n)$ does as $n$ grows.
• $n^2 + n = O(n^2)$.
• $100n = O(n)$.
• $\log(n) = O(n)$.

Common Complexities

• Constant ($O(1)$): It takes the same amount of time to perform the function no matter the array size (Accessing array element).
• Logarithmic ($O(log n)$): Time increases proportionally to the logarithm of the input size (using the "Binary Search" algorithm).
• Linear ($O(n)$): Time increases in direct proportion to input size (looping through an array).
• Log-Linear ($O(n log n)$): Time increases proportionally to the input size times the logarithm of the input size (using the "Merge Sort" algorithm).
• Quadratic ($O(n^2)$): Time increases proportionally to the square of the input size (Nested loops).
• Cubic ($O(n^3)$): Time increases proportionally to the cube of the input size (Matrix multiplication).
• Exponential ($O(2^n)$): Time doubles with each additional input (Traveling salesman (naive)).

Simplifying Big-O Expressions

• Delete lower order terms: $n^2 + n \rightarrow n^2$.
• Delete constact factors: $100n \rightarrow n$.
• Ensure use the simplest expression possible: $O(n^2 + n) \rightarrow O(n^2)$.
• $O(log_a n) = O(log_b n)$.

Performance of Algorithms

• Linear Search is $O(n)$.
• Binary Search is $O(log n)$.
• Bubble Sort is $O(n^2)$.
• Merge Sort: is $O(n log n)$.

Important Caveats

• Big-O describes the asymptotic behaviors of algorithms.
• Constant factors can matter.
• Big-O does not tell anything about the actual runtme of algorithms.
• Considers "Worst-Case" vs "Average-Case".

Algorithmic Game Theory

What is Game Theory?

• Game theory is the study of mathematical models of strategic interactions among rational agents.
• Cooperative: Focus on groups of players that form coalitions.
• Non-Cooperative: Focus on individual players and their strategies.

Normal-Form Games

• Described via a payoff matrix.
• A tuple $(N, A, u)$, where:
• $N$ is a finite set of $n$ players, indexed by $i$.
• $A = A_1 \times \dots \times A_n$, where $A_i$ is a finite set of actions available to player $i$. Each $a = (a_1, \dots, a_n) \in A$ is an action profile.
• $u = (u_1, \dots, u_n)$, where $u_i : A \mapsto \mathbb{R}$ is a real-valued utility function for player $i$. $u_i(a)$ specifies the payoff to player $i$ when the action profile is $a$.

Prisoner's Dilemma Example

• Suspects arrested, lacking conviction evidence unless one confesses.
• If one confesses and the other doesn't, the confessor is freed, the other jailed for 3 years.
• If both confess, both jailed for 2 years.
• If neither confesses, both jailed for 1 year.

Strategies in Game Theory

• Pure Strategy: An action $a_i \in A_i$.
• Mixed Strategy: Probability distribution over $A_i$.
  • Let $S_i$ denote the set of all possible mixed strategies for player $i$.
  • For $s_i \in S_i$, let $s_i(a_i)$ be the probability of playing action $a_i \in A_i$ under mixed strategy $s_i$.
• Strategy Profile: A tuple $s = (s_1, \dots, s_n)$, where $s_i \in S_i$ is a mixed strategy for player $i$.
  • Let $S = S_1 \times \dots \times S_n$ denote the set of all strategy profiles.

Expected Utility

• The expected utility of player $i$ under strategy profile $s$ is:
• $u_i(s) = \sum_{a \in A} u_i(a) \prod_{j \in N} s_j(a_j)$.

Nash Equilibrium

• A strategy profile $s^* \in S$ is a Nash Equilibrium if, for every player $i \in N$ and every strategy $s_i \in S_i$:
• $u_i(s_i^, s_{-i}^) \ge u_i(s_i, s_{-i}^)$, where $s_{-i}^$ denotes the strategies of all players except $i$.
• No player has an incentive to unilaterally deviate from their strategy in a Nash Equilibrium.
• The only Nash Equilibrium within the Prisoners dilemma is (Defect, Defect).

Existence Theorem

• Every normal-form game with a finite number of players and actions has at least one Nash Equilibrium, possibly in mixed strategies.