(a) Output: w rk e

• s holds n(0) e(1) t(2) w(3) o(4) r(5) k(6). p = s + 3 points at index 3, so *p = 'w'.
• p + 2 points at index 5. Printing it with %s prints from there to the end: "rk".
• s[1] = 'e'.

(b) Output: 5 6 6

• A 2×3 array sits in memory row by row: 1 2 3 4 5 6. q points at the first element, so *(q + 4) is the 5th element = a[1][1] = 5.
• a[1][1] + *q = 5 + 1 = 6.
• a + 1 points to row 1, *(a + 1) is that row (an int* to 4), and *(*(a + 1) + 2) = a[1][2] = 6.

Key rules: %s prints until the '\0'; a 2D array is one flat block in row-major order; a[i][j] = *(*(a + i) + j).

(a) Plug every combination into the equations (A⁺ = D_A, B⁺ = D_B):

(b) State diagram (states AB, arrows labelled x / y):

• On x = 1: 00 → 01, 01 → 11, 11 → 10, 10 → 10 (stays).
• On x = 0: every state goes to 00. The output y = 1 during that transition from any nonzero state (01, 10, 11), and y = 0 from 00.

(c) From 00, while x stays 1 the circuit walks 00 → 01 → 11 → 10 and then parks in 10, with y = 0 the whole time. The moment x returns to 0, the state is nonzero, so y = 1 for that one clock and the circuit resets to 00. So the circuit remembers "x was 1 recently" and gives a single 1-pulse when x drops back to 0.

Let D = defective. Given: P(A) = 0.5, P(B) = 0.3, P(C) = 0.2 and P(D|A) = 0.02, P(D|B) = 0.03, P(D|C) = 0.05.

Total probability of a defect:

Posteriors by Bayes:

• \( P(A\mid D) = \dfrac{0.010}{0.029} = \dfrac{10}{29} \approx 0.345 \)
• \( P(B\mid D) = \dfrac{0.009}{0.029} = \dfrac{9}{29} \approx 0.310 \)
• \( P(C\mid D) = \dfrac{0.010}{0.029} = \dfrac{10}{29} \approx 0.345 \)

Check: the three posteriors add to \( \frac{29}{29} = 1 \) ✓.

Most likely source: A and C are exactly tied (10/29 each), slightly ahead of B. Note the surprise: C has the worst defect rate (5%), but its small share (20%) pulls it down to a tie with A — the prior matters as much as the likelihood.

(a) Always place the biggest subnet first.

• LAN-A: needs 110 + 2 (network + broadcast) = 112 addresses. \( 2^6 = 64 \) is too small, \( 2^7 = 128 \) fits → 7 host bits → /25 (126 usable ≥ 110).
• LAN-B: needs 40 + 2 = 42 addresses. \( 2^5 = 32 \) too small, \( 2^6 = 64 \) fits → 6 host bits → /26 (62 usable ≥ 40).

(b)

(c) The block 192.168.10.192/26 (64 addresses, 62 usable) is still completely free. With fixed-length subnetting we would have to cut the /24 into two /25s (the size the biggest LAN forces), LAN-B would waste a whole /25 for only 40 hosts, and nothing would be left over. VLSM gives each LAN a right-sized block, so a quarter of the address space stays available.

Output:

Base::show
Derived::show
Derived::show
Base::tag

• Line 1: new Derived() first runs the Base constructor. Inside a base constructor the object is still only a Base — the Derived part does not exist yet — so the virtual call show() dispatches to Base::show(). This is the classic trap: virtual dispatch is "turned down" to the current construction level inside constructors.
• Line 2: then the Derived constructor body runs; now the object is a Derived, so its show() call prints "Derived::show".
• Line 3: p->show() is a normal virtual call on a fully built object → dynamic binding → Derived::show().
• Line 4: tag() is not virtual, so the compiler binds it statically by the pointer type Base* → Base::tag(), even though the object is a Derived.

delete p is safe and prints nothing: ~Base() is virtual, so the Derived part is destroyed correctly.

(a) Guess \( a_n = r^n \). The recurrence gives the characteristic equation:

Two distinct roots, so \( a_n = \alpha 2^n + \beta 3^n \). Use the initial values:

• \( n = 0:\ \alpha + \beta = 2 \)
• \( n = 1:\ 2\alpha + 3\beta = 5 \)

