(a) struct P = 12 bytes. Layout byte by byte:

offset: 0     1  2  3   4  5  6  7   8     9  10 11
        a     [pad....]  b  b  b  b   c     [pad.....]

• a sits at offset 0. The next member b is an int, so it must start at a multiple of 4 → offsets 1–3 become 3 padding bytes, and b occupies 4–7.
• c sits at offset 8. Then the struct's total size must be a multiple of the largest alignment (4), so 3 tail padding bytes (9–11) are added → size 12. (Tail padding exists so that in an array, every element's b stays aligned.)

struct Q = 8 bytes. Layout:

offset: 0  1  2  3   4     5     6  7
        b  b  b  b   a     c     [pad]

b fills 0–3, a at 4, c at 5, and only 2 tail padding bytes (6–7) round the size up to a multiple of 4. Same members, 12 vs 8 bytes — only the order changed.

(b) Hardware reads memory in aligned chunks. A 4-byte int at a misaligned address needs two memory reads (or, on some CPUs, causes a fault). Padding keeps every member at its natural alignment so access stays fast and legal.

(c) Rule: order members from largest to smallest (or group same-size members together) — big aligned members first leave no gaps, and the small ones pack at the end. sizeof(arr) = 10 × 12 = 120 bytes — arrays multiply the padded size, so the waste multiplies too.

(a) Each clock: shift right (Q3→Q2→Q1→Q0) and load Q3 with Q0′:

The 1s "fill up" from the left, then "drain out" — after 8 clocks it is back at 0000, so it is a MOD-8 counter.

(b) An n-bit Johnson counter cycles through 2n states. For n = 4: Johnson = 8 states, ring counter = n = 4 states (a single circulating 1), binary counter = 2ⁿ = 16 states. Johnson doubles the ring counter's states with the same 4 flip-flops.

(c) Advantage: every state can be decoded with a single 2-input AND gate (e.g. state 1100 is Q2·Q1′), and only one flip-flop changes per clock, so decoding is glitch-free — no need for the n-input gates a binary counter's decoder uses. Problem: 2⁴ − 8 = 8 states are unused. Noise can knock the counter into one of them, and it will then cycle among invalid states forever — a practical design adds self-correcting logic to force it back into the main loop.

Poisson with rate \( \lambda = 3 \):

(a) \( P(X = 0) = e^{-3} \dfrac{3^0}{0!} = e^{-3} \approx \mathbf{0.0498} \) — about a 5% chance of a silent minute.

(b) \( P(X = 2) = e^{-3} \dfrac{3^2}{2!} = e^{-3} \times \dfrac{9}{2} = 4.5 \times 0.0498 \approx \mathbf{0.224} \).

(c) Use the complement — "at least 2" means not 0 and not 1:

(\( P(1) = e^{-3} \times 3 \approx 0.149 \).) So roughly 80% of minutes bring 2 or more requests.

For a Poisson distribution the mean and the variance are both equal to λ: \( E[X] = \mathrm{Var}(X) = 3 \). This equality is the quick signature of a Poisson model in exam questions.

(a) G has degree 3, so append three 0s: divide 101110000 by 1001 using XOR (no borrows):

1 0 1 1 1 0 0 0 0
1 0 0 1             ← XOR at the leading 1
-------
0 0 1 0 1 0 0 0 0
    1 0 0 1         ← next leading 1
    -------
0 0 0 0 1 1 0 1 0   (bits 2-5: 1010 ⊕ 1001 = 0011)
        1 0 0 1
        -------
0 0 0 0 0 1 0 1 1   (bits 4-7: 1100 ⊕ 1001 = 0101)
          1 0 0 1
          -------
0 0 0 0 0 0 0 1 1   (bits 5-8: 1010 ⊕ 1001 = 0011)

No leading 1 with 4 bits left → stop. Remainder = last 3 bits = 011.

Transmitted frame = data + remainder = 101110 011 → 101110011 (the appended zeros are replaced by the CRC).

(b) The receiver divides the whole received frame 101110011 by 1001. By construction the frame is an exact multiple of G, so the remainder comes out 000 → frame accepted.

(c) Flipping the 3rd bit gives 100110011. Dividing by 1001 leaves remainder 001 ≠ 000, so the receiver rejects the frame and asks for retransmission. In polynomial terms the error added \( x^6 \), which is not divisible by \( x^3 + 1 \) — any single-bit error is caught because G has more than one term.

