Laplace Transform

The Laplace Transform

• Converts a function f(t) to F(s) using an integral transform.

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

Region of Convergence (ROC)

• The Laplace transform exists when the integral converges, typically when $Re(s) > a$ for some real number a.

Properties of Laplace Transforms

• Linearity: $\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)$, where $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

• $\mathcal{L} {\frac{d}{dt}f(t)} = sF(s) - f(0)$.

• $\mathcal{L} {\frac{d^2}{dt^2}f(t)} = s^2F(s) - sf(0) - f'(0)$.

• $\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)$, where $(f * g)(t) = \int_{0}^{t} f(\tau)g(t - \tau) d\tau$.

Initial and Final Value Theorems

• 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 Summary

• Unit Impulse: $\delta(t)$ transforms to $1$, ROC: All s.

• Unit Step: $u(t)$ transforms to $\frac{1}{s}$, ROC: $Re(s) > 0$.

• Ramp: $t$ transforms to $\frac{1}{s^2}$, ROC: $Re(s) > 0$.

• Exponential: $e^{at}$ transforms to $\frac{1}{s - a}$, ROC: $Re(s) > Re(a)$.

• Sine: $\sin(\omega t)$ transforms to $\frac{\omega}{s^2 + \omega^2}$, ROC: $Re(s) > 0$.

-Cosine: $\cos(\omega t)$ transforms to $\frac{s}{s^2 + \omega^2}$, ROC: $Re(s) > 0$.

• Hyperbolic Sine: $\sinh(at)$ transforms to $\frac{a}{s^2 - a^2}$, ROC: $Re(s) > |a|$.

• Hyperbolic Cosine: $\cosh(at)$ transforms to $\frac{s}{s^2 - a^2}$, ROC: $Re(s) > |a|$.

• Damped Sine: $e^{-at}\sin(\omega t)$ transforms to $\frac{\omega}{(s + a)^2 + \omega^2}$, ROC: $Re(s) > -a$.

• Damped Cosine: $e^{-at}\cos(\omega t)$ transforms to $\frac{s + a}{(s + a)^2 + \omega^2}$, ROC: $Re(s) > -a$.

• t to the power of n: $t^n$ transforms to $\frac{n!}{s^{n+1}}$, ROC: $Re(s) > 0$.

Vectors in Physics: Sum and Product

Vector Summation

• Using the graphical method, vectors A and B are placed sequentially, maintaining their magnitude, direction, and sense.
• The resultant vector R extends from the origin of the first vector to the end of the last.

Analytical Vector Summation

• Rectangular Components: $A_x = A \cos \theta$ and $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}$.

Vector Product

• Scalar Product (Dot Product): $\vec{A} \cdot \vec{B} = AB \cos \theta = A_x B_x + A_y B_y + A_z B_z$; result is a scalar.

• Vector Product (Cross Product):

  • $\vec{A} \times \vec{B} = AB \sin \theta \hat{n}$.
  • Defined by a determinant using unit vectors $\hat{i}, \hat{j}, \hat{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}$
  • Result is a vector perpendicular to the plane formed by A and B, direction given by the right-hand rule.

Energy Bands & Charge Carriers in Semiconductors

Energy Bands

• E vs. k Diagram: Represents solutions to Schrödinger's equation for electrons in a crystal lattice.

Metals

• The Fermi level is within an allowed band, resulting in a partially filled band.

Semiconductors

• The Fermi level is in a band gap separating the filled valence band from the empty conduction band.

Insulators

• The Fermi level is in a larger band gap, differentiating them from semiconductors.

Intrinsic Semiconductors

• Perfect crystals without impurities or defects, like Silicon (Si) and Germanium (Ge).
• At 0K, all valence band states are filled, and conduction band states are empty.
• At T > 0K, thermal excitation creates electron-hole pairs with $n = p = n_i$, where $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}$, where $N_c$ and $N_v$ are the effective densities of states in the conduction and valence bands, respectively.

Extrinsic Semiconductors

• Doping intentionally adds impurities to control properties.

n-type Semiconductors

• Doped with donor impurities (e.g., Phosphorus in Silicon) contributing electrons with $n > n_i$, shifting $E_F$ closer to $E_c$.

p-type Semiconductors

• Doped with acceptor impurities (e.g., Boron in Silicon) creating holes with $p > n_i$, shifting $E_F$ closer to $E_v$.

Compensation

• Both donors and acceptors are present, the conductivity type depends on the higher concentration impurity.

Carrier Transport Phenomena

