Output: 4 8 8

Step by step:

• p = a + 1 makes p point to a[1]. So *p = a[1] = 4.
• *(p + 2) means the element 2 positions after a[1], which is a[3] = 8.
• p[3] is the same as *(p + 3) = a[4] = 10, and *a = a[0] = 2. So p[3] - *a = 10 - 2 = 8.

Key rule: for an int*, adding 1 moves the pointer by one whole int, not one byte. Also p[i] and *(p + i) are exactly the same thing.

Place 1s at minterms 1, 3, 5, 7, 9 and X (don't care) at 6, 12, 13 on a 4-variable K-map (variables A, B, C, D; minterm number = ABCD in binary).

Group 1 (quad): minterms 1, 3, 5, 7. All have A = 0 and D = 1, while B and C change. This group gives \( A'D \).

Group 2 (quad): minterms 1, 5, 9, 13 (13 is a don't care, we use it for free). All have C = 0 and D = 1, while A and B change. This group gives \( C'D \).

Every real minterm is now covered: 1, 3, 5, 7 by group 1; 9 by group 2 (1 and 5 are covered twice, which is fine). Don't cares 6 and 12 are simply left unused.

Check: m9 = 1001: A'D = 0 but C'D = 1 ✓. m3 = 0011: A'D = 1 ✓. No 0-cell is inside any group, so the answer is correct and minimal (two quads, 4 literals).

(a) Each face has probability \( \frac{1}{6} \). Winnings W: faces 2, 4, 6 pay 2, 4, 6 taka; faces 1, 3, 5 pay 0.

(b) Expected winnings (2 taka) exactly equal the ticket price (2 taka), so the expected net gain is \( 2 - 2 = 0 \). The game is fair.

(c) At a 2.50 taka ticket, expected net gain = \( 2 - 2.50 = -0.50 \) taka per game. On average you lose 50 poysha every play, so a rational player should not play.

/28 means 28 network bits, so 32 − 28 = 4 host bits. Block size in the last octet = \( 2^4 = 16 \).

• (a) Mask: 28 ones → 255.255.255.240 (240 = 11110000).
• (b) Subnet address: subnets in the last octet go 0, 16, 32, 48, 64, 80, … Since 64 ≤ 77 < 80, the subnet is 172.16.5.64. (Same result by AND: 77 AND 240 = 64.)
• (c) Broadcast: next subnet − 1 = 80 − 1 → 172.16.5.79.
• (d) Usable range: first host = 172.16.5.65, last host = 172.16.5.78.
• (e) Usable hosts: \( 2^4 - 2 = 14 \) (subtract the network and broadcast addresses).

Output:

Circle area
I am Shape
I am Circle

• p->area(): area() is virtual, so the call uses dynamic binding (runtime dispatch through the vtable). The object really is a Circle, so Circle::area() runs → "Circle area".
• p->name(): name() is not virtual, so the call uses static binding — the compiler picks by the pointer's declared type, which is Shape*. So Shape::name() runs → "I am Shape".
• c.name(): called directly on a Circle object, so Circle::name() (which hides the base version) runs → "I am Circle".

One-line rule: virtual → decided at runtime by the object's real type; non-virtual → decided at compile time by the pointer's type.

(a) Build up from the base case:

• \( T(2) = 2T(1) + 2 = 2(1) + 2 = 4 \)
• \( T(4) = 2T(2) + 4 = 2(4) + 4 = 12 \)
• \( T(8) = 2T(4) + 8 = 2(12) + 8 = \mathbf{32} \)

(b) Expanding \( \log_2 n \) levels, each level costs n, plus n leaves of cost 1:

Check with n = 8: \( 8 \times 3 + 8 = 32 \) ✓. (Master theorem also gives it: a = 2, b = 2, f(n) = n = \( n^{\log_2 2} \) → case 2 → \( \Theta(n\log n) \).)

(c) Merge sort — two half-size recursive calls plus a linear merge.

A* always expands the open node with the smallest f = g + h.

1. Expand S (g = 0, f = 7). Children: A (g = 1, f = 1 + 6 = 7), B (g = 4, f = 4 + 4 = 8).
2. Expand A (f = 7, the smallest). Children: B via A (g = 1 + 2 = 3, f = 3 + 4 = 7 — better than the old g = 4, so update B), C via A (g = 1 + 5 = 6, f = 6 + 2 = 8). Open: B(f = 7), C(f = 8).
3. Expand B (g = 3, f = 7). Child: C via B (g = 3 + 2 = 5, f = 5 + 2 = 7 — better than g = 6, update C). Open: C(f = 7).
4. Expand C (g = 5, f = 7). Child: G (g = 5 + 3 = 8, f = 8 + 0 = 8). Open: G(f = 8).
5. Expand G — goal reached, stop.

Expansion order: S, A, B, C, G.

Path: S → A → B → C → G, following the recorded parents. Cost = 1 + 2 + 2 + 3 = 8.

This is optimal because h never overestimates the true remaining cost (admissible), e.g. true cost from B is 5 and h(B) = 4.

(a) 5 rows. CSE students are id 1 (Rahim) and id 3 (Salma). The join keeps one row per matching Enroll row: id 1 has 2 enrollments (DB, OS) and id 3 has 3 (AI, DB, OS). 2 + 3 = 5.

(b) 1 row. A LEFT JOIN keeps every student; students with no enrollment get NULLs on the Enroll side. Only id 4 (Jamal) never appears in Enroll, so e.sid IS NULL keeps exactly the row 'Jamal'.

(c) 2 rows. Group counts: DB → 3, OS → 2, AI → 1. HAVING keeps groups with count ≥ 2, so DB and OS survive → rows (DB, 3) and (OS, 2).

Claim: P(n): "n taka can be made with 4- and 5-taka stamps," for all n ≥ 12.

Base cases (we need 4 of them because the step goes back 4):

• P(12): 12 = 4 + 4 + 4 ✓
• P(13): 13 = 4 + 4 + 5 ✓
• P(14): 14 = 4 + 5 + 5 ✓
• P(15): 15 = 5 + 5 + 5 ✓

Inductive step: Let n ≥ 16, and assume (strong hypothesis) that P(k) is true for every k with 12 ≤ k < n. Since n ≥ 16, we have n − 4 ≥ 12, so n − 4 is inside the hypothesis range and P(n − 4) holds. Take the stamp combination for n − 4 and add one more 4-taka stamp. This forms exactly n taka, so P(n) is true.

Conclusion: By strong induction, P(n) holds for all n ≥ 12. ∎

Exam tip: state clearly why 4 base cases are needed — the step reaches back exactly 4, so 16 needs 12, 17 needs 13, 18 needs 14, 19 needs 15.

Need = Max − Allocation:

          Need
          A  B  C
   P1     3  1  1
   P2     1  2  0
   P3     5  1  1

Safety algorithm with Work = Available = (2, 2, 1):

1. P1 needs (3,1,1): 3 > 2 → cannot run. P2 needs (1,2,0) ≤ (2,2,1) ✓ → run P2, then Work = (2,2,1) + Allocation(P2) = (2+2, 2+0, 1+2) = (4, 2, 3).
2. P1 needs (3,1,1) ≤ (4,2,3) ✓ → run P1, then Work = (4+1, 2+2, 3+1) = (5, 4, 4).
3. P3 needs (5,1,1) ≤ (5,4,4) ✓ → run P3, then Work = (5+3, 4+1, 4+2) = (8, 5, 6) = total resources ✓.

All processes can finish, so the system is in a safe state with safe sequence ⟨P2, P1, P3⟩.

Sanity check: total allocation (1+2+3, 2+0+1, 1+2+2) = (6, 3, 5), and (6,3,5) + available (2,2,1) = (8,5,6) = total ✓.

Idea: the machine only needs to remember (count of 1s) mod 3. That needs exactly 3 states.

• q0 — count ≡ 0 (mod 3). Start state and the only accepting state.
• q1 — count ≡ 1 (mod 3).
• q2 — count ≡ 2 (mod 3).

Transition table:

Why correct: a 0 never changes the count of 1s, so every state loops to itself on 0. A 1 increases the count by one, so the state advances q0 → q1 → q2 → q0, which is exactly addition mod 3. The string is accepted iff the machine ends in q0, i.e. iff the count of 1s ≡ 0 (mod 3). The empty string is accepted (0 ones is divisible by 3), which is right.

(a) \( n = pq = 5 \times 11 = 55 \). \( \varphi(n) = (p-1)(q-1) = 4 \times 10 = 40 \).

(b) e = 3 is valid because \( \gcd(3, 40) = 1 \) (3 is prime and does not divide 40).

(c) We need \( d \) with \( 3d \equiv 1 \pmod{40} \). Try multiples: 3 × 27 = 81 = 2 × 40 + 1 ✓. So d = 27. (Extended Euclid gives the same: 40 = 13·3 + 1 → 1 = 40 − 13·3 → −13 ≡ 27 mod 40.)

(d) Ciphertext \( c = m^e \bmod n = 8^3 \bmod 55 \).

So the encrypted message is 17. (Decryption would compute \( 17^{27} \bmod 55 = 8 \), recovering m.)

(a) Each key goes left if smaller, right if larger:

          50
        /    \
      30      70
     /  \    /  \
   20    40 60   80

(b) Inorder (left, root, right): 20, 30, 40, 50, 60, 70, 80 — sorted, as always for a BST. Preorder (root, left, right): 50, 30, 20, 40, 70, 60, 80.

(c) Height = 2 (longest root-to-leaf path, e.g. 50 → 30 → 20, has 2 edges). The tree is perfectly balanced.

(d) Any fully sorted order, e.g. 20, 30, 40, 50, 60, 70, 80 — every new key goes right, producing a chain of height 6, which is the worst case (n − 1 edges).

(a) Lines = cache size / block size = \( \frac{64 \times 1024}{32} = \frac{65536}{32} = 2048 \) lines.

(b)

• Offset: selects a byte inside a 32-byte block → \( \log_2 32 = 5 \) bits.
• Index: selects one of 2048 lines → \( \log_2 2048 = 11 \) bits.
• Tag: the rest → 32 − 11 − 5 = 16 bits.

(c) Each line stores one tag: \( 2048 \times 16 = 32768 \) bits = 4 KB of tag storage.

Bank system → Waterfall (or V-model):

• Requirements are fixed by regulation, so the biggest weakness of waterfall (late requirement change) does not apply.
• Each phase produces the heavy documentation that auditors and regulators demand.
• Clear phase gates (requirements → design → implementation → testing) make sign-off and legal accountability easy.
• Correctness matters more than delivery speed; full upfront design and a dedicated testing phase reduce risk.

Startup app → Agile (e.g. Scrum):

• Requirements change every few weeks — agile welcomes change even late, while waterfall would need a costly restart.
• Short sprints deliver working software fast, so real user feedback arrives early and steers the product.
• A prioritized, re-orderable backlog lets the team drop bad ideas cheaply instead of finishing a full planned scope.
• Minimal documentation overhead suits a small fast team.

One-line summary: stable requirements + heavy compliance → waterfall; unstable requirements + need for fast feedback → agile.

(a) n % 10 takes the last digit and n / 10 removes it (integer division). So f computes the sum of the digits of n.

(b) Trace of f(4725):

f(4725) = 5 + f(472)
f(472)  = 2 + f(47)
f(47)   = 7 + f(4)
f(4)    = 4 + f(0)
f(0)    = 0

Adding back up: 4 + 0 = 4; 7 + 4 = 11; 2 + 11 = 13; 5 + 13 = 18.

(c) f(999) = 9 + 9 + 9 = 27.

(a) We need \( 2^k \geq 6 \). With k = 2, \( 2^2 = 4 \) — not enough. With k = 3, \( 2^3 = 8 \) ✓. Borrow 3 bits → new prefix /27 (mask 255.255.255.224).

(b) Subnets: \( 2^3 = 8 \) (we use 6, 2 spare). Host bits left: 32 − 27 = 5, so usable hosts = \( 2^5 - 2 = 30 \) per subnet.

(c) Block size = 256 / 8 = 32 in the last octet:

• Subnet 1: network 10.0.0.0/27, hosts .1–.30, broadcast 10.0.0.31.
• Subnet 2: network 10.0.0.32/27, hosts .33–.62, broadcast 10.0.0.63.

Number of flip-flops: we must count 0–5 (6 states). \( 2^2 = 4 < 6 \leq 2^3 = 8 \), so we need 3 JK flip-flops (outputs Q2 Q1 Q0, Q2 = MSB).

Circuit:

• Set J = K = 1 on all three flip-flops (toggle mode).
• Clock feeds FF0; Q0 clocks FF1; Q1 clocks FF2 (ripple connection) — by itself this is a MOD-8 counter.
• Connect Q2 and Q1 to a NAND gate, and the NAND output to the active-low CLEAR of all flip-flops.

How it works: the counter goes 000 → 001 → 010 → 011 → 100 → 101. On the next pulse it momentarily becomes 110 (decimal 6). Now Q2 = 1 and Q1 = 1, so the NAND output drops to 0 and immediately clears the counter to 000. So the visible sequence is 0, 1, 2, 3, 4, 5, 0, 1, … — six states, and Q2 gives a divide-by-6 output frequency.

Note: state 110 exists only for a few nanoseconds (a glitch). We decode 110 (not 101) because clearing must happen at the first unwanted state.

Let D = has disease, + = tests positive. Given: P(D) = 0.01, P(+|D) = 0.90, P(+|D') = 0.05, P(D') = 0.99.

Numerator: \( 0.90 \times 0.01 = 0.009 \).

Denominator: \( 0.009 + 0.05 \times 0.99 = 0.009 + 0.0495 = 0.0585 \).

Comment: even with a 90%-accurate test, a positive person has only about a 15% chance of being sick. The reason is the very low base rate (1%): among 10,000 people, ~90 true positives but ~495 false positives, so most positives are healthy. This is the classic base-rate effect.

Rule: push operands; for an operator, pop the top two (second pop is the LEFT operand), apply, push the result.

Result: 7.

Infix: \( (7 - 2 \times 3) \times (4 + 6 / 2) = 1 \times 7 = 7 \) ✓.

Structure: a PaymentStrategy interface; concrete strategies CardPayment, BkashPayment, CashOnDelivery; a context class Checkout that holds a strategy reference and delegates to it.

interface PaymentStrategy {
    void pay(double amount);
}

class BkashPayment implements PaymentStrategy {
    public void pay(double amount) {
        System.out.println("Paid " + amount + " via bKash");
    }
}

class Checkout {                    // context
    private PaymentStrategy strategy;
    public void setStrategy(PaymentStrategy s) { strategy = s; }
    public void payBill(double amount) { strategy.pay(amount); }
}

// usage
Checkout c = new Checkout();
c.setStrategy(new BkashPayment());
c.payBill(500.0);

Why better than if–else:

• Open–closed principle: adding a new method (say Nagad) means adding one new class — no existing code is edited or re-tested.
• Each algorithm sits in its own class, so the code is easier to test and reuse.
• The strategy can be swapped at runtime (user picks a method on the payment page).
• An if–else chain grows forever and mixes every payment rule into one method — high coupling, low cohesion.

(a) FIFO (evict the page that entered earliest):

FIFO faults = 9.

(b) LRU (evict the page unused for the longest time):

Key evictions: at ref 4, LRU evicts 1 (least recently used, since 2 was just hit); at ref 1 it evicts 3; at ref 5 it evicts 2; at ref 2 it evicts 4; at ref 3 it evicts 5; at ref 4 it evicts 1. LRU faults = 9.

(c) Here both give 9 faults out of 12 references — the counts happen to tie, but the eviction choices differ (e.g. at reference 4, FIFO evicts 1 because it is oldest, while LRU evicts 1 because it is least recently used; at reference 1 FIFO evicts 2 but LRU evicts 3). In general LRU usually performs equal or better because it uses recency information, and unlike FIFO it never suffers Belady's anomaly.

(a) FIRST sets:

• FIRST(A) = {a, ε} — from A → aA and A → ε.
• FIRST(B) = {b, c} — from B → bB and B → c.
• FIRST(S): S → AB. FIRST(A) without ε gives {a}; since A can be ε, we add FIRST(B). So FIRST(S) = {a, b, c}.

(b) FOLLOW sets:

• FOLLOW(S) = {$} (start symbol).
• FOLLOW(A): A is followed by B in S → AB, so add FIRST(B) = {b, c}. B is never ε, so nothing more. FOLLOW(A) = {b, c}.
• FOLLOW(B): B ends S → AB, so FOLLOW(B) = FOLLOW(S) = {$}.

(c) LL(1) check — for each nonterminal with multiple productions, the lookahead sets must not overlap:

• A: for A → aA choose on FIRST = {a}; for A → ε choose on FOLLOW(A) = {b, c}. {a} ∩ {b, c} = ∅ ✓
• B: FIRST(bB) = {b}, FIRST(c) = {c}. Disjoint ✓

No conflicts, no left recursion → the grammar is LL(1).

(a) By repeated squaring mod 23: \( 5^2 = 25 \equiv 2 \), \( 5^4 \equiv 2^2 = 4 \), \( 5^8 \equiv 4^2 = 16 \).

• Alice sends \( A = 5^6 = 5^4 \cdot 5^2 \equiv 4 \times 2 = \mathbf{8} \pmod{23} \).
• Bob sends \( B = 5^{15} = 5^8 \cdot 5^4 \cdot 5^2 \cdot 5^1 \equiv 16 \times 4 \times 2 \times 5 = 640 \). \( 640 - 27 \times 23 = 640 - 621 = \mathbf{19} \).

(b) Shared secret s:

• Alice computes \( B^a = 19^6 \bmod 23 \). Since \( 19 \equiv -4 \pmod{23} \), \( (-4)^6 = 4^6 = 4096 \). \( 4096 - 178 \times 23 = 4096 - 4094 = \mathbf{2} \).
• Bob computes \( A^b = 8^{15} = 2^{45} \bmod 23 \). By Fermat's little theorem \( 2^{22} \equiv 1 \), and in fact \( 2^{11} = 2048 = 89 \times 23 + 1 \equiv 1 \). So \( 2^{45} = (2^{11})^4 \cdot 2 \equiv \mathbf{2} \).

Both sides get s = 2 ✓ (they match because \( B^a = g^{ab} = A^b \)).

(c) The eavesdropper would need a from A = g^a mod p (or b from B). That is the discrete logarithm problem, which has no known efficient algorithm for large p (hundreds of digits). With tiny p = 23 it is easy — that is exactly why real systems use huge primes.

dp[i][w] = best value using the first i items within weight w. Recurrence: take max(skip, value + dp[i−1][w−weight]).

Key cells: row B, w = 5: max(30, 40 + dp[A][2] = 40 + 30) = 70. Row C, w = 5: max(70, 55 + dp[B][1] = 55 + 0) = 70. Row C, w = 4: max(40, 55 + 0) = 55.

Answer: maximum value = 70, choosing A + B (weight 2 + 3 = 5 ≤ 5).

Greedy fails: "highest value first" picks C (value 55, weight 4). Remaining capacity 1 fits nothing, total = 55 < 70. Greedy cannot see that two medium items beat one big item — that is why 0/1 knapsack needs DP.

(a) The 12 months are pigeonholes, the 25 students are pigeons. By the generalized pigeonhole principle, some month holds at least

Direct argument: if every month had at most 2 students, the class could have at most 12 × 2 = 24 students — but it has 25. Contradiction, so some month has ≥ 3. ∎

(b) Answer: 25.

• 25 works: shown in part (a).
• 24 does not: place exactly 2 students in each of the 12 months. That is a valid arrangement of 24 students where no month has 3. So 24 gives no guarantee.

General formula: to force k + 1 in one of n holes you need kn + 1 pigeons; here 2 × 12 + 1 = 25.

(a) Without pipelining, each instruction takes all 5 stages in sequence: 5 × 2 = 10 ns. Total = 100 × 10 = 1000 ns.

(b) With pipelining, the first instruction finishes after 5 cycles, then one instruction completes every cycle:

(c) Speedup = 1000 / 208 ≈ 4.81. It is below the ideal 5 because of the pipeline fill time: the first 4 cycles produce no completed instruction. As n → ∞ the speedup approaches k = 5. In real processors it drops further because of hazards (data, control, structural) that insert stalls — this question assumed none.

(a) (StudentID, CourseID) together determine every attribute: StudentID → StudentName, CourseID → CourseName, and the pair → Grade. Neither alone determines everything, so the candidate key is (StudentID, CourseID).

(b) 2NF forbids a non-prime attribute depending on part of a composite key. Here StudentName depends only on StudentID, and CourseName only on CourseID — both are partial dependencies. So R is in 1NF but not 2NF. (Symptoms: a student's name is repeated for every course — redundancy, and update/insert/delete anomalies.)

(c) Decompose one relation per dependency:

• Student(StudentID, StudentName) — key StudentID
• Course(CourseID, CourseName) — key CourseID
• Result(StudentID, CourseID, Grade) — key (StudentID, CourseID); StudentID and CourseID are foreign keys

Each relation now has only full, direct dependencies on its whole key — no partial and no transitive ones — so all three are in 3NF (in fact BCNF). Lossless: joining Result with Student on StudentID and with Course on CourseID rebuilds R exactly, because the join attributes are keys of Student and Course.

Step 1 — assignment (squared Euclidean distance is enough for comparing):

Clusters: {P1, P2} and {P3, P4}.

Step 2 — update centers (mean of each cluster):

Next iteration? Re-check with the new centers: P1: d² to C1′ = 0.25 vs to C2′ = 12.25 + 6.25 = 18.5 → stays. P2: 0.25 vs 6.25 + 6.25 = 12.5 → stays. P3: 6.25 + 4 = 10.25 vs 0.25 + 0.25 = 0.5 → stays. P4: 12.25 + 9 = 21.25 vs 0.25 + 0.25 = 0.5 → stays. No assignment changes, so K-means has converged after this one iteration.

The diagram is a system boundary box with ovals (use cases) inside and stick-figure actors outside, connected by lines:

• Customer — Browse Menu, Place Order, Track Order, Rate Order
• Restaurant — Accept Order, Update Menu
• Rider — Deliver Order, Update Delivery Status
• Admin — Manage Users, View Reports

            +-------------------------------------------+
Customer -- | (Browse Menu)   (Place Order)             |
            |                     | <<include>>        |
            |                     v                     |
            |                (Make Payment)             |
            |  (Track Order)  (Rate Order)              |
Restaurant--| (Accept Order)  (Update Menu)             |
Rider ------| (Deliver Order) (Update Delivery Status)  |
            |  (Place Order) <-- <<extend>> (Apply     |
Admin ------| (Manage Users)         Promo Code)        |
            +-------------------------------------------+

<<include>>: Place Order includes Make Payment — payment happens every time an order is placed, so it is mandatory shared behavior pulled out as its own use case.

<<extend>>: Apply Promo Code extends Place Order — it runs only sometimes (when the customer has a code), so it is optional behavior attached at an extension point.

Memory rule: include = always happens (base points to included); extend = optional extra (extension points to base).