Review & Cheat Sheet
[!NOTE] This module explores the core principles of Discrete Math and Information Theory, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.
1. Interactive Flashcards
Test your knowledge. Click a card to flip it.
Click/Tap to Flip · Scroll to see more
2. Cheat Sheet
Complexity Analysis
| Algorithm / Structure | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Adjacency Matrix | O(1) lookup | O(V2) | Good for dense graphs. |
| Adjacency List | O(Degree) lookup | O(V+E) | Standard for most apps. |
| BFS / DFS | O(V+E) | O(V) | Graph traversal. |
| Dijkstra | O(E log V) | O(V) | Weighted shortest path (using Min-Heap). |
| DFT (Naive) | O(N2) | O(N) | Slow Fourier Transform. |
| FFT | O(N log N) | O(N) | Fast Fourier Transform. |
| Self-Attention | O(N2) | O(N2) | Quadratic with sequence length. |
Key Formulas
- Surprisal: I(x) = − log2 P(x)
- Entropy: H(P) = − Σ P(x) log2 P(x)
- Euler’s Formula: eix = cos(x) + isin(x)
- Attention: softmax( QKT / √dk ) V
- Reparameterization: z = μ + σ ⊙ ε
3. Quick Revision
- Graph Search: Always ask if the graph is Weighted or Unweighted.
- Unweighted → BFS.
- Weighted → Dijkstra.
- Cycle Detection:
- Directed → DFS (check recursion stack) or Kahn’s Algo.
- Undirected → DFS (check visited parent) or Union-Find.
- FFT: Mention it for any signal processing, audio, or multiplication of large polynomials.
- Transformers: Remember the N2 bottleneck. This is why ChatGPT has a context limit (e.g., 32k tokens).