Output: 8 11

• Overloaded operators keep the normal precedence: * binds tighter than +. So a + b * 2 means a + (b * 2).
• b * 2 calls b.operator*(2) → Vec(3×2, 4×2) = (6, 8).
• a + (6, 8) calls a.operator+(...) → Vec(1+6, 2+8) = (7, 10), copied into c.
• ++c calls the prefix operator++ → c becomes (8, 11). It returns *this by reference, the standard prefix style (a postfix version would take a dummy int parameter and return the old value by copy).

Why 2 * b fails: a member operator is called on the left operand. 2 * b would need 2.operator*(b) — but 2 is an int, not a Vec, and an int has no members. The compiler cannot convert the left side for a member call.

Fix: add a non-member (often friend) overload whose first parameter is the int:

friend Vec operator*(int k, const Vec &v) { return Vec(v.x * k, v.y * k); }

Now both b * 2 (member) and 2 * b (non-member) work. Rule: when the left operand is not your class, the operator must be a free function.

(a) Set \( \frac{1}{k(k+1)} = \frac{A}{k} + \frac{B}{k+1} \). Then \( 1 = A(k+1) + Bk \). Put k = 0 → A = 1; put k = −1 → B = −1:

(b) The sum telescopes — every middle term cancels with its neighbour:

Only the very first term (1) and the very last term (−1/(n+1)) survive.

For n = 99: \( \dfrac{99}{100} = \mathbf{0.99} \). Quick check with n = 2: \( \frac{1}{1\cdot2} + \frac{1}{2\cdot3} = \frac{1}{2} + \frac{1}{6} = \frac{2}{3} = \frac{2}{2+1} \) ✓.

(c) As \( n \to \infty \), \( \frac{1}{n+1} \to 0 \), so the sum approaches \( \mathbf{1} \). (An infinite series of positive terms that stays below 1 and gets arbitrarily close to it — a convergent series with sum exactly 1.)

Priors: \( P(\text{spam}) = 4/10 = 0.4 \), \( P(\text{ham}) = 6/10 = 0.6 \).

(a) Zero-frequency problem. Without smoothing, \( P(\text{"meeting"}\mid\text{spam}) = 0/4 = 0 \). The whole spam score becomes \( 0.4 \times \frac{3}{4} \times 0 = 0 \) — one unseen word vetoes the class completely, no matter how spammy the rest of the email is. That is why raw counts are never used.

(b) With Laplace smoothing (add 1 to the count, add 2 to the denominator for a binary feature):

• \( P(\text{free}\mid\text{spam}) = \frac{3+1}{4+2} = \frac{4}{6} = \frac{2}{3} \),   \( P(\text{meeting}\mid\text{spam}) = \frac{0+1}{4+2} = \frac{1}{6} \)
• \( P(\text{free}\mid\text{ham}) = \frac{1+1}{6+2} = \frac{1}{4} \),   \( P(\text{meeting}\mid\text{ham}) = \frac{3+1}{6+2} = \frac{1}{2} \)

Naive Bayes multiplies (features assumed independent given the class):

0.075 > 0.0444 → classify as ham. ("meeting" is strong ham evidence; "free" leans spam but not enough.)

(c) Normalize the two scores:

So the filter says ham with about 63% confidence — smoothing kept the decision sensible instead of collapsing to zero.

(a) The RA says: keep CSE students, keep A-grade enrollments, natural-join on sid, project the name. In SQL:

SELECT DISTINCT s.name
FROM   Student s JOIN Enrolled e ON s.sid = e.sid
WHERE  s.dept = 'CSE' AND e.grade = 'A';

(DISTINCT matches the set behavior of π.) Evaluate step by step:

• CSE students: sid 1 (Rina), sid 3 (Salma).
• A-grade rows: (1, C101), (2, C101), (3, C102).
• Join on sid → sid 1 and sid 3 survive.

Result: Rina, Salma (2 rows). Karim has an A but is EEE; Tanvir is ME with a B.

(b) The SQL joins, filters grade = 'B', and projects dept. In relational algebra:

B-grade rows: (1, C102), (4, C103) → students 1 (CSE) and 4 (ME). Result: {CSE, ME}. Note π automatically removes duplicates, which is why the SQL needs DISTINCT to match — a favourite exam point about the bag-vs-set difference between SQL and relational algebra.

