High-density quick references designed for the final 30 days of preparation. Decidability bounds, asymptotic runtimes, and hardware formula tables.
D = Decidable (An algorithm exists that halts on all inputs with Yes/No) • U = Undecidable (No algorithm exists).
| Problem Name | Regular | DCFL | CFL | CSL | Recursive (REC) | RE |
|---|---|---|---|---|---|---|
| Membership (\(w \in L\)) | D | D | D (CYK) | D | D | U |
| Emptiness (\(L = \emptyset\)) | D | D | D | U | U | U |
| Finiteness (\(|L| < \infty\)) | D | D | D | U | U | U |
| Equivalence (\(L_1 = L_2\)) | D | D (Sénizergues) | U | U | U | U |
| Subset (\(L_1 \subseteq L_2\)) | D | U | U | U | U | U |
| Totality (\(L = \Sigma^*\)) | D | D | U | U | U | U |
| Disjointness (\(L_1 \cap L_2 = \emptyset\)) | D | U | U | U | U | U |
| Ambiguity of Grammar | D (NFA\to DFA) | D (Unambiguous) | U | U | U | U |
| Regularity (\(\text{Is } L \text{ Regular?}\)) | D | D (Stearns) | U | U | U | U |
| Operation | Regular | DCFL | CFL | CSL | Recursive (REC) | RE |
|---|---|---|---|---|---|---|
| Union (\(L_1 \cup L_2\)) | Yes | No | Yes | Yes | Yes | Yes |
| Intersection (\(L_1 \cap L_2\)) | Yes | No | No | Yes | Yes | Yes |
| Complementation (\(\overline{L}\)) | Yes | Yes | No | Yes (Immerman) | Yes | No |
| Concatenation (\(L_1 \cdot L_2\)) | Yes | No | Yes | Yes | Yes | Yes |
| Kleene Star (\(L^*\)) | Yes | No | Yes | Yes | Yes | Yes |
| Intersection with Regular (\(L \cap R\)) | Yes | Yes | Yes | Yes | Yes | Yes |
| Homomorphism | Yes | No | Yes | No (\(\epsilon\)-free: Yes) | No | Yes |
| Inverse Homomorphism | Yes | Yes | Yes | Yes | Yes | Yes |
| Reversal (\(L^R\)) | Yes | No | Yes | Yes | Yes | Yes |
| Algorithm | Best Time | Average Time | Worst Time | Worst Space | Stable? | In-Place? |
|---|---|---|---|---|---|---|
| MergeSort | \(\Omega(n \log n)\) | \(\Theta(n \log n)\) | \(O(n \log n)\) | \(O(n)\) | Yes | No |
| QuickSort (Randomized) | \(\Omega(n \log n)\) | \(\Theta(n \log n)\) | \(O(n^2)\) | \(O(\log n)\) (Call stack) | No | Yes |
| HeapSort | \(\Omega(n \log n)\) | \(\Theta(n \log n)\) | \(O(n \log n)\) | \(O(1)\) | No | Yes |
| InsertionSort | \(\Omega(n)\) | \(\Theta(n^2)\) | \(O(n^2)\) | \(O(1)\) | Yes | Yes |
| CountingSort | \(\Omega(n + k)\) | \(\Theta(n + k)\) | \(O(n + k)\) | \(O(k)\) | Yes | No |
| Dijkstra (Binary Heap) | \(\Theta((V + E) \log V)\) | \(O(V)\) | Requires all edge weights \(\ge 0\) | |||
| Bellman-Ford | \(O(V \cdot E)\) | \(O(V)\) | Detects negative weight cycles | |||
| Floyd-Warshall | \(\Theta(V^3)\) | \(\Theta(V^2)\) | All-pairs shortest paths via DP | |||
| Kruskal (Disjoint Set) | \(O(E \log E) = O(E \log V)\) | \(O(V)\) | Greedy Minimum Spanning Tree | |||
S = \frac{n \cdot k}{k + n - 1 + \text{stalls}} \implies \lim_{n \to \infty} S = \frac{k}{1 + \text{stalls\_per\_inst}}
T_{avg} = h_1 t_1 + (1 - h_1)[h_2 t_2 + (1 - h_2) t_{mem}]
\text{CPU Block Fraction} = \frac{\text{Memory Cycle Time}}{\text{Device Word Production Interval}}
\eta = \frac{W_S}{1 + 2a} \quad \text{where } a = \frac{T_p}{T_t}; \quad W_S + W_R \le 2^k
L_{min} \ge 2 \cdot Bandwidth \cdot \frac{\text{Distance}}{\text{Propagation Velocity}}
\text{Size} = \frac{\text{Physical RAM Size}}{\text{Page Size}} \times (\text{PID Bits} + \text{VPN Bits} + \text{Protection Bits})