Algorithms and Data Structures 2

Module 1: Advanced Tree Structures

1.1 Height-Balanced Trees (AVL & B-Trees)

A tree's efficiency relies on maintaining a minimized height. For a binary tree of $n$ nodes and height $h$:

• Minimum internal nodes: $h$ (max $2^h - 1$ )
• External nodes: $\ge h+1$ (max $2^h$ )
• Height bounds: $\log_2(n+1) - 1 \le h \le \frac{n-1}{2}$

Average access complexity is logarithmic, approximated by:

$$z_N \sim 2 \ln N - c$$

AVL Trees:
Binary search trees where the height of each internal node’s children differs by at most 1. The upper limit is derived from Fibonacci trees, where the minimum number of nodes $N(h)$ for a given height $h$ is defined by:

$$N(h) = 1 + N(h-1) + N(h-2) = \text{Fib}(h+3) - 1$$

$$\text{Fib}(h) = \frac{1}{\sqrt{5}} \left( \left(\frac{1 + \sqrt{5}}{2}\right)^h - \left(\frac{1 - \sqrt{5}}{2}\right)^h \right)$$

Leading to the height bound:

$$h \le 1.44 \log_2 (N+2)$$

B-Trees:
Multi-path trees where every non-leaf node (except the root) has children between $t$ and $2t$ (where $m = 2t$ ). This self-balancing mechanism guarantees access, insertion, and deletion in $O(\log n)$ time.

1.2 Weight-Balanced Search Trees (BB)

Weight-balanced trees tolerate structural deviation measured by the ratio of node weights. The root balance $\rho(B)$ for a tree with a left subtree of size $l$ and total nodes $N$ is:

$$\rho(B) = \frac{l + 1}{N + 1}$$

A tree is weight-balanced $BB(\alpha)$ if for each subtree $B'$:

$$\alpha \le \rho(B') \le 1 - \alpha$$

Rebalancing via rotation is guaranteed if $\alpha \le 1 - \frac{\sqrt{2}}{2}$.

1.3 Splay Trees and Treaps

Splay Trees: Reorganize themselves after every access operation using "splaying" (move-to-root via zick-zick or zick-zack rotations). Cost is amortized $O(\log N)$, but worst-case linear $O(N)$.

Treaps: Cartesian trees combining a Binary Search Tree (BST) for keys $X$ and a Max-Heap for priorities $Y$. If node $v$ contains $(X_0, Y_0)$:

• Left subtree: $X \le X_0$
• Right subtree: $X \ge X_0$
• Both subtrees: $Y \le Y_0$

In a Randomized Treap, random priorities simulate uniform distribution, bounding expected height. Depth $D_k$ for a node $N_k$ is the expected sum of ancestor probabilities:

$$E[V] = \sum_{i=1}^{M} v_i * p_i$$

Module 2: Hashing

2.1 Hash Functions and Compression Maps

An occupancy factor $\alpha = \frac{n}{N}$ denotes the ratio of stored keys to table size.
Common compression maps include:

• Division-Remainder: $h(k) = |k| \pmod N$
• Multiply, Add, and Divide (MAD): Eliminates sequential patterns.

$$h(k) = |ak + b| \pmod N$$

• Multiplicative Method: Utilizes an irrational number $\Psi$ to divide intervals. The optimal constant is the Golden Ratio $\Psi = \frac{\sqrt{5} - 1}{2} \approx 0.618$.

$$h(k) = \lfloor N(k\Psi \pmod 1) \rfloor = \lfloor N(k\Psi - \lfloor k\Psi \rfloor) \rfloor$$

2.2 Collision Handling

Open Hashing (Closed Probing): Computes a probing sequence to resolve collisions:

$$(h(k) - s(j,k)) \pmod N$$

• Linear Probing: $s(j,k) = j$
• Quadratic Probing: $s(j,k) = (-1)^j \cdot \lceil j/2 \rceil^2$
• Double Hashing: Utilizes a secondary hash function:

$$s(j,k) = j \cdot h_2(k)$$

Universal Hashing: Limits collision probability to $\frac{|H|}{N}$. A standard universal set employs prime $p \ge |K|$:

$$h(x) = ((ix + j) \pmod p) \pmod N$$

Module 3: Graph Algorithms and Flows

3.1 Transitive Closure & Traversal

• DFS & BFS: Vertex traversal mechanisms yielding $O(1)$ lookup for adjacency. BFS resolves the shortest path in unweighted graphs.
• Floyd-Warshall: Derives the transitive closure $G_k$ considering paths through intermediate vertices $\{v_1, \dots, v_k\}$. Operates in $O(n^3)$ time.

3.2 Network Flows (Ford-Fulkerson)

Networks possess a source $s$ and sink $t$. Flows must observe capacity limits ( $0 \le f(u,v) \le c(u,v)$ ) and node conservation laws.

The Maximum Flow Minimum Cut Theorem declares that maximum flow equals the capacity of the minimum cut $X = (V_s, V_t)$.

A Residual Network $N_f$ defines available capacity:

• Forward edge: $c_f(u,v) = c(u,v) - f(u,v)$
• Backward edge: $c_f(v,u) = f(u,v)$

Using BFS to locate augmenting paths (Edmonds-Karp) binds runtime to:

$$O((n+m) \cdot n \cdot m) = O(n^5)$$

Module 4: Community Analysis

4.1 Clustering and Density

Clustering Coefficient: Determines how tightly a node $i$ 's neighbors are connected.

$$C_i = \frac{k_i}{d_i \times (d_i - 1) / 2}$$

(Where $k_i$ = existing connections between neighbors, and $d_i$ = degree)

4.2 Centrality Metrics

• Closeness Centrality: Reciprocal of average geodesic distance $g(v_i, v_j)$.

$$C_C(v_i) = \frac{n - 1}{\sum_{j \neq i} g(v_i, v_j)}$$

• Betweenness Centrality: Ratio of shortest paths $\sigma_{st}$ passing through $v_i$.

$$C_B(v_i) = \sum_{v_s \neq v_i \neq v_t \in V, s < t} \frac{\sigma_{st}(v_i)}{\sigma_{st}}$$

• Eigenvector Centrality: Proportional to the centrality of adjacent nodes.

$$A\mathbf{x} = \lambda \mathbf{x}$$

Module 5: Monte Carlo Tree Search (MCTS)

MCTS guides decision processes in game trees (e.g., AlphaGo) through Selection, Expansion, Simulation, and Backpropagation.

Selection employs the Upper Confidence Bound applied to Trees (UCT) to balance exploitation and exploration:

$$UCT(i, a) = \frac{W(i, a)}{N(i, a)} + c \sqrt{\frac{\ln N(i)}{N(i, a)}}$$

Where $W(i,a)$ is the total reward, $N(i,a)$ is action visits, $N(i)$ is parent visits, and $c$ is the exploration constant ( $\approx \sqrt{2}$ ).

Module 6: PRAM Algorithms

Parallel Prefix Summation: Aggregates array data iteratively over $\lceil \log n \rceil$ steps using parallel spawn instructions:

$$A[2i] \leftarrow A[2i] + A[2i + 2^j]$$

This mechanism allows rapid evaluation in shared-memory multiprocessor systems for array packing.