• Drift: Motion due to electric field E, with current density $J_{drift} = \sigma E = q(n\mu_n + p\mu_p)E$, where $\sigma$ is conductivity, and $\mu_n$ and $\mu_p$ are electron and hole mobilities.
• Diffusion: Movement from high to low concentration areas, with current density $J_{diffusion} = qD_n \frac{dn}{dx} - qD_p \frac{dp}{dx}$, where $D_n$ and $D_p$ are diffusion coefficients.
• Einstein Relation: $\frac{D_n}{\mu_n} = \frac{D_p}{\mu_p} = \frac{kT}{q}$ relates diffusion coefficient with mobility.

Algorithmic Complexity

• Quantifies resource usage, compares algorithms, and predicts scaling with increasing input size (n).

Importance

• Enables informed algorithm selection, code optimization, and understanding computational limits.

Process

• Selection of a computation model followed by defining the input size $n$. Counting operations as f(n), the complexity is expressed using Big-O notation.

Models of Computation

• Turing Machine: Manipulates symbols on tape.
• Random Access Machine (RAM): Allows random memory access.
• Word RAM: Memory divided into fixed-size words.
• Real RAM: Allows real number storage.

Big-O Notation Explained

• Definition: $f(n) = O(g(n))$ if there exist $c$ and $n_0$ such that $f(n) \le cg(n)$ for all $n \ge n_0$.

• Interpretation: $f(n)$ grows no faster than $g(n)$ as $n$ approaches infinity.

• Examples:

  • $n^2 + n = O(n^2)$.
  • $100n = O(n)$.
  • $\log(n) = O(n)$.

List of Common Complexities

• Constant: O(1) e.g., array access.
• Logarithmic: O(log n) e.g., binary search.
• Linear: O(n) e.g., array loop.
• Log-Linear: O(n log n) e.g., merge sort.
• Quadratic: O(n^2) e.g., nested loops.
• Cubic: O(n^3) e.g., matrix multiplication.
• Exponential: O(2^n) e.g., naive traveling salesman solution.

Simplifying Big-O Expressions

• Drop lower order terms: $n^2 + n \rightarrow n^2$.
• Ignore constant factors: $100n \rightarrow n$.
• Use the simplest form. $O(n^2 + n) \rightarrow O(n^2)$.
• Logarithms to different bases are equivalent: $O(log_a n) = O(log_b n)$.

Examples

• Searching:
  • Linear search: $O(n)$.
  • Binary search: $O(log n)$.
• Sorting:
  • Bubble sort: $O(n^2)$.
  • Merge sort: $O(n log n)$.

Important Caveats

• Asymptotic behavior is described by Big-O notation.
• Constant factors can matter.
• Actual running time isn't indicated by Big-O.
• Consider worst-case vs. average-case complexity.

Algorithmic Game Theory Concepts and Definitions

Game Theory

• Study of strategic interactions among rational agents with applications in various fields.

Scope

• Includes cooperative (coalition-focused) and non-cooperative (individual strategy-focused) games.

Normal-Form Games

• Defines games via payoff matrix. Defined by tuple $(N, A, u)$:
  • $N$: finite set of n players.
  • $A$: action profiles ($A = A_1 \times \dots \times A_n$, where $A_i$ is actions for player i).
  • $u$: utility function for player i that maps action profiles to real-valued payoffs $u_i(a)$.

Prisoner’s Dilemma

• Two suspects; police lack evidence unless one confesses.
• Suspect confesses alone: is freed. The other gets 3 years.
• Both confess: each gets 2 years. Neither suspect confesses: each gets 1 year.

Game Representation of Prisoner’s Dilemma

• $N = {1, 2}$.
• $A_i = {\text{Cooperate}, \text{Defect}}$ for $i \in N$.
  • Utility is defined by the table:

Strategies Explained

• Pure Strategy: An action $a_i \in A_i$ for player i.
• Mixed Strategy: A probability distribution over $A_i$.
  • $S_i$: the set of all possible mixed strategies for player i.
  • $s_i(a_i)$: The probability of playing action $a_i \in A_i$ under mixed strategy $s_i$.

Strategy Profile Defined

• Strategy Profile: a tuple $s = (s_1, \dots, s_n)$, where $s_i \in S_i$ is mixed for player i.
• $S = S_1 \times \dots \times S_n$: The set of all strategy profiles.

Expected Utility

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

Nash Equilibrium Defined

• $s^* \in S$: strategy profile is Nash Equilibrium if, for every player i $u_i(s_i^, s_{-i}^) \ge u_i(s_i, s_{-i}^*)$
• $s_{-i}^*$: strategies of all players except i. No player can unilaterally deviate for motivation.

Prisoner’s Dilemma (Example)

• (Defect, Defect) is the only Nash Equilibrium.

Existence Of Nash Equilibrium

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