(a) The array halves each level: sizes 16 → 8 → 4 → 2 → 1. That is \( \log_2 16 = 4 \) levels of splitting, i.e. 5 levels of nodes counting the root. Calls: 1 + 2 + 4 + 8 + 16 = 31 calls (in general \( 2n - 1 \)).

(b) Count the merges bottom-up (a merge producing size 2s costs at most 2s − 1):

(c) Every level of the tree touches all n elements once, doing at most n comparisons per level, and there are \( \log_2 n \) merging levels → \( O(n \log n) \). Here: ≈ 16 × 4 = 64 is the rough bound and 49 is the exact worst case (each level is a bit under n because every merge saves at least one comparison).

Bubble sort worst case: \( \frac{n(n-1)}{2} = \frac{16 \times 15}{2} = 120 \) comparisons — about 2.4× worse at n = 16, and the gap explodes as n grows (for n = 1024: ~10 240 vs ~523 776).

(a) SJF: shortest bursts first: P2 (3), P4 (3, tie → higher number after P2), P1 (6), P3 (8).

| P2 | P4 | P1   | P3     |
0    3    6     12       20

Waiting = start − arrival: P2 = 0, P4 = 3, P1 = 6, P3 = 12 → average = 21/4 = 5.25.

(b) RR, q = 2:

| P1 | P2 | P3 | P4 | P1 | P2 | P3 | P4 | P1 | P3 | P3 |
0    2    4    6    8   10   11   13   14   16   18   20

(P2 finishes at 11 using only 1 unit of its second slice; P4 finishes at 14.) Completion: P1 = 16, P2 = 11, P3 = 20, P4 = 14. Waiting = completion − burst (arrival 0): P1 = 10, P2 = 8, P3 = 12, P4 = 11 → average = 41/4 = 10.25.

(c) SJF nearly halves the average wait (5.25 vs 10.25), but look at first response (first time each process gets the CPU):

Under SJF the longest job (P3) sits untouched for 12 units — on a desktop that is a frozen app. RR guarantees every process is served within (n−1)q, gives smooth interactive response, and needs no knowledge of burst lengths (which SJF must predict). SJF also risks starvation of long jobs if short ones keep arriving. So: batch throughput → SJF; interactivity and fairness → RR.

(a) A DFA has a fixed, finite number of states — say p of them. While it reads \( a^p \) it visits p + 1 states, so some state repeats (pigeonhole). That means two different prefixes \( a^i \) and \( a^j \) (i ≠ j) land in the same state, and from there the DFA treats them identically. But \( a^i b^{2i} \in L \) while \( a^j b^{2i} \notin L \) — the DFA must accept both or reject both, contradiction. Accepting L needs unbounded counting of the a's, which finite memory cannot do.

(b) PDA (accept by empty stack + end of input, start symbol Z on stack):

• Reading an a (still in the a-phase): push two X's onto the stack.
• Reading a b: pop one X. Once the first b is read, switch to the b-phase — any later a rejects (wrong order).
• At end of input: accept iff only Z remains (every pushed X was matched by exactly one b). n = 0 (empty string) accepts immediately.

Each a deposits 2 tokens and each b spends 1, so acceptance forces #b = 2·#a — exactly L.

(c) Trace of aabbbb (stack shown top-first, Z at bottom):

Input finished, stack back to Z → accept ✓. (For aabbb an X would remain → reject; for aabbbbb a b would find no X → reject.)

(a) Repeat the key under the message and add mod 26 (\( C_i = (M_i + K_i) \bmod 26 \)):

Ciphertext: CHWEEY

(b) Decrypt with \( M_i = (C_i - K_i) \bmod 26 \): C−C = 0→A; H−O = 7−14 = −7 ≡ 19→T; W−D = 22−3 = 19→T; E−E = 0→A; E−C = 2→C; Y−O = 24−14 = 10→K → ATTACK ✓.

(c) The two T's encrypt to different letters (H and W), because they line up with different key letters (O and D). A Caesar cipher shifts every letter by the same amount, so letter frequencies pass straight through — count the most common ciphertext letter and you have likely found E. Vigenère is polyalphabetic: it smears each plaintext letter over several ciphertext letters, flattening the frequency histogram.

It still falls to the Kasiski examination: repeated plaintext fragments that align with the same key position produce repeated ciphertext fragments; the distances between repeats reveal the key length m. Then the ciphertext splits into m interleaved Caesar ciphers, each broken by ordinary frequency analysis.

