The High-Yield Problem Vault & Mathematical Derivations

Step 1 (S1 is TRUE): Ambiguity of CFGs is proven undecidable via reduction from the Post Correspondence Problem (PCP). There exists no algorithm that can test arbitrary CFG ambiguity.

Step 2 (S2 is FALSE): By Rice's Theorem, any non-trivial semantic property of the language recognized by a Turing machine is undecidable. \"Language contains at least 5 strings\" is a semantic property (satisfied by some TMs, not satisfied by \(\emptyset\)). Hence it is undecidable.

Step 3 (S3 is TRUE): For two DFAs \(D_1, D_2\), \(L(D_1) = L(D_2) \iff (L(D_1) \cap \overline{L(D_2)}) \cup (\overline{L(D_1)} \cap L(D_2)) = \emptyset\). Since regular languages are closed under complement, intersection, and union, and DFA emptiness is decidable, DFA equivalence is DECIDABLE.

Step 4 (S4 is FALSE): Emptiness for Context-Sensitive Languages (CSLs / Linear Bounded Automata) is UNDECIDABLE. Membership for CSL is decidable (in PSPACE), but emptiness is undecidable.

Step 1: Virtual Address Breakdown:

• Page Size \(= 4\text{ KB} = 2^{12}\text{ bytes} \implies \text{Offset} = 12\text{ bits}\).
• Virtual Page Number \(= 32 - 12 = 20\text{ bits}\).
• Page capacity \(= 4096 / 4 = 1024 = 2^{10}\text{ entries} \implies \text{Outer} = 10\text{ bits}, \text{Inner} = 10\text{ bits}\). Two levels confirmed.

Step 2: Latency on TLB Hit (\(h = 0.90\)):

T_{hit} = t_{TLB} + m = 10 + 80 = 90\text{ ns}

Step 3: Latency on TLB Miss (\(1 - h = 0.10\)):

T_{miss} = t_{TLB} + m (\text{Outer PT}) + m (\text{Inner PT}) + m (\text{Actual Operand}) = 10 + 3 \times 80 = 250\text{ ns}

Step 4: Effective Memory Access Time (EMAT):

\text{EMAT} = 0.90 \times 90 + 0.10 \times 250 = 81 + 25 = 106\text{ ns}

Step 1: Propagation and Transmission Delays:

• Propagation Time \(T_p = \frac{100 \times 10^3\text{ m}}{2 \times 10^8\text{ m/s}} = 0.5\text{ ms} = 500\text{ }\mu\text{s}\).
• Transmission Time \(T_t = \frac{1000 \times 8\text{ bits}}{10^9\text{ bps}} = 8\text{ }\mu\text{s}\).
• Parameter \(a = \frac{T_p}{T_t} = \frac{500}{8} = 62.5\).

Step 2: Optimal Sender Window Size:

W_S \ge 1 + 2a = 1 + 2 \times 62.5 = 126\text{ packets}

Step 3: Selective Repeat Sequence Number Constraint:

In Selective Repeat, \(W_S = W_R\). To prevent overlap between current and old window packets:

W_S + W_R \le 2^k \implies 2 \times 126 \le 2^k \implies 252 \le 2^k

Since \(2^7 = 128 < 252\) and \(2^8 = 256 \ge 252\), the minimum sequence bits required is \(k = 8\text{ bits}\).

Step 1: Identify Conflicting Operations: Two operations conflict if they belong to different transactions, access the same data item, and at least one is a write.

• On variable \(X\): \(r_3(X)\) precedes \(w_1(X) \implies T_3 \to T_1\).
• On variable \(Z\): \(r_1(Z)\) precedes \(w_2(Z) \implies T_1 \to T_2\).
• On variable \(Y\): \(w_3(Y)\) precedes \(r_2(Y)\) and \(w_2(Y) \implies T_3 \to T_2\).

Step 2: Precedence Graph Construction:

Edges: (T_3 \to T_1), (T_1 \to T_2), (T_3 \to T_2)

The graph is a DAG with NO cycles. Therefore, \(S\) is Conflict Serializable.

Step 3: Topological Sorting: In-degree of \(T_3\) is 0. Removing \(T_3\) leaves in-degree of \(T_1\) as 0. Unique topological order is \(T_3 \to T_1 \to T_2\).

Step 1: Normal Insertion Costs: Each of the 64 items requires 1 unit of insertion work: \(\text{Cost}_{\text{insert}} = 64\).

Step 2: Table Expansion Copy Costs:

• Insertion 2: capacity doubles from 1 to 2 \(\implies 1\) item copied.
• Insertion 3: capacity doubles from 2 to 4 \(\implies 2\) items copied.
• Insertion 5: capacity doubles from 4 to 8 \(\implies 4\) items copied.
• Insertion 9: capacity doubles from 8 to 16 \(\implies 8\) items copied.
• Insertion 17: capacity doubles from 16 to 32 \(\implies 16\) items copied.
• Insertion 33: capacity doubles from 32 to 64 \(\implies 32\) items copied.

\text{Copy Cost} = 1 + 2 + 4 + 8 + 16 + 32 = 63

Step 3: Total Cumulative Work:

\text{Total} = \text{Insertion Cost} + \text{Copy Cost} = 64 + 63 = 127

Amortized cost per operation is \(127 / 64 = 1.984 < 2 = O(1)\).

Step 1: Euler's Formula for Connected Planar Graphs:

V - E + F = 2 \implies F = 2 - V + E

Step 2: Edge-Face Inequality:

Each edge is shared by at most 2 faces. If every face has degree \(\ge 4\):

2E = \sum \text{deg}(F_i) \ge 4F \implies F \le \frac{E}{2}

Step 3: Substitute \(F\) and Solve:

2 - V + E \le \frac{E}{2} \implies 2 - 20 + E \le \frac{E}{2} \implies \frac{E}{2} \le 18 \implies E \le 36

Maximum possible edges is \(E = 36\).