History chap 6.4

Ford-Fulkerson Algorithm

• A greedy algorithm used to compute the maximum flow in a flow network.
• Input: Flow network $G=(V, E)$ with capacities $c(u, v) \geq 0$ for all $(u, v) \in E$.
• Output: Maximum flow $f$ from $s$ to $t$.
• Initial flow $f(u, v) = 0$ for all $(u, v) \in E$.
• The algorithm iterates as long as there exists an augmenting path $p$ from $s$ to $t$ in the residual network $G_f$.
• Rest capacity $c_f(p) = \min{c_f(u, v) | (u, v) \in p}$ is computed.
• The flow along path $p$ is augmented by $c_f(p)$.
  • For each edge $(u, v) \in p$:
    • $f(u, v) = f(u, v) + c_f(p)$
    • $f(v, u) = f(v, u) - c_f(p)$
• Finally, the maximum flow f is returned.

Residual Network

• Denoted as $G_f$, with the same nodes as $G$.
• Edges represent residual capacity.
• The residual capacity of an edge $(u, v)$ is defined as $c_f(u, v) = c(u, v) - f(u, v)$, if $f(u, v) > 0$, and $c_f(v, u) = f(v, u)$, if $f(u, v) < 0$.

Augmenting Path

• A path from $s$ to $t$ in the residual network $G_f$.
• It possesses positive residual capacity.

Example

• Flow network with nodes $s, a, b, t$ and edges $(s, a), (s, b), (a, b), (a, t), (b, t)$.
• Capacities are $c(s, a) = 10, c(s, b) = 5, c(a, b) = 4, c(a, t) = 8, c(b, t) = 10$.
• The maximum flow found is 13.

Analysis

• Runtime depends on the choice of augmenting paths.
• Exponential time can be required if capacities are irrational (worst case).
• With integer capacities, the runtime is $O(E \cdot f^)$, where $f^$ is the value of the maximum flow.
• The Edmonds-Karp algorithm uses breadth-first search to find augmenting paths, with a runtime of $O(V \cdot E^2)$.

Matrix Basics

Definition

• An $m \times n$ matrix is a rectangular array of $m \cdot n$ real or complex numbers
• Denoted as $A = (a_{ij})$, $A_{m \times n}$.
• $a_{ij}$ is an element of the matrix at the $i$th row and $j$th column
  • $i$ is the row index, $j$ is the column index
  • $m$ is the number of rows, $n$ is the number of columns
• Type of a matrix is $m \times n$

Examples

• $A = \begin{bmatrix} 1 & 2 \ 3 & 4 \end{bmatrix}_{2 \times 2}$
• $B = \begin{bmatrix} 1 & 2 & 3 \end{bmatrix}_{1 \times 3}$
• $C = \begin{bmatrix} 1 \ 2 \ 3 \end{bmatrix}_{3 \times 1}$

Terminology

• A square matrix is a matrix where $m = n$
• The elements $a_{11}, a_{22}, \dots, a_{nn}$ form the main diagonal if $m = n$
• An upper triangular matrix is a square matrix where $a_{ij} = 0$ when $i > j$
• A lower triangular matrix is a square matrix where $a_{ij} = 0$ when $i < j$
• A diagonal matrix is a square matrix where $a_{ij} = 0$ when $i \neq j$, denoted as $A = diag(a_{11}, a_{22}, \dots, a_{nn})$
• An identity matrix is $I = diag(1, 1, \dots, 1)$
• A zero matrix is $A = (a_{ij})$ where $a_{ij} = 0$ for all $i, j$
• A row vector is a $1 \times n$ matrix
• A column vector is an $m \times 1$ matrix

Matrix Operations

• For $A = (a_{ij})$ and $B = (b_{ij})$ of the same type $m \times n$, and scalar $c$:
  • Matrix addition: $A + B = (a_{ij} + b_{ij})$
  • Scalar multiplication: $cA = (ca_{ij})$
• For matrix $A_{m \times n}$ and $B_{n \times p}$, the product $AB = C_{m \times p}$ is defined as:
  • Each element $c_{ij} = \sum_{k=1}^{n} a_{ik}b_{kj}$
• Note*: Matrix multiplication is not commutative, meaning $AB \neq BA$ in general.

Examples

• $\begin{bmatrix} 1 & 2 \ 3 & 4 \end{bmatrix} + \begin{bmatrix} 5 & 6 \ 7 & 8 \end{bmatrix} = \begin{bmatrix} 6 & 8 \ 10 & 12 \end{bmatrix}$
• $2 \begin{bmatrix} 1 & 2 \ 3 & 4 \end{bmatrix} = \begin{bmatrix} 2 & 4 \ 6 & 8 \end{bmatrix}$
• $\begin{bmatrix} 1 & 2 \ 3 & 4 \end{bmatrix} \begin{bmatrix} 5 & 6 \ 7 & 8 \end{bmatrix} = \begin{bmatrix} 19 & 22 \ 43 & 50 \end{bmatrix}$