(a) Enqueue: rear = (rear + 1) % 5; dequeue: front = (front + 1) % 5. Dashes are free slots:

(b) At enqueue(F): rear was 4, and (4 + 1) % 5 = 0 — the rear pointer wraps from the end of the array back to index 0, reusing the slot A freed earlier. That reuse is the whole point of the circular design; a linear queue would have declared the array full despite two free slots.

(c) After enqueue(G) the queue was full (size 5); after the last dequeue it holds 4 elements (D, E, F, G from front to rear: indices 3, 4, 0, 1) — not full. The counter is needed because with pure pointers, full and empty look identical: both give front == (rear + 1) % 5 / coincident pointers depending on convention. The two standard fixes: keep a size counter (as here), or sacrifice one slot and call the queue full when (rear + 2) % capacity == front-style condition — either removes the ambiguity.

On a TLB hit: TLB lookup + one memory access = 10 + 100 = 110 ns. On a miss: TLB lookup + page-table access + data access = 10 + 100 + 100 = 210 ns.

(a) With hit ratio h:

For h = 0.90: \( EAT = 0.9 \times 110 + 0.1 \times 210 = 99 + 21 = \mathbf{120 \text{ ns}} \).

(b) For h = 0.98: \( EAT = 0.98 \times 110 + 0.02 \times 210 = 107.8 + 4.2 = \mathbf{112 \text{ ns}} \).

(c) Without a TLB every access needs two memory trips (page table + data) = 200 ns. So the TLB gives speedup 200/120 ≈ 1.67 at 90% and 200/112 ≈ 1.79 at 98% — paging's overhead falls from 100% to about 12%. Note the EAT can never beat 110 ns: the TLB only removes the translation access, not the data access.

A TLB of just 64–512 entries hits so often because of locality of reference: a program spends long stretches inside a few pages (current code page, stack page, active data pages), so the same translations are used again and again. Each TLB entry covers a whole page (e.g. 4 KB), so a handful of entries covers the entire working set.

(a) Equivalence classes — inputs the program should treat identically:

Seven classes → 7 tests cover every behavior once.

(b) Boundary values — each edge of each range, plus one step outside the valid domain:

• Domain edges: −1, 0 and 100, 101
• F/C edge: 39, 40  ·  C/B edge: 59, 60  ·  B/A edge: 79, 80

That is 10 focused tests: −1, 0, 39, 40, 59, 60, 79, 80, 100, 101.

(c) Random tests pile up in the middle of big ranges — dozens of values like 47, 52, 68 all exercise the same code path, adding no new information. EP guarantees every path is hit at least once, and BVA aims exactly where programmers err: comparison operators. Concrete catch: if the code says if (mark > 80) grade = 'A' instead of >=, every mid-range random test passes, but the boundary test mark = 80 returns B instead of A — bug found immediately. Same for 39/40, 59/60, and 100/101 (accepting 101 shows a missing upper check).

(a) Output: 3 2 1 1 2 3

Trace (indent = recursion depth):

f(3): print 3 → call f(2)
  f(2): print 2 → call f(1)
    f(1): print 1 → call f(0)
      f(0): returns immediately
    f(1): print 1 → return
  f(2): print 2 → return
f(3): print 3 → return

(b) Calls: f(3), f(2), f(1), f(0) → 4 calls (in general n + 1).

(c) For general n the output is the palindrome:

The descending half (n … 1) comes from the printf placed before the recursive call — it runs while the stack is winding up, each frame printing on its way in. The ascending half (1 … n) comes from the printf after the call — those statements are frozen on the stack and only run as the frames pop, i.e. while the stack is unwinding, in reverse order of creation (LIFO). This "code after the recursive call runs backwards" behavior is the standard exam trick — for example, it is exactly how you print a linked list or a number's binary digits in reverse.

(a) In order:

1. DNS cache check — empty, so the laptop must ask 8.8.8.8.
2. Routing decision: 8.8.8.8 AND-ed with mask /24 gives 8.8.8.0 ≠ 192.168.1.0 → the DNS server is off-subnet → next hop is the gateway 192.168.1.1.
3. ARP request (broadcast): "Who has 192.168.1.1? Tell 192.168.1.20." — sent to MAC ff:ff:ff:ff:ff:ff.
4. ARP reply (unicast): the gateway answers with its MAC. The laptop stores it in the ARP cache.
5. DNS query (UDP, port 53): frame has destination MAC = gateway's, but destination IP = 8.8.8.8. The gateway forwards it toward the Internet.
6. DNS response: A record — www.example.com → 93.184.216.34. Cached with its TTL.
7. TCP SYN to 93.184.216.34 port 443/80 — again off-subnet, again framed to the gateway's MAC (ARP cache hit this time, no new ARP).

(b) The laptop ARPs only for the gateway's MAC (both times a MAC is needed, it is the same gateway). ARP works by broadcast, and broadcasts do not cross routers — a link-layer address is only meaningful on the local segment. 8.8.8.8 and 93.184.216.34 sit on distant networks; their MACs would be useless here anyway, because each hop of the path rewrites the frame with the next hop's MAC while the IP addresses stay end-to-end. Rule: MAC = next hop, IP = final destination.