Subtract twice the first from the second: \( \beta = 5 - 4 = 1 \), so \( \alpha = 1 \).

(b) Closed form: \( a_2 = 4 + 9 = 13 \). Recurrence: \( a_2 = 5(5) - 6(2) = 25 - 12 = 13 \) ✓.

(c) Closed form: \( a_4 = 2^4 + 3^4 = 16 + 81 = \mathbf{97} \). Recurrence: \( a_3 = 5(13) - 6(5) = 65 - 30 = 35 \), then \( a_4 = 5(35) - 6(13) = 175 - 78 = 97 \) ✓. (Also \( a_3 = 8 + 27 = 35 \) matches.)

(a) Overall: 6 Yes, 2 No.

(b) Weather: Sunny = days {1,3,4,5,6} → 5 Yes, 0 No → entropy 0 (pure). Rain = days {2,7,8} → 1 Yes, 2 No →

Weighted entropy = \( \frac{5}{8}(0) + \frac{3}{8}(0.918) = 0.344 \). Gain(Weather) = 0.811 − 0.344 = 0.467.

Wind: Weak = days {1,2,3,4} → 4 Yes, 0 No → entropy 0. Strong = days {5,6,7,8} → 2 Yes, 2 No → entropy 1. Weighted = \( \frac{4}{8}(0) + \frac{4}{8}(1) = 0.5 \). Gain(Wind) = 0.811 − 0.5 = 0.311.

(c) Weather has the larger gain (0.467 > 0.311), so Weather is the root.

• Sunny branch: all 5 days are Yes → leaf Yes.
• Rain branch: days {2,7,8} are mixed, split on Wind: Weak → day 2 only → leaf Yes; Strong → days 7, 8 → leaf No.

Weather?
├─ Sunny  → Yes
└─ Rain   → Wind?
            ├─ Weak   → Yes
            └─ Strong → No

The tree classifies all 8 training rows correctly.

First compute the overall average: \( \frac{50000 + 60000 + 70000 + 45000 + 80000}{5} = \frac{305000}{5} = 61000 \).

(a) 2 rows. Salaries above 61000 are 70000 (Chitra) and 80000 (Esha). Result: Chitra, Esha.

(b) 3 rows. This is a correlated subquery — for each employee it recomputes the max of that employee's own dept. Dept maxima: CSE → 70000, EEE → 80000, ME → 45000. The employees who equal their dept max: Chitra (70000), Esha (80000), Dipu (45000). Result: Chitra, Dipu, Esha.

(c) 1 row. Dept averages: CSE = (50000 + 70000)/2 = 60000; EEE = (60000 + 80000)/2 = 70000; ME = 45000. Only EEE (70000) beats the overall average 61000. Result: EEE.

Dijkstra finalizes the unvisited node with the smallest tentative distance, then relaxes its edges.

Final distances: S = 0, B = 2, A = 3, C = 8, D = 10, T = 13.

Path: follow the parents backward: T ← D ← C ← A ← B ← S, so

Notice two relaxations that improved earlier guesses: A dropped from 4 to 3 (via B), C dropped from 10 to 8 (via A), D dropped from 12 to 10 (via C), and T dropped from 14 to 13 (via D) — missing any of these is the common mistake.

Blanks:

• (1) mutex = 1 — binary lock for the buffer.
• (2) empty = 8 — number of empty slots, starts at the buffer size.
• (3) full = 0 — number of filled slots, starts at zero.
• (4) wait(full) — the consumer must wait for at least one filled slot.
• (5) wait(mutex) — lock before inserting.
• (6) signal(empty) — removing an item frees one slot.

Swapped waits → deadlock. Suppose the producer does wait(mutex) first and then wait(empty):

1. The buffer becomes completely full, so empty = 0.
2. The producer runs: wait(mutex) succeeds (mutex → 0), then wait(empty) blocks — but it blocks while still holding the mutex.
3. The consumer runs: wait(full) succeeds, then wait(mutex) blocks, because the producer holds it.
4. Now each process waits for something only the other can release: the producer needs the consumer to signal(empty), the consumer needs the producer to signal(mutex). Neither can move — deadlock (circular wait).

Rule: always acquire the counting semaphore (resource) before the mutex, and release in the opposite order.

(a) Start from {q0} and follow every input, creating new subset states as needed:

