Dynamic Programming: Edit Distance

Dynamic Programming - Edit Distance

• Dynamic programming is used to determine the minimum number of edits needed to transform one string into another.
• Edit operations include inserting, deleting, or replacing a character.

Substructure

• E(i, j) represents the edit distance between x[1...i] and y[1...j].
• If x[i] = y[j], then E(i, j) = E(i-1, j-1), indicating no edit is needed.
• If x[i] ≠ y[j], the edit distance is the minimum of the following: inserting y[j], deleting x[i], or replacing x[i] with y[j], each with a cost of 1.

Recurrence Relation

• For base cases, E(i, 0) = i and E(0, j) = j for all i and j.
• The general case involves checking if characters match and choosing the minimum edit distance accordingly.
• If $x[i] = y[j]$, $E(i, j) = E(i-1, j-1)$.
• If $x[i] \neq y[j]$, $E(i, j) = \min{E(i, j-1) + 1, E(i-1, j) + 1, E(i-1, j-1) + 1}$.

Dynamic Programming Approach

• The edit distance table is computed in a bottom-up manner.
• The algorithm iterates through the matrix, filling in values based on the recurrence relation.
• Running time is $O(mn)$, with space complexity of $O(mn)$.

Example: food → money

• The edit distance table shows the minimum edits needed at each step.
• The calculated edit distance between "food" and "money" is 4.

Physics: Rotational Motion

Torque

• Torque ($\tau$) is the turning effect of a force and is a vector quantity.
• $\tau = rF\sin\theta$, where $r$ is the distance from the axis of rotation, $F$ is the force magnitude, and $\theta$ is the angle between the force and lever arm.
• Can alternatively be represented as $\tau = r_{\perp}F = rF_{\perp}$.
• The direction of the torque is given by the right-hand rule, perpendicular to the plane formed by $r$ and $F$.
• The net torque ($\tau_{net}$) is the sum of all torques: $\tau_{net} = \sum \tau = \tau_1 + \tau_2 +...$

Torque and Angular Acceleration

• Angular acceleration is directly proportional to the net torque: $\tau = I\alpha$.
• $I$ is the moment of inertia, and $\alpha$ is the angular acceleration.
• Moment of Inertia ($I$) measures an object's resistance to changes in rotational motion and is $I = \sum mr^2$.
• The parallel-axis theorem: $I = I_{CM} + Md^2$, where $I_{CM}$ is the moment of inertia about the center of mass, $M$ is the total mass, and $d$ is the distance between the two axes.

Rotational Kinetic Energy

• Rotational kinetic energy $K_R = \frac{1}{2}I\omega^2$, where $I$ is the moment of inertia, and $\omega$ is the angular speed.
• Total kinetic energy of a rolling object: $K = \frac{1}{2}Mv^2 + \frac{1}{2}I\omega^2$, where $M$ is the mass and $v$ is the linear speed.

Work and Power in Rotational Motion

• Work done by torque: $W = \int_{\theta_i}^{\theta_f} \tau d\theta$, or $W = \tau\Delta\theta$ if torque is constant.
• Power delivered by torque: $P = \tau\omega$.

Angular Momentum

• Angular momentum of a particle: $L = r \times p = r p \sin\theta$.
• Angular momentum of a rigid object: $L = I\omega$.
• Conservation of angular momentum: $\sum L_i = \sum L_f$ if the net external torque is zero.
• Angular impulse: $\Delta L = \int \tau dt$, or $\Delta L = \tau \Delta t$ if torque is constant.

Rolling Motion

• For rolling without slipping: $v = R\omega$, where $v$ is linear speed, $R$ is the radius, and $\omega$ is angular speed.
• Total kinetic energy: $K = \frac{1}{2}Mv^2 + \frac{1}{2}I\omega^2$.
• When rolling down an incline, acceleration is less than $g\sin\theta$ due to rotational inertia.