(c) On reload: steps 1 (lookup now hits the DNS cache, if TTL unexpired) and 3–4 (the ARP cache still holds the gateway's MAC) disappear. The laptop goes straight to the TCP connection — this is why the second visit to any site feels snappier.

(a) Add 0110 (6) when the raw 4-bit sum is greater than 9 (1010–1111) or the 4-bit addition produced a carry out (sum ≥ 16). Reason: BCD skips the six codes 1010–1111, so crossing 9 must jump ahead by 6 to land on the right BCD digit.

(b) 7 + 6:

  0111   (7)
+ 0110   (6)
------
  1101   raw sum = 13 → invalid BCD (> 9), no carry
+ 0110   correction
------
1 0011   → carry 1, digit 0011

Result: carry 1, digit 3 → 13 ✓.

8 + 9:

  1000   (8)
+ 1001   (9)
------
1 0001   raw sum: carry K = 1, low nibble 0001 (raw value 17)
  0001
+ 0110   correction (because K = 1)
------
  0111   → digit 0111, carry stays 1

Result: carry 1, digit 7 → 17 ✓. Note the two cases trigger differently: 13 was caught by "> 9", 17 by "carry out" (its low nibble 0001 looks innocent).

(c) Per decimal digit: two 4-bit binary adders — the first adds the digits, the second adds 0000 or 0110 chosen by the correction signal. Detection: sums 10–15 have Z8 with Z4 or Z8 with Z2 set, so

C is also the decimal carry to the next digit stage. (Check: 1101 → Z8Z4 = 1 ✓; 1010 → Z8Z2 = 1 ✓; 1001 = 9 → neither ✓; 17 → K = 1 ✓.)

(a) Sum = 4 + 8 + 6 + 5 + 3 + 7 + 9 + 6 = 48 → mean = 48/8 = 6. Sorted: 3, 4, 5, 6, 6, 7, 8, 9 → n even, median = average of the 4th and 5th values = (6 + 6)/2 = 6. Mode = 6 (appears twice, all others once). All three equal — a nicely symmetric dataset.

(b) Squared deviations from the mean 6:

Sum of squares = 28.

(c) Sample variance:

We divide by n − 1 (Bessel's correction) because the deviations are measured from the sample mean, which was itself computed from the same data — the data sit closer to their own mean than to the true population mean, so dividing by n would underestimate the real variance on average. Losing one degree of freedom (the mean is fixed by the data) and dividing by n − 1 makes \( s^2 \) an unbiased estimator.

(a) All five keys have \( h_1 = k \bmod 11 = 3 \) — a worst-case collision chain on slot 3:

Final table: slot 3 → 14, slot 5 → 47, slot 6 → 25, slot 8 → 58, slot 9 → 36 (others empty). Every colliding key resolved in just one extra probe.

(b) Linear probing tries 3, 4, 5, 6, … for every key: 14→3, 25→4, 36→5, 47→6, 58→7. The keys pile into the contiguous run 3–7: primary clustering. Every future key hashing anywhere into that run must scan to its end, and the cluster keeps growing — probe costs degrade badly. Double hashing avoids this because each key jumps with its own step size (7, 3, 6, 2, 5 here), scattering the chain across the table.

(c) If \( h_2 = 0 \), the probe sequence is \( h_1, h_1, h_1, \ldots \) — it never moves, an infinite loop on one slot; the formula 7 − (k mod 7) gives values 1–7, never 0, exactly to prevent that. The table size m should be prime (or at least coprime to every possible \( h_2 \)) so that stepping by \( h_2 \) visits all m slots before repeating: with gcd(h2, m) = 1 the sequence is a full cycle. If m = 12 and h2 = 4, only 3 slots would ever be probed and the insert could fail with the table nearly empty.

(a) Output: 7 — wider compares the private widths 3 and 7 directly and returns the larger.

(b) A friend function is a non-member function that a class explicitly grants access to its private and protected members. The declaration friend int wider(Box, Box); inside Box is that grant — it is the class's own decision, so encapsulation is loosened only where the class author chooses. wider is not a member: it is a free function (called as wider(p, q), not p.wider(q)), it has no this pointer, and the public:/private: label where the friend declaration sits is irrelevant.

(c) Friendship is:

• Not mutual — Box trusting wider (or class A trusting B) gives Box no access back.
• Not inherited — a class derived from Box does not inherit Box's friends, and a friend of a base is not a friend of the derived class.
• Not transitive — a friend of my friend is a stranger.

Classic use: stream output, friend ostream& operator<<(ostream& os, const Box& b) — it cannot be a member of Box because the left operand is the stream, yet it needs Box's private data. Same story for symmetric binary operators like operator+ on two objects, or int * Vec style mixed-type operators.

(a) 3 frames (F = fault, H = hit; frames listed oldest → newest):

9 faults (hits on the 1, 2 after 5 arrives, and on the final 5).

(b) 4 frames:

10 faults — after page 5 evicts page 1, every following reference misses.

(c) More frames gave more faults (10 > 9): this is Belady's anomaly, and this reference string is the classic demonstration. Intuitively, with 4 frames FIFO kept the early pages "too long", so its eviction order fell exactly out of phase with the reuse pattern.

LRU cannot show the anomaly because it is a stack algorithm: at every instant, the set of pages LRU keeps in k frames (the k most recently used pages) is always a subset of what it would keep in k + 1 frames. A hit with k frames is therefore automatically a hit with k + 1 — fault counts can only stay equal or fall as memory grows. FIFO's content depends on arrival order, not recency, so the inclusion property fails.

(a) Two readings of if E₁ then if E₂ then a else a:

• Tree 1 (else with the inner if): S → if E₁ then [ if E₂ then a else a ]. The outer if has no else.
• Tree 2 (else with the outer if): S → if E₁ then [ if E₂ then a ] else a. The inner if has no else.

Both are valid derivations of the same string — the grammar is ambiguous, and the two trees genuinely mean different programs (if E₁ is false, Tree 1 runs nothing while Tree 2 runs the else-branch).

(b) A shift–reduce conflict, occurring exactly when the lookahead is else. At that moment the parser has if E then S sitting on top of its stack (the inner if is complete) and must choose between:

• Reduce by S → if E then S — close the inner if now, leaving the else for the outer if (Tree 2), or
• Shift the else — keep growing the inner if into the longer production S → if E then S else S (Tree 1).

Since else ∈ FOLLOW(S) (an S can be followed by else in the second production), both actions land in the same table cell — SLR, LALR, and LR(1) all keep this conflict, because it comes from real ambiguity, not weak lookahead.

(c) Standard resolution: prefer shift over reduce for this conflict (Yacc/Bison's default, plus a suppressed warning). Shifting attaches each else to the nearest unmatched if — Tree 1 — which is exactly the rule C, C++, and Java define. (The alternative fix is rewriting the grammar into "matched"/"unmatched" statements, which is unambiguous but clumsier; languages like Python sidestep the issue with indentation, and others require explicit end if.)

(a)

• MAC: sender computes tag = MAC(K, message) with a shared symmetric key K and appends it. The receiver recomputes the tag with the same K and compares. Example: HMAC-SHA256.
• Digital signature: sender hashes the message and encrypts the hash with their private key; anyone verifies by decrypting the signature with the sender's public key and comparing against a fresh hash. Example: RSA or DSA signatures.

(b)

(c) The two banks already share K and trust each other's infrastructure — a MAC is the right fit: fast enough for thousands of orders per second and verifiable by the only party who matters (the other bank). The e-commerce site needs digital signatures: a customer's order signed with the customer's private key can be shown to a judge and verified with the public key.

Why a MAC can never give non-repudiation: the shared key K is held by both parties, and a valid tag only proves "someone holding K made this". The receiving bank could have forged the very tag it presents as evidence — so the sender can always plausibly deny it, and no third party can tell who computed it. A signature binds the message to the one private key that only the signer holds, which is exactly what a court needs.

(a) In-degrees: A = 0, B = 0, C = 2 (from A, B), D = 1 (from C), E = 1 (from C).

1. Queue starts with the zero in-degree nodes {A, B}. Remove one (say A): C drops to 1.
2. Remove B: C drops to 0 → C enters the queue.
3. Remove C: D and E both drop to 0 → both enter the queue.
4. Remove D, then E (either order). All 5 nodes output → done.

One possible output: A, B, C, D, E.

(b) Structure of every valid order: A and B (in either order) must both precede C; D and E (in either order) must both follow C. With 5 positions, C is forced into the middle position, {A, B} fill the first two slots, {D, E} the last two:

• A, B, C, D, E
• A, B, C, E, D
• B, A, C, D, E
• B, A, C, E, D

(Kahn's algorithm exposes the same count: 2 choices at step 1, then forced, then 2 choices after C.)

(c) D → B creates the cycle B → C → D → B: B needs to run before C, C before D, and now D before B — impossible, so no topological order exists (a topological sort is defined only for DAGs). Kahn's algorithm detects it cleanly: after outputting A, the remaining nodes B, C, D, E all have in-degree ≥ 1 (B now has in-degree 1 from D), the queue becomes empty, and the algorithm stops having output fewer than 5 nodes. "Output count < node count" is precisely Kahn's cycle report — which is how build tools print "circular dependency detected".

DISCRETE has 8 letters: D, I, S, C, R, E, T, E — the letter E repeats twice, everything else is distinct.

(a) Permutations of a multiset — divide by the repeats:

(Dividing by 2! kills the double-counting from swapping the two identical E's.)

(b) Glue the two E's into one block [EE]. Now we arrange 7 objects: [EE], D, I, S, C, R, T — all distinct (and the two E's inside the block are identical, so the block has only 1 internal arrangement):

Sanity check: the fraction of arrangements with the E's together is 5040/20160 = 1/4 — and directly, the two E's occupy 2 of \( \binom{8}{2} = 28 \) position pairs, of which 7 are adjacent: 7/28 = 1/4 ✓.

(c) Glue I, E, E into one vowel block. Objects to arrange: [vowels], D, S, C, R, T = 6 distinct objects → 6! ways. Inside the block the three vowels arrange in \( \frac{3!}{2!} = 3 \) distinguishable ways (IEE, EIE, EEI):

Pattern to remember: "together" → treat the group as one object, multiply by the group's internal arrangements, and keep dividing by factorials of identical letters.

(a) In cycle stealing, the DMA controller takes the memory bus for one cycle at a time, transfers one word/byte, and immediately returns the bus to the CPU — the CPU is delayed by single cycles, "stolen" between its own accesses, and barely notices. In burst mode, the DMA controller seizes the bus and moves a whole block back-to-back — faster for the device, but the CPU stalls for the entire burst. Cycle stealing suits slow-to-medium devices; burst mode suits fast ones (disk block into a full buffer).

(b) Stolen time per second = 8000 steals × 1 µs = 8000 µs = 8 ms. Fraction:

The CPU loses under 1% of its cycles — effectively it runs at 99.2% speed while the transfer streams in the background.

(c) Programmed I/O cost = 8000 bytes × 20 µs = 160 000 µs = 0.16 s per second:

Fundamental advantage: DMA moves data without executing CPU instructions per byte — the CPU sets up the transfer once (address, count, direction), does useful work meanwhile, and takes a single interrupt when the whole block is done. Programmed I/O burns instruction cycles on every byte (poll status, read register, store, loop), so its overhead scales with the data rate and would swallow the CPU entirely for fast devices.

Two operations conflict when they belong to different transactions, touch the same item, and at least one is a write.

S1 — conflicts:

• On X: r1(X)→w2(X), w1(X)→r2(X), w1(X)→w2(X) — all give edge T1 → T2.
• On Y: r2(Y)→w1(Y), w2(Y)→r1(Y), w2(Y)→w1(Y) — all give edge T2 → T1.

Graph: T1 → T2 and T2 → T1 — a cycle. So S1 is not conflict-serializable: T1 must come before T2 (they fought over X in that order) but also after T2 (they fought over Y in the other order) — no serial order satisfies both. Intuitively, each transaction read the other's "middle" state.

S2 — conflicts:

• On X: r1(X)→w2(X), w1(X)→r2(X), w1(X)→w2(X) — all edges T1 → T2.
• On Y: only T1 touches Y (r1, w1) — no conflict.

Graph: a single edge T1 → T2 — acyclic. S2 is conflict-serializable, equivalent to the serial order T1, then T2. (Check: swapping the non-conflicting neighbours r1(Y) and w2(X) turns S2 into r1(X), w1(X), r1(Y), w1(Y)?, … — repeatedly swapping non-conflicting adjacent operations pushes all of T1 before all of T2, which is the definition of conflict equivalence.)

Method summary: precedence-graph test — build one node per transaction, add an edge Ti → Tj for every conflict where Ti acts first; the schedule is conflict-serializable iff the graph has no cycle, and any topological order of the graph is a valid equivalent serial schedule.

(a)

All four rows match — the line \( 0.6x_1 + 0.6x_2 = 1 \) separates (1,1) from the other three points.

(b) Suppose weights \( w_1, w_2, b \) computed XOR. The four cases demand:

• (0,0) → 0: \( b < 0 \)
• (1,0) → 1: \( w_1 + b \geq 0 \)
• (0,1) → 1: \( w_2 + b \geq 0 \)
• (1,1) → 0: \( w_1 + w_2 + b < 0 \)

Add the middle two: \( w_1 + w_2 + 2b \geq 0 \), so \( w_1 + w_2 + b \geq -b \). Since \( b < 0 \), \( -b > 0 \), giving \( w_1 + w_2 + b > 0 \) — directly contradicting the fourth inequality. No weights exist: XOR's 1-points (1,0),(0,1) and 0-points (0,0),(1,1) sit on the diagonals of a square and no single straight line separates them (not linearly separable). This is why XOR needs a hidden layer — a multi-layer network.

(c) Forward pass: \( 0.1(0) + 0.6(1) - 0.2 = 0.4 \geq 0 \) → prediction \( \hat{y} = 1 \), but target t = 0 → error \( t - \hat{y} = -1 \). Update rule \( w_i \leftarrow w_i + \eta(t - \hat{y})x_i \), \( b \leftarrow b + \eta(t - \hat{y}) \):

• \( w_1 = 0.1 + 0.1(-1)(0) = \mathbf{0.1} \) (unchanged — its input was 0)
• \( w_2 = 0.6 + 0.1(-1)(1) = \mathbf{0.5} \)
• \( b = -0.2 + 0.1(-1) = \mathbf{-0.3} \)

The step pushes the boundary the right way ((0,1) now scores 0.5 − 0.3 = 0.2, still wrong but closer to negative). Repeated passes keep shrinking it, and the perceptron convergence theorem guarantees a correct separator is reached — AND, unlike XOR, is linearly separable.

(a) The V-model bends waterfall's straight line into a V: development phases go down the left arm, testing phases climb the right arm, and each test level is planned against its mirror phase while that phase is still running:

Key difference from waterfall: waterfall treats testing as one late phase after coding; the V-model makes verification a parallel activity — acceptance criteria are written with the requirements, unit test cases with the module design. Defects in the requirements are caught while writing their tests, not months later, and every artifact has a defined check against it. The phase discipline (documents, sign-offs, no phase overlap) stays the same as waterfall.

(b) The V-model. Reasons:

1. Requirements are stable and regulator-fixed — the model's main weakness (handling change) never bites, and its strength (rigor) pays fully.
2. Traceability: regulators (e.g. IEC 62304 for medical software) demand proof that every requirement maps to design, code, and a passed test — the V's phase-to-test pairing produces exactly that evidence chain.
3. Early test design reviews the requirements themselves: writing acceptance tests against "shock within 5 s of fibrillation detection" exposes vague or untestable requirements before any code exists — vital when a late defect is life-threatening.
4. (Also: complete documentation for audits, and validation at every level rather than one big late test.)

(c) Shared weakness: both assume the requirements are known, complete, and frozen up front; working software appears only at the very end, and feedback arrives too late to steer. A project with fast-changing or initially unclear requirements — a consumer app or startup product hunting for market fit — exposes this immediately: by delivery time the requirements have moved. Such projects need iterative/agile models that ship small increments and absorb change every cycle.