• A = {q0}: on a → q0 gives {q0, q1} = B; on b → {q0} = A.
• B = {q0, q1}: on a → q0 gives {q0, q1}, q1 gives nothing → B; on b → q0 gives {q0}, q1 gives {q2} → {q0, q2} = C.
• C = {q0, q2}: on a → {q0, q1} = B; on b → {q0} = A (q2 has no moves).

Only 3 subset states appear (out of the possible 8) — the construction stops when no new subset shows up.

(b) A DFA state is accepting iff it contains an NFA accepting state. Only C contains q2, so C is the accepting state.

(c) To reach q2 the NFA must use q0 →a→ q1 →b→ q2 as the final two moves, and q0 loops on everything before that. So the language is all strings that end in "ab". The DFA confirms it: you sit in B after a trailing a, and move to C exactly when a b follows an a.

(a)

• Alice sends \( A = 3^4 \bmod 17 = 81 \bmod 17 \). \( 81 - 4(17) = 81 - 68 = \mathbf{13} \).
• Bob sends \( B = 3^7 \bmod 17 \). Build it up: \( 3^2 = 9 \), \( 3^4 \equiv 13 \). So \( 3^7 = 3^4 \cdot 3^2 \cdot 3 \equiv 13 \times 9 \times 3 = 351 \). \( 351 - 20(17) = 351 - 340 = \mathbf{11} \).

(b)

• Alice: \( B^a = 11^4 \bmod 17 \). \( 11^2 = 121 \equiv 121 - 7(17) = 2 \), so \( 11^4 \equiv 2^2 = \mathbf{4} \).
• Bob: \( A^b = 13^7 \bmod 17 \). \( 13^2 = 169 \equiv 169 - 9(17) = 16 \equiv -1 \), so \( 13^4 \equiv 1 \) and \( 13^7 = 13^4 \cdot 13^2 \cdot 13 \equiv 1 \times (-1) \times 13 = -13 \equiv \mathbf{4} \).

Both get s = 4 ✓ (as expected, \( B^a = g^{ab} = A^b \)).

(c) MITM attack: attacker Mallory sits between them and swaps the public values.

1. Alice sends A = 13. Mallory intercepts it and forwards her own value \( M = g^m \bmod p \) to Bob instead.
2. Bob sends B = 11. Mallory intercepts it too and sends her M to Alice.
3. Now Alice computes a key with Mallory (\( M^a \)) and Bob computes a different key with Mallory (\( M^b \)). Mallory knows both keys.
4. Mallory decrypts every message with one key, reads or edits it, re-encrypts with the other key, and forwards it. Alice and Bob notice nothing.

It works because plain DH has no authentication — nobody proves whose public value is whose. Defense: authenticate the exchanged values, e.g. digitally sign A and B with certified keys (certificates/PKI), as done in TLS ("authenticated Diffie–Hellman").

Insert 10, 20: simple BST inserts, no imbalance:

10
  \
   20

Insert 30: 10 gets balance factor −2 with the new node in the right-right direction → RR case → single left rotation at 10:

   20
  /  \
10    30

Insert 25: goes left of 30. All balance factors stay within ±1 (20 has bf −1, 30 has bf +1) — no rotation:

   20
  /  \
10    30
     /
   25

Insert 28: goes right of 25 (path 20 → 30 → 25 → 28). Node 30 now has left height 2 and right height 0 → bf +2, and the insertion went left then right of 30 → LR case → double rotation: first left-rotate at 25 (28 rises, 25 becomes its left child), then right-rotate at 30 (28 rises again, 30 becomes its right child):

   20
  /  \
10    28
     /  \
   25    30

Final tree with balance factors (height of left subtree minus right subtree): for node 20, the left subtree (10) has height 0 and the right subtree (28) has height 1, so bf(20) = −1. bf(10) = 0, bf(28) = 0, bf(25) = 0, bf(30) = 0. All in {−1, 0, +1} ✓.

Rotations used: one single left rotation (RR) at step 3, one LR double rotation at step 5.

(a) AMAT = L1 hit time + L1 miss rate × (L2 access + L2 miss rate × memory time):

(b) Without L2, every L1 miss goes straight to memory:

So the L2 cache makes memory access 2.4× faster on average, even though it only helps on the 5% of accesses that miss L1.