Regular Expressions (Regex)

Definition

• A regular expression (Regex) is a sequence of characters that define a search pattern.

Applications

• Text searching.
• Text replacement.
• Input format validation.

Components

Character Classes

• \d: Digit (0-9).
• \w: "Word character" (A-Z, a-z, 0-9, _).
• \s: Whitespace (space, tab, newline).
• .: Any character (except newline).

Quantifiers

• *: Zero or more occurrences.
• +: One or more occurrences.
• ?: Zero or one occurrence.
• {n}: Exactly n occurrences.
• {n,}: n or more occurrences.
• {n,m}: Between n and m occurrences.

Anchors

• ^: Beginning of the line.
• $: End of the line.
• \b: Word boundary.

Grouping and Alternation

• (): Grouping.
• |: Alternation ("or").

Examples

• \d{3}-\d{2}-\d{4}: Pattern for a date in the format "XXX-XX-XXXX".
• [a-zA-Z]+: One or more letters (uppercase or lowercase).
• ^Hello\sWorld$: A line that contains exactly "Hello World".

Using in Python

Module re

• The re module provides functions for working with regular expressions.

Important Functions

• re.search(pattern, string): Searches for the first occurrence of the pattern in the string.
  • Returns a match object if found, otherwise None.
• re.match(pattern, string): Checks if the pattern matches the beginning of the string.
• re.findall(pattern, string): Finds all non-overlapping occurrences of the pattern.
  • Returns a list of strings.
• re.sub(pattern, replacement, string): Replaces all occurrences by replacement.
• re.compile(pattern): Compiles a regular expression into a regex object.
  • More efficient when using the same pattern repeatedly.

Example

import re

text = "Meine Telefonnummer ist 012-3456-7890."
pattern = r"\d{3}-\d{4}-\d{4}" #Raw string
match = re.search(pattern, text)

if match:
    print("Telefonnummer gefunden:", match.group())

Tips

• Use raw strings (r"...") to avoid escaping backslashes.
• Use online tools for testing regular expressions.
• Keep regular expressions simple and clear.

Chemical Kinetics

Reaction Rate

• For the reaction $aA + bB \rightarrow cC + dD$, the rate is:
  • $Rate = -\frac{1}{a}\frac{d[A]}{dt} = -\frac{1}{b}\frac{d[B]}{dt} = \frac{1}{c}\frac{d[C]}{dt} = \frac{1}{d}\frac{d[D]}{dt}$
• $[A]$ = concentration of reactant A
• $\frac{d[A]}{dt}$ = rate of change of concentration of A with time

Rate Law

• $Rate = k[A]^x[B]^y$
  • $k$ = rate constant
  • $x$ = order of reaction with respect to A
  • $y$ = order of reaction with respect to B
  • $x + y$ = overall order of reaction
• Values of $x$ and $y$ are determined experimentally.

Zero Order Reaction

• $Rate = k[A]^0 = k$
  • Reaction rate is independent of reactant concentration.
  • Plot of reactant concentration vs time is linear with slope $-k$.
  • Half-life: $t_{1/2} = \frac{[A]_0}{2k}$

First Order Reaction

• $Rate = k[A]^1 = k[A]$
  • Reaction rate is directly proportional to reactant concentration.
  • Plot of $\ln[A]$ vs time is linear with slope $-k$.
  • Half-life: $t_{1/2} = \frac{0.693}{k}$

Second Order Reaction

• $Rate = k[A]^2$ or $Rate = k[A][B]$
  • Reaction rate is proportional to square of reactant concentration.
  • Plot of $\frac{1}{[A]}$ vs time is linear with slope $k$.
  • Half-life: $t_{1/2} = \frac{1}{k[A]_0}$

Collision Theory

• For a reaction, reactant molecules must
  • Collide.
  • Have sufficient activation energy($E_a$).
  • Have correct orientation.

Arrhenius Equation

• $k = Ae^{-E_a/RT}$
  • $k$ = rate constant
  • $A$ = frequency factor
  • $E_a$ = activation energy
  • $R$ = gas constant (8.314 J/mol·K)
  • $T$ = temperature (Kelvin)
• The frequency factor $A$ represents collision frequency with proper orientation.

Catalysts

• Catalysts increase reaction rate by lowering the activation energy ($E_a$).
  • Homogeneous Catalysts: Same phase as reactants.
  • Heterogeneous Catalysts: Different phase than reactants.