(c) Global miss rate = fraction of ALL accesses that must go to main memory = L1 miss rate × L2 local miss rate = \( 0.05 \times 0.20 = 0.01 = \mathbf{1\%} \). (The 20% is "local": measured only among the accesses that reach L2.)

(a) Statement coverage: 2 tests. We must execute r = 1 (D1 true), r = r + 2 (D2 true) and r = r - 1 (D2 false).

• T1: (x = 20, y = 5) → D1 true, D2 true → covers r = 1 and r + 2.
• T2: (x = 5, y = −1) → D1 false, D2 false → covers r − 1.

One test cannot take both the if and else of D2, so 2 is minimal.

(b) Branch coverage: 2 tests. Needed outcomes: D1 {T, F}, D2 {T, F}. T1 gives (T, T), T2 gives (F, F) — all four branch outcomes covered with the same 2 tests.

(c) Condition coverage of D1: 3 tests. Each atomic condition must be seen both true and false. Because of short-circuit, when x > 0 is false, y > 0 is never evaluated.

• (x = 20, y = 5): x>0 = T, y>0 = T
• (x = 5, y = −1): x>0 = T, y>0 = F
• (x = −3, y = anything): x>0 = F (y not evaluated)

Two tests cannot show y>0 both ways and x>0 both ways, since the x-false test never touches y. So minimum = 3.

(d) Path coverage: 4 tests. Paths = D1 outcome × D2 outcome = 2 × 2 = 4, and all four are feasible:

• (T, T): x = 20, y = 5 → returns 3
• (T, F): x = 5, y = 5 → returns 0
• (F, T): x = 20, y = −1 → returns 2
• (F, F): x = 5, y = −1 → returns −1

Summary: statement 2, branch 2, condition 3, path 4 — each stronger criterion needs at least as many tests.

Output: 14 16

A static local variable is created and initialized once, and keeps its value between calls:

• Call 1: x = 1 → x = 2, returns 2 (s = 2)
• Call 2: x = 2 → x = 4, returns 4 (s = 6)
• Call 3: x = 4 → x = 8, returns 8 (s = 14)
• Call 4 (inside printf): x = 8 → x = 16, returns 16

So it prints s = 14 and then 16.

Without static: x becomes a normal automatic variable, re-created and re-initialized to 1 on every call. Each call computes x = 1 × 2 = 2 and returns 2. So s = 2 + 2 + 2 = 6 and the extra call returns 2 → output 6 2.

One-line rule: static local = lifetime of the whole program, initialized once; automatic local = reborn on every call.

Transmission time \( T_t = \frac{2000 \text{ bits}}{10^6 \text{ bps}} = 2 \text{ ms} \). Propagation \( T_p = 9 \) ms, so one full cycle = \( T_t + 2T_p = 2 + 18 = 20 \) ms.

(a)

Throughput = \( 0.10 \times 1 \text{ Mbps} = 100 \text{ kbps} \) (equivalently: 2000 bits every 20 ms).

(b) With window N, utilization \( U = \frac{N \cdot T_t}{T_t + 2T_p} \). For 100%:

So a window of 10 frames keeps the pipe full — the sender is still transmitting when the first ack returns.

(c) Go-Back-N with m sequence bits allows a window of at most \( 2^m - 1 \). Need \( 2^m - 1 \geq 10 \): m = 3 gives 7 (too small), m = 4 gives 15 ✓. So 4 bits.

(a) 73 = 64 + 8 + 1 = 01001001. Invert: 10110110, add 1: 10110111 = −73.

(b) 92 = 01011100, 45 = 00101101.

  01011100   (92)
+ 00101101   (45)
----------
  10001001

The result 10001001 is negative (sign bit 1): invert → 01110110, +1 → 01110111 = 119, so it reads as −119. But 92 + 45 = 137. This is overflow: 137 > 127, outside the 8-bit range [−128, 127]. Two positives produced a negative → overflow.

(c) 58 − 73 = 58 + (−73): 58 = 00111010, −73 = 10110111.

  00111010   (58)
+ 10110111   (−73)
----------
  11110001   (carry out = 0)

Result 11110001: invert → 00001110, +1 → 00001111 = 15, so the value is −15 ✓ (58 − 73 = −15). No overflow — the answer fits.

Overflow rule: overflow occurs iff the carry into the sign bit differs from the carry out of it (equivalently: adding two same-sign numbers gives the opposite sign). In (b) the operands are both positive and the sum looks negative → overflow. In (c) the operands have opposite signs — opposite-sign addition can never overflow.

X follows a Binomial(n = 5, p = 0.2) distribution: fixed number of independent yes/no trials with the same p.

(a)

(b) \( P(X \leq 1) = P(X = 0) + P(X = 1) \). \( P(X = 0) = (0.8)^5 = 0.32768 \).

So about 74% of the time, at most one packet is lost.

(c) For a binomial: \( E[X] = np = 5 \times 0.2 = \mathbf{1} \) and \( \mathrm{Var}(X) = np(1-p) = 5 \times 0.2 \times 0.8 = \mathbf{0.8} \) (standard deviation \( \approx 0.894 \)).

(a) Array (0-based): [12, 5, 18, 40, 7, 25]. Last parent index = ⌊6/2⌋ − 1 = 2. Sift down from index 2, 1, 0:

• i = 2 (18): child is 25 (index 5) → swap → [12, 5, 25, 40, 7, 18]
• i = 1 (5): children 40, 7 → biggest 40 → swap → [12, 40, 25, 5, 7, 18] (5 lands at index 3, a leaf)
• i = 0 (12): children 40, 25 → swap with 40 → [40, 12, 25, 5, 7, 18]; now 12 at index 1 has children 5, 7 → 12 is biggest, stop → [40, 12, 25, 5, 7, 18]

Check the heap property: 40 ≥ 12, 25; 12 ≥ 5, 7; 25 ≥ 18 ✓.

(b) Delete-max #1: remove 40, move the last element 18 to the root → [18, 12, 25, 5, 7]. Sift down: children 12, 25 → swap with 25 → [25, 12, 18, 5, 7] (18 at index 2 has no children in size 5).

Delete-max #2: remove 25, move 7 to the root → [7, 12, 18, 5]. Sift down: children 12, 18 → swap with 18 → [18, 12, 7, 5].

(c) In bottom-up build, a node's sift-down cost is its height. Half the nodes are leaves (height 0), a quarter have height 1, and so on: \( \sum_{h} \frac{n}{2^{h+1}} \cdot O(h) = O(n) \) because \( \sum h/2^h \) converges. Inserting one by one instead pays up to O(log n) per element for n elements → O(n log n). Most nodes sit near the bottom, and bottom-up gives them almost no work.

(a) Output: A B C ~C ~B ~A

• Construction order: base class first (A), then member objects in declaration order (b prints B), then the constructor body of C (prints C).
• Destruction order: the exact reverse — C's destructor body (~C), then members (~B), then the base (~A).

Note: even if C's constructor used an initializer list in a different order, members are always built in declaration order, not initializer-list order.

(b) delete p destroys through a A* pointer, but ~A() is not virtual. The behavior is undefined; in practice only ~A() runs — ~C() and ~B() are skipped, so the B member (and anything C owns) leaks. The one-word fix: declare the base destructor virtual (virtual ~A() { ... }). Then delete p correctly prints ~C ~B ~A. Rule: any class meant to be used polymorphically needs a virtual destructor.

(a) SRTF trace (always run the smallest remaining time; preempt on arrival):

• t = 0: only P1 → runs (rem 8).
• t = 1: P2 arrives (4 < 7) → preempts P1.
• t = 2: P3 arrives (2 < 3) → preempts P2.
• t = 3: P4 arrives (1 = P3's remaining 1, tie → P3 keeps running). P3 finishes at t = 4.
• t = 4: remaining — P1: 7, P2: 3, P4: 1 → P4 runs, finishes at 5.
• t = 5: P2 (3) runs, finishes at 8. Then P1 (7) runs, finishes at 15.

| P1 | P2 | P3  | P4 | P2   | P1        |
0    1    2     4    5      8           15

(b) Turnaround = completion − arrival; waiting = turnaround − burst:

Average turnaround = (15 + 7 + 2 + 2)/4 = 26/4 = 6.5. Average waiting = (7 + 3 + 0 + 1)/4 = 11/4 = 2.75.

(c) FCFS runs P1(0–8), P2(8–12), P3(12–14), P4(14–15). Waiting: P1 = 0, P2 = 8 − 1 = 7, P3 = 12 − 2 = 10, P4 = 14 − 3 = 11 → average = 28/4 = 7. SRTF's 2.75 is far better — short jobs no longer sit behind the long P1 (the convoy effect), which is exactly what SRTF is designed to avoid.

Proof (by contradiction). Assume L is regular. Then the pumping lemma gives a pumping length \( p \geq 1 \): every string \( s \in L \) with \( |s| \geq p \) can be split as \( s = xyz \) with

• \( |xy| \leq p \),
• \( |y| \geq 1 \),
• \( xy^iz \in L \) for every \( i \geq 0 \).

Choose \( s = a^p b^p \). Clearly \( s \in L \) and \( |s| = 2p \geq p \).

Where can y sit? Since \( |xy| \leq p \) and the first p symbols of s are all a's, both x and y lie inside the a-block. So \( y = a^k \) for some \( k \geq 1 \).

Pump up (i = 2):

This string has \( p + k > p \) a's but only \( p \) b's, so it is not in L. But the lemma promises \( xy^2z \in L \) — contradiction. (Pumping down with i = 0 gives \( a^{p-k}b^p \notin L \), a contradiction too.)

Therefore the assumption was wrong: L is not regular. ∎

Intuition behind the proof: a DFA has finitely many states, so while reading \( a^p \) it must repeat a state; looping that repeated part changes the number of a's without touching the b's, and the machine cannot notice — but the language requires the counts to match, which needs unbounded memory (a stack — L is context-free, accepted by a PDA).

(a) XOR bit by bit (1 when the bits differ):

M1 = 1 0 1 1 0 0 1 1
K  = 0 1 1 0 1 0 0 1
C1 = 1 1 0 1 1 0 1 0

Decryption: \( C_1 \oplus K = M_1 \) because \( (M \oplus K) \oplus K = M \oplus (K \oplus K) = M \oplus 0 = M \). Check the first bits: 1⊕0 = 1 ✓, 1⊕1 = 0 ✓ … recovering 10110011.

(b)

M2 = 1 1 1 1 0 0 0 0
K  = 0 1 1 0 1 0 0 1
C2 = 1 0 0 1 1 0 0 1

(c) The eavesdropper XORs the two ciphertexts — the key cancels out:

Numerically: \( C_1 \oplus C_2 = 11011010 \oplus 10011001 = 01000011 \), and directly \( M_1 \oplus M_2 = 10110011 \oplus 11110000 = 01000011 \) ✓ — identical.

So key reuse hands the attacker \( M_1 \oplus M_2 \) — pure plaintext structure with no key in it at all. If the messages are natural language (or one part is guessed — a "crib"), both plaintexts can be peeled apart. Perfect secrecy of the OTP is proved only when the key is truly random and used exactly once; this "two-time pad" mistake broke real systems (e.g. the VENONA project).

L[i][j] = LCS length of the first i chars of X and first j chars of Y. If the chars match: L[i][j] = L[i−1][j−1] + 1; else max of top and left.

(a)

Sample cells: row B (i=2), col B (j=1): match → 0 + 1 = 1. Row D (i=3), col D (j=2): match → L[2][1] + 1 = 2. Row A (i=4), col A (j=4): match → L[3][3] + 1 = 3. Row B (i=5), col B (j=5): match → L[4][4] + 1 = 4.

(b) LCS length = L[5][5] = 4.

(c) Traceback from (5,5): B = B match → take B, go to (4,4): A = A match → take A, go to (3,3): D ≠ C, left cell L[3][2] = 2 ≥ up L[2][3] = 1 → go to (3,2): D = D match → take D, go to (2,1): B = B match → take B, go to (1,0) → stop.

Read in reverse: LCS = "BDAB". Check: B‑D‑A‑B appears in order inside CBDAB (CBDAB) and inside BDCAB (BDCAB) ✓.

(a) By inclusion–exclusion:

(b) None = 120 − 100 = 20.

(c) "Exactly one" per subject = total − both pairwise overlaps + the triple (added back because it was subtracted twice):

• Math only: 65 − 20 − 25 + 8 = 28
• Physics only: 45 − 20 − 15 + 8 = 18
• Chemistry only: 42 − 25 − 15 + 8 = 10

Exactly one = 28 + 18 + 10 = 56.

Consistency check: exactly two = (20 − 8) + (25 − 8) + (15 − 8) = 12 + 17 + 7 = 36; all three = 8. Then 56 + 36 + 8 = 100 ✓ matches part (a), and 100 + 20 = 120 ✓ the whole class.

(a) Average CPI = 0.5(1) + 0.3(2) + 0.2(3) = 0.5 + 0.6 + 0.6 = 1.7.

(b) ALU instructions drop from \( 0.5 \times 10^9 \) to \( 0.4 \times 10^9 \). New instruction count = \( (0.4 + 0.3 + 0.2) \times 10^9 = 0.9 \times 10^9 \). Total cycles:

New time = \( \frac{1.6 \times 10^9}{2 \times 10^9} = 0.8 \) s. Speedup = 0.85 / 0.8 = 1.0625 (6.25% faster).

(c) New CPI = \( \frac{1.6 \times 10^9}{0.9 \times 10^9} \approx 1.78 \), which is worse than 1.7 — because we removed only cheap CPI-1 instructions, so the remaining mix is "heavier" per instruction. But performance depends on the product IC × CPI (total cycles), which fell from 1.7 × 10⁹ to 1.6 × 10⁹. Lesson: never judge performance by CPI (or MIPS) alone — only total execution time counts.

(a)

• AB⁺: AB → C gives C; C → D gives D → {A, B, C, D} (everything).
• BC⁺: C → D gives D; D → A gives A → {A, B, C, D}.
• BD⁺: D → A gives A; then AB → C gives C → {A, B, C, D}.
• C⁺: C → D, D → A → {A, C, D} — no B, so not a key.

(b) B never appears on the right side of any FD, so every key must contain B. B alone: B⁺ = {B}, not enough. Adding one attribute: AB⁺, BC⁺, BD⁺ each cover R (part a), so AB, BC, BD are all candidate keys. They are minimal (B alone fails), and any other superkey contains one of them. Candidate keys: AB, BC, BD.

(c) Prime attributes = attributes in some key = {A, B, C, D} — every attribute is prime. 2NF and 3NF violations both need a non-prime attribute, so R passes them automatically: R is in 3NF.

But R is not in BCNF: BCNF demands that for every nontrivial FD X → Y, X is a superkey. Here C → D holds but C⁺ = {A, C, D} ≠ R, so C is not a superkey (same problem with D → A). So the highest normal form is 3NF — this is the classic case where 3NF and BCNF differ.

(a) MIN values: B = min(3, 12, 8) = 3; C = min(2, 14, 6) = 2; D = min(1, 9, 5) = 1. Root (MAX) = max(3, 2, 1) = 3, choosing move B.

(b) Alpha–beta, left to right (α = best for MAX so far, β = best for MIN so far):

1. Node B (α = −∞, β = +∞): see 3 → β = 3; see 12, 8 (no cutoff, both ≥ nothing below α). B returns 3. Root now has α = 3.
2. Node C (α = 3, β = +∞): first leaf 2 → β = 2. Now β = 2 ≤ α = 3 → β-cutoff: MIN can already force ≤ 2 here, but MAX already has 3, so MAX will never come here. Leaves 14 and 6 are pruned.
3. Node D (α = 3, β = +∞): first leaf 1 → β = 1 ≤ α = 3 → cutoff at once. Leaves 9 and 5 are pruned.

Root value = 3 (identical to plain minimax, as always). Evaluated leaves: 3, 12, 8, 2, 1 (five). Pruned: 14, 6, 9, 5 (four of the nine).

(c) Pruning depends on move order. Best case (examining each MIN node's smallest leaf first, and the best MAX move first) cuts the effective branching factor to about \( \sqrt{b} \) — roughly \( O(b^{m/2}) \) nodes instead of \( O(b^m) \), doubling the search depth for the same effort. Worst-case order (best leaf last) prunes nothing. That is why real engines sort moves (e.g. by previous iteration scores) before searching.

(a)

(b) \( CAF = 0.65 + 0.01 \times 40 = 0.65 + 0.40 = 1.05 \).

(c) Effort = \( \frac{114.45}{8} \approx 14.3 \) person-months (about 14–15 PM).

Advantage over LOC: function points are measured from the requirements/specification, before any code exists, and they are language-independent — 100 FP means the same functional size in C or in Python, while the LOC for the same program can differ 5–10×. (LOC also punishes concise code and cannot be known until the project is nearly done.)