Complexity আর dry-run — হাতে চালিয়ে উত্তর বের করার অনুশীলন

Θ(n²). i-এর জন্য ভেতরের লুপ n − i বার: n + (n − 1) + … + 1 = n(n + 1)/2. n = 10-এ ঠিক ৫৫. “ভেতরের লুপ ছোট হচ্ছে, তাই n log n” — ভুল; অর্ধেক i-এর জন্যও ভেতরে অন্তত n/2 কাজ, তাই অন্তত n²/4.

Θ(log n). k-তম iteration-এ i = 2^k; লুপ চলে যতক্ষণ 2^k < n, অর্থাৎ ⌈log₂ n⌉ বার (n ≥ 2). n = 1000-এ ১০ বার (1, 2, 4, …, 512). ভিত্তি 2 না হয়ে 3 হলেও (i *= 3) Θ(log n) — log-এর ভিত্তি শুধু ধ্রুবক গুণক বদলায়।

Θ(n). বাইরের লুপ log n বার, কিন্তু “log n × n = n log n” ভুল — ভেতরের কাজ প্রতিবার অর্ধেক: n + n/2 + n/4 + … < 2n (geometric series). n = 16-এ ঠিক ৩১. বড় পদটিই (প্রথমটি) যোগফলকে নিয়ন্ত্রণ করে।

(a) Θ(n), (b) Θ(n log n). (a)-তে কাজ 1 + 2 + 4 + … + 2^{⌊log n⌋} < 2n; n = 16-এ ৩১. (b)-তে বাইরের লুপের ⌊log₂ n⌋ + 1 বারের প্রতিটিতে পুরো n, তাই n(⌊log₂ n⌋ + 1); n = 16-এ ৮০. শিক্ষা: বাইরের লুপের সংখ্যা × ভেতরের সর্বোচ্চ কাজ দিয়ে শুধু ওপরের সীমা পাওয়া যায় — টাইট উত্তরের জন্য যোগ করুন।

Θ(n log n). i-এর জন্য ভেতরে ⌈log₂ i⌉ কাজ, মোট ≈ Σ log i = log(n!). ওপরের সীমা: প্রতিটি পদ ≤ log n, তাই ≤ n log n. নিচের সীমা: শেষ অর্ধেক (i ≥ n/2) প্রতিটির কাজ ≥ log(n/2), তাই ≥ (n/2) log(n/2) = Ω(n log n). n = 1024-এ ৯২১৭ (n log₂ n = 10240-এর কাছাকাছি)।

Θ(n log n) — ভাগ ২-এর stepper. মোট Σ ⌊n/i⌋ ≈ n · H_n ≈ n ln n. n = 8-এ ২০, n = 1024-এ ৭২৬২ (n ln n ≈ 7098). এই ছাঁচে “প্রতিটি সংখ্যার সব গুণিতক ঘোরা” কাজ হয় — যেমন 1 থেকে n পর্যন্ত প্রতিটি সংখ্যার divisor-এর সংখ্যা একসাথে বের করা।

Θ(n³). প্রতিটি কাজ একটি ত্রয়ী k < j < i, যেখানে তিনটিই 0..n−1 থেকে আলাদা — এমন ত্রয়ী ঠিক C(n, 3) = n(n − 1)(n − 2)/6টি। ধ্রুবক 1/6 ছোট, কিন্তু বৃদ্ধির হার ঘন। (n = 1024-এ ১৭,৮৪,৩৩,০২৪ বার — গুনে মেলানো।)

Θ(√n). শর্ত i ≤ √n, তাই ⌊√n⌋ বার; n = 1024-এ ৩২. Trial division দিয়ে মৌলিক যাচাই (পর্ব ৬২) এই ছাঁচের। সাবধান: n-এর bit সংখ্যা b হলে √n = 2^b/2 — ইনপুটের দৈর্ঘ্যের তুলনায় exponential.

Θ(log log n). k-তম iteration-এ i = 2^2k. লুপ চলে যতক্ষণ 2^2k ≤ n, অর্থাৎ 2^k ≤ log₂ n, k ≤ log₂ log₂ n. n = 10⁶-এ মাত্র ৫ বার: 2, 4, 16, 256, 65536. int নিলে 65536 × 65536-এ overflow হতো — তাই long long.

Θ(n) — two pointer-এর amortized যুক্তি। একটি নির্দিষ্ট i-এর জন্য while অনেকবার চলতে পারে, কিন্তু j কখনো কমে না আর n ছাড়ায় না — তাই পুরো প্রোগ্রামে while-এর শরীর সব মিলিয়ে সর্বোচ্চ n বার। মোট ≤ n (বাইরের) + n (ভেতরের) = 2n. লুপের ভেতরে লুপ মানেই n² নয়; প্রশ্ন হলো ভেতরের ভ্যারিয়েবল প্রতিবার শূন্য থেকে শুরু হয় কি না।

Worst case Θ(n²), best case Θ(n). j প্রতিটি i-এ আবার 0 থেকে শুরু হয়, তাই amortized যুক্তি খাটে না। a ছোট থেকে বড় সাজানো হলে while i বার চলে: 0 + 1 + … + (n − 1) = n(n − 1)/2. a বড় থেকে ছোট সাজানো হলে প্রথম তুলনাতেই থামে — Θ(n). উত্তরে কোন case বলছেন, লিখুন।

Θ(n) worst case. প্রতিটি iteration-এ r − l ঠিক ১ কমে (বা লুপ থামে); শুরুতে r − l = n − 1, তাই সর্বোচ্চ n − 1 বার। এটিই সাজানো অ্যারেতে two-sum-এর রৈখিক সমাধান (পর্ব ১৬); ট-০৫-এ এটি হাতে চালাবেন।

s = s + 'a': Θ(n²); s += 'a': Θ(n) মোট (প্রতি কাজে amortized O(1)). s + 'a' একটি নতুন string বানায় আর পুরোনো i টি অক্ষর কপি করে: 1 + 2 + … + n = n(n + 1)/2 অক্ষর কপি। += জায়গায় যোগ করে, দরকারে capacity দ্বিগুণ করে — ঠিক dynamic array-র মতো (ক-২৪). Java আর Python-এ string immutable (পর্ব ১১), তাই লুপে জোড়া লাগাতে StringBuilder বা "".join(...). CPython কখনো কখনো ভেতরের একটি অপ্টিমাইজেশনে s = s + 'a' দ্রুত করে ফেলে, কিন্তু ভাষা সেই নিশ্চয়তা দেয় না।

Θ(n log log n). ভেতরের লুপ শুধু মৌলিক i-এর জন্য চলে, প্রায় n/i বার। মোট ≈ n · Σ_{p ≤ √n} 1/p, আর মৌলিকের উল্টোগুলোর যোগফল ≈ ln ln n (Mertens-এর উপপাদ্য)। তাই n log log n — বাস্তবে প্রায় রৈখিক। n = 10⁶-এ কাটাকাটি ২১,২২,০৪৮ বার, আর n ln ln n প্রায় ২৬ লাখ. if (!comp[i]) বাদ দিলে প্রতিটি i-এর জন্য চলত — তখন harmonic-এর মতো Θ(n log n)-এর কাছাকাছি।

f: সময় Θ(n), জায়গা Θ(n). bs: সময় Θ(log n), জায়গা Θ(log n). f-এর recurrence T(n) = T(n − 1) + O(1), আর একসাথে n টি frame stack-এ থাকে। bs-এর T(n) = T(n/2) + O(1). bs হলো tail recursion (রিকার্সিভ ডাকটিই শেষ কাজ), কিন্তু f নয় — ডাক ফেরার পর + 1 করতে হয়। C++ compiler অপ্টিমাইজেশনে bs-কে loop বানাতে পারে, কিন্তু ভাষা তার নিশ্চয়তা দেয় না — পরীক্ষায় stack-এর জায়গা গুনে লিখুন। খেয়াল করুন, vector reference-এ পাঠানো হয়েছে; মান হিসেবে পাঠালে প্রতিটি ডাকে Θ(n) কপি হতো, আর bs হয়ে যেত Θ(n log n).

সময় Θ(φⁿ), φ = (1 + √5)/2 ≈ 1.618; জায়গা Θ(n). কলের সংখ্যা C(n) = 1 + C(n − 1) + C(n − 2), C(0) = C(1) = 1 — সমাধান C(n) = 2F(n + 1) − 1, যেখানে F হলো Fibonacci সংখ্যা। fib(5)-এ ১৫টি, fib(10)-এ ১৭৭টি কল (গুনে মেলানো)। O(2ⁿ) সত্য কিন্তু টাইট নয়। Stack-এ একসাথে সর্বোচ্চ n টি frame (fib(n) → fib(n−1) → … → fib(1)), তাই জায়গা Θ(n). Memoization দিলে সময় Θ(n) — পর্ব ৫২.

Θ(n log n). T(n) = 2T(n/2) + Θ(n): a = 2, b = 2, d = 1, a = b^d → master theorem-এর case 2. গাছে log₂ n স্তর, প্রতিটিতে মোট n — merge sort-এর হুবহু ছাঁচ (পর্ব ২১)। জায়গা: stack-এ Θ(log n) frame.

Θ(n). T(n) = 2T(n/2) + Θ(1): a = 2 > b^d = 2⁰ = 1 → case 1, Θ(n^{log₂ 2}) = Θ(n). গাছে মোট node ≈ 2n − 1, প্রতিটিতে O(1). অনেকে “ভাগ করে জয় = n log n” মুখস্থ বলেন — ভুল; প্রতি স্তরের কাজই ঠিক করে। Binary tree-র সব node ঘোরা (পর্ব ২৬) এই ছাঁচ।

প্রতিটিতে a আর b^d তুলনা করুন:

• (a) Θ(n²): 4 > 2¹, n^{log₂ 4} = n². (n = 2²⁰-এ T(n)/n² → 2, গুনে মেলানো।)
• (b) Θ(n^{log₂ 3}) ≈ Θ(n^1.585): 3 > 2 — Karatsuba-র গুণ (পর্ব ৪৯)।
• (c) Θ(n^{log₂ 7}) ≈ Θ(n^2.807): 7 > 2² = 4 — Strassen-এর matrix গুণ।
• (d) Θ(√n log n): a = 2, b^d = 4^1/2 = 2, সমান → case 2.
• (e) Θ(n): 1 < 2¹ → case 3 (regularity শর্ত: f(n/2) = n/2 ≤ c · n, c = 1/2 — খাটে)। গড় হিসেবে quickselect-এর ছাঁচ (পর্ব ২২)।

Θ(n log² n). ফাঁদ: n log n “n-এর চেয়ে বড়”, তাই অনেকে case 3 ধরে Θ(n log n) বলেন। কিন্তু case 3-এ f(n)-কে n^{log_b a} = n-এর চেয়ে polynomially বড় হতে হয় (n^1+ε); log n কোনো n^ε-এর চেয়ে ধীরে বাড়ে। তিন-case-এর মূল রূপ এখানে খাটে না। Recursion tree: স্তর i-তে 2ⁱ টি node, প্রতিটির কাজ (n/2ⁱ) log(n/2ⁱ), স্তরের মোট n(log n − i). যোগ করলে n · (log n + (log n − 1) + … + 1) = Θ(n log² n). সম্প্রসারিত case 2 (f(n) = Θ(n^{log_b a} log^k n) হলে Θ(n^{log_b a} log^k+1 n)) একই উত্তর দেয়।

(a) Θ(n²), (b) Θ(2ⁿ) (ঠিক 2ⁿ − 1). Master theorem এখানে খাটে না — আকার ভাগ হয় না, এক কমে। (a) খুলে লিখুন: n + (n − 1) + … + 1 = n(n + 1)/2 — সাজানো ইনপুটে শেষ উপাদানকে pivot ধরা quick sort-এর worst case (পর্ব ২২)। (b) হলো Tower of Hanoi-র চাল (পর্ব ০৭): প্রতিটি স্তরে কল দ্বিগুণ।

Θ(n log n). Master theorem-এর আকারে নেই (দুটি আলাদা আকার)। Recursion tree: প্রতিটি পূর্ণ স্তরের মোট আকার n/3 + 2n/3 = n, তাই প্রতি স্তরে ≤ n কাজ। সবচেয়ে লম্বা পথ (প্রতিবার 2/3) log_3/2 n স্তর, সবচেয়ে ছোট পথ (প্রতিবার 1/3) log₃ n স্তর — প্রথম log₃ n স্তর পুরো ভরা। তাই n log₃ n ≤ T(n) ≤ n log_3/2 n (ধ্রুবক বাদে) — দুই দিকেই Θ(n log n). শিক্ষা: quick sort-এ pivot সবসময় ১:২ অনুপাতে ভাগ করলেও n log n থাকে।

Θ(log n · log log n). Change of variables (পর্ব ০৮): m = log₂ n ধরুন, তাহলে √n = 2^m/2. S(m) = T(2^m) লিখলে S(m) = 2S(m/2) + m — ক-১৭-এর মতো, Θ(m log m). m = log n বসিয়ে Θ(log n log log n).

(a) মোট Θ(n), প্রতি push amortized O(1); (b) মোট Θ(n²), প্রতি push amortized Θ(n). (a)-তে কপি হয় 1 + 2 + 4 + … (n-এর চেয়ে ছোট সবচেয়ে বড় ২-এর ঘাত পর্যন্ত) < 2n — capacity 1 থেকে শুরু করলে n = 2¹⁶-এ ঠিক ৬৫,৫৩৫টি কপি। (b)-তে কপি 10 + 20 + 30 + … ≈ n²/20 — গুনে অনুপাত 0.05-এ স্থির। একটি একক push-এর worst case দুটিতেই Θ(n); amortized মানে “ধারার মোট ÷ n”, গড়-case (সম্ভাবনা) নয়। C++-এর std::vector আর Python-এর list গুণ করে বাড়ে, যোগ করে নয়।

মোট Θ(n), প্রতি increment amortized O(1) — যদিও একটি increment (যেমন 0111 → 1000) Θ(log n) bit উল্টাতে পারে। Aggregate যুক্তি: bit 0 প্রতিবার উল্টায় (n বার), bit 1 প্রতি দুবারে একবার (n/2), bit 2 প্রতি চারবারে (n/4)… মোট < 2n. n = 2¹⁶-এ উল্টানো bit ঠিক 2n − 1 = ১,৩১,০৭১.

(a) Θ(V²), (b) Θ(V + E), (c) O((V + E) log V), (d) Θ(V³). (a)-তে প্রতিটি বের করা vertex-এর জন্য matrix-এর পুরো সারি (V টি ঘর) দেখতে হয়, edge কম হলেও। (b)-তে প্রতিটি vertex একবার কিউতে, প্রতিটি edge (undirected হলে দুই দিক থেকে) একবার দেখা। (c)-তে প্রতিটি relaxation একটি O(log V) heap কাজ (পর্ব ৪৩)। (d)-তে তিনটি nested loop, প্রতিটি V বার (পর্ব ৪৪)। গ্রাফের প্রশ্নে সবসময় V আর E আলাদা করে লিখুন — শুধু “n” লিখলে উত্তর অস্পষ্ট।

মোট ১৫টি কল; fib(2) ৩ বার; সর্বোচ্চ গভীরতা ৫টি frame. গণনা: fib(5) ১, fib(4) ১, fib(3) ২, fib(2) ৩, fib(1) ৫, fib(0) ৩ — যোগ ১৫ = 2F(6) − 1. সবচেয়ে গভীর পথ fib(5) → fib(4) → fib(3) → fib(2) → fib(1). খাতায় call tree আঁকুন: প্রতিটি node-এ n লিখে বাঁয়ে n − 1, ডানে n − 2.

উত্তর 3. 13 = 1101₂. সারিগুলো (e, সেই সময়ের b, কাজের পর r):

e = 13 (odd):  r = 1*3 mod 7 = 3     b -> 9 mod 7 = 2
e = 6  (even): r = 3                 b -> 4
e = 3  (odd):  r = 3*4 mod 7 = 5     b -> 16 mod 7 = 2
e = 1  (odd):  r = 5*2 mod 7 = 3     b -> 4,  e -> 0, stop

চেক: 3⁶ = 729 = 7 · 104 + 1, তাই 3¹² ≡ 1 আর 3¹³ ≡ 3 (mod 7) ✓. গুণ মাত্র ৪ ধাপে — Θ(log e).

উত্তর 7. 5 → [5]; 3 → [5, 3]; 2 → [5, 3, 2]; * → 3·2: [5, 6]; + → 5+6: [11]; 4 → [11, 4]; − → 11−4: [7]. মনে রাখুন বিয়োগ আর ভাগে ক্রম: প্রথমে pop করা হয় ডান operand (b), তারপর বাঁ (a), ফল a − b. উল্টালে −7 আসে — প্রচলিত ভুল।

(a) P = [0, 3, 4, 8, 9, 14, 23, 25]; যোগফল = P[6] − P[2] = 23 − 4 = 19 (4 + 1 + 5 + 9 ✓). সীমা মনে রাখুন: a[l..r] = P[r+1] − P[l]. (b) d[1] += 5, d[4] −= 5, d[2] += 2, d[6] −= 2 → d = [0, 5, 2, 0, −5, 0] (d[6] অ্যারের বাইরে, বাদ). Prefix যোগ করে [0, 5, 7, 7, 2, 2] (পর্ব ১৭)।

(0, 5, 16) বেশি → r−−; (0, 4, 12) কম → l++; (1, 4, 13) কম → l++; (2, 4, 15) পাওয়া গেল. জোড়া 4 + 11, index 2 আর 4; চার ধাপে।

পাস ১: [3, 6, 2, 5, 1, 8] (৪ swap); পাস ২: [3, 2, 5, 1, 6, 8] (৩ swap); পাস ৩: [2, 3, 1, 5, 6, 8]; পাস ৪: [2, 1, 3, 5, 6, 8]; পাস ৫: [1, 2, 3, 5, 6, 8]. মোট ৫টি পাস (n − 1 = ৫, শেষ পাসেও swap হয়েছে বলে আগে থামেনি), ১১টি swap = inversion-এর সংখ্যা ✓.

[2, 3, 6, 8, 5, 1] — ভাগ ১-এর stepper-এর চতুর্থ সারি। বাঁয়ের চারটি ঘর সাজানো, কিন্তু চূড়ান্ত নয় (1 পরে এসে সবাইকে ঠেলবে)। “পাস” শব্দটির মানে নিয়ে সন্দেহ হলে উত্তরে লিখুন “i = 1 থেকে গুনে”.

পাস ১: 1 আর 6 বদল → [1, 3, 8, 2, 5, 6]; পাস ২: বাকিদের সবচেয়ে ছোট 2, 3-এর সাথে বদল → [1, 2, 8, 3, 5, 6]. তিন সর্টের মাঝপথের অবস্থা আলাদা চেনা যায়: bubble-এ ডানে বড়গুলো চূড়ান্ত, selection-এ বাঁয়ে ছোটগুলো চূড়ান্ত, insertion-এ বাঁ অংশ সাজানো কিন্তু চূড়ান্ত নয়।

(a) (0, 9, 4) → B[4] = 16 < 23, lo = 5; (5, 9, 7) → 56 > 23, hi = 6; (5, 6, 5) → 23 পাওয়া গেল, index 5, ৩টি তুলনা-ধাপ. (b) একই প্রথম তিন ধাপ (23 < 40, lo = 6); (6, 6, 6) → 38 < 40, lo = 7; এখন lo = 7 > hi = 6, থামুন — পাওয়া যায়নি, ৪ ধাপ. থামার সময় lo = 7 হলো 40 ঢোকানোর জায়গা (প্রথম ≥ 40 উপাদান 56-এর index) — lower_bound-এর উত্তর।

প্রথম ভাগ [0, 3) আর [3, 7) — বাঁয়ে ৩টি, ডানে ৪টি। Merge-এর ক্রম:

1. [27] + [43]          -> [27, 43]                    1 comparison
2. [38] + [27, 43]      -> [27, 38, 43]                2
3. [3] + [9]            -> [3, 9]                      1
4. [82] + [10]          -> [10, 82]                    1
5. [3, 9] + [10, 82]    -> [3, 9, 10, 82]              2
6. [27, 38, 43] + [3, 9, 10, 82] -> [3, 9, 10, 27, 38, 43, 82]   6

শেষ merge-এ ৬টি তুলনা (বাঁয়ের তিনটি শেষ হওয়ার পর 82 তুলনা ছাড়াই যায়)। মোট ১৩টি। “বাঁ অর্ধেকে বেশি” নিয়ম নিলে ক্রম বদলাত — তাই mid-এর সূত্র উত্তরে লিখুন।

(a) pivot 6. j চলার সময় ≤ 6 পাওয়া যায় 2, 4, 3 — তারা i = 0, 1, 2-তে আসে: [2, 7, 9, 4, 3, 8, 6] → [2, 4, 9, 7, 3, 8, 6] → [2, 4, 3, 7, 9, 8, 6]; শেষে a[3] ↔ pivot: [2, 4, 3, 6, 9, 8, 7], index 3 — pivot নিজের চূড়ান্ত জায়গায়।

(b) pivot 5. প্রথম জোড়া: i থামে index 0-তে (5 ≥ 5), j থামে index 6-এ (1 ≤ 5) → swap: [1, 3, 8, 4, 2, 7, 5, 6]. পরের জোড়া: i = 2 (8), j = 4 (2) → swap: [1, 3, 2, 4, 8, 7, 5, 6]. তারপর j = 3, i = 4, i ≥ j — ফেরত j = 3, অ্যারে [1, 3, 2, 4, 8, 7, 5, 6]. সাবধান: Hoare-এ pivot (5) index 3-এ বসে না! শুধু নিশ্চয়তা: a[0..3] ≤ 5 ≤ a[4..7]. পরের রিকার্শন [0..3] আর [4..7]-এ — Lomuto-র মতো p − 1 আর p + 1 নয়।

(a) [10] → [4, 10] → [4, 10, 15] → [2, 4, 15, 10] → [2, 4, 15, 10, 8] → [2, 4, 15, 10, 8, 20] → [1, 4, 2, 10, 8, 20, 15] (1 index 6 থেকে 2-এ, তারপর 0-তে)। Extract 1: 15 root-এ, ছোট সন্তান 2-এর সাথে বদল → [2, 4, 15, 10, 8, 20]. Extract 2: 20 root-এ → 4-এর সাথে → 8-এর সাথে → [4, 8, 15, 10, 20].

(b) i = 3 থেকে 0 পর্যন্ত sift-down: i = 3 (1 ↔ 7) → [3, 9, 2, 7, 4, 5, 8, 1]; i = 2 (2 ↔ 8) → [3, 9, 8, 7, 4, 5, 2, 1]; i = 1 (9 ঠিক আছে); i = 0 (3 ↔ 9, তারপর 3 ↔ 7) → [9, 7, 8, 3, 4, 5, 2, 1]. চেক: প্রতিটি a[i] ≥ a[2i+1], a[2i+2] ✓. একে একে insert করলে অন্য heap আসতে পারে — প্রশ্ন কোন পদ্ধতি চাইছে, দেখে নিন।

একক অঙ্ক: [170, 90, 802, 2, 24, 45, 75, 66]. দশক: [802, 2, 24, 45, 66, 170, 75, 90]. শতক: [2, 24, 45, 66, 75, 90, 170, 802]. দ্বিতীয় পাসে 802 আর 2 দুটির দশকই 0 — stable বলে আগের ক্রম (802 আগে) থাকে; একই পাসে 170 আর 75 (দুটির দশকই 7)-ও তাই। Stable না হলে আগের পাসের কাজ নষ্ট হয় (পর্ব ২৪)।

            50
         /      \
       30        70
      /  \      /  \
    20    40   60   80
         /  \    \
       35    45   65

(a) Preorder: 50 30 20 40 35 45 70 60 65 80. Inorder: 20 30 35 40 45 50 60 65 70 80 (সাজানো — চেক ✓). Postorder: 20 35 45 40 30 65 60 80 70 50. Level order: 50 30 70 20 40 60 80 35 45 65. উচ্চতা 3 (যেমন 50 → 30 → 40 → 35).

(b) 30-এর দুই সন্তান; successor = ডান subtree-র সবচেয়ে ছোট = 35 (leaf). 35 ওপরে আসে: preorder 50 35 20 40 45 70 60 65 80. এবার 50: successor = 60 (70-এর বাঁয়ে, নিজের বাঁ সন্তান নেই)। 60 root-এ কপি, আর পুরোনো 60-এর জায়গায় তার একমাত্র সন্তান 65. শেষ preorder: 60 35 20 40 45 70 65 80. Predecessor নিয়ম নিলে অন্য উত্তর আসত — প্রশ্নে নিয়ম না থাকলে নিজে লিখে দিন।

2 5 6 4 10 14 12 8. Preorder-এর প্রথমটি root (8); inorder-এ 8-এর বাঁয়ে {2, 4, 5, 6} বাঁ subtree, ডানে {10, 12, 14}. বাঁ অংশের preorder 4 2 6 5 → root 4, বাঁয়ে 2, ডানে {5, 6} যার root 6 আর 5 তার বাঁ সন্তান। ডান অংশ 12 (10, 14). শুধু preorder আর postorder দিলে tree অনন্য হয় না (যেমন একটি সন্তান বাঁয়ে না ডানে, বোঝা যায় না) — inorder লাগে।

(a) 30 ঢোকার পর 10-এ RR (বাঁয়ে ঘোরানো) → 20(10, 30). 50 ঢোকার পর 30-এ RR → 20(10, 40(30, 50)). 25 যায় 20 → 40 → 30-এর বাঁয়ে; এখন 20-এর balance factor −2, আর ডান সন্তান 40-এর +1 — RL: আগে 40-এ ডানে ঘোরানো, তারপর 20-এ বাঁয়ে। শেষ preorder 30 20 10 25 40 50.

        30
       /  \
     20    40
    /  \     \
  10    25    50

(b) 10-এর পর 40-এ LL → 20(10, 40). 30-এর পর 40-এ LR (25 বাঁ সন্তান, তার ডানে 30) → 20(10, 30(25, 40)). 22-এর পর 20-এ RL → 25(20(10, 22), 30(—, 40)). 50-এর পর 30-এ RR → 40(30, 50). শেষ preorder 25 20 10 22 40 30 50. নিয়ম: নতুন node থেকে ওপরে উঠে প্রথম ভারসাম্যহীন node-এ rotation, আর সেখান থেকে নতুন node কোন দিকে-কোন দিকে গেছে, তা-ই নাম (পর্ব ২৮)।

25, 36, 14, 47, 3, 58 — ছয়টিরই h = 3! তারা 3, 4, 5, 6, 7, 8 দখল করে (probe ১, ২, ৩, ৪, ৫, ৬)। 9 → ঘর 9 (১ probe), 20 → h = 9, ভরা, ঘর 10 (২ probe).

index: 0  1  2  3   4   5   6   7  8   9  10
key  : -  -  -  25  36  14  47  3  58  9  20

(b) মোট probe ১ + ২ + ৩ + ৪ + ৫ + ৬ + ১ + ২ = ২৪. (c) 69 mod 11 = 3; ঘর 3 থেকে 10 পর্যন্ত আটটি ভরা, তারপর ঘর 0 খালি — ৯টি probe. এটিই primary clustering: একটি লম্বা ভরা ব্লক, যার যেকোনো জায়গায় পড়া key-কে পুরো ব্লক হাঁটতে হয়।

প্রথম চারটি union-এ চারটি জোড়া: 1 → 0, 3 → 2, 5 → 4, 7 → 6, প্রতিটি root-এর rank 1. union(1,3): root 0 আর 2, rank সমান → 2 → 0, rank[0] = 2. union(5,7): 6 → 4, rank[4] = 2. union(3,7): find(3) হাঁটে 3 → 2 → 0 আর compress করে p[3] = 0; find(7) হাঁটে 7 → 6 → 4, p[7] = 4. rank সমান (2, 2) → 4 → 0, rank[0] = 3.

i     : 0  1  2  3  4  5  6  7
parent: 0  0  0  0  0  4  4  4
rank  : 3  0  1  0  2  0  1  0

find(7): 7 → 4 → 0; compression-এ p[7] = 0 (p[4] আগেই 0). অন্য কারও parent বদলায় না — compression শুধু হাঁটা পথের node ছোঁয়। লক্ষ করুন, rank[2] = 1 রয়ে গেছে যদিও 2 এখন root নয়; compression rank কমায় না।

node : 1[0,5]=24  2[0,2]=8  3[3,5]=16  4[0,1]=7  5[2,2]=1  6[3,4]=13
       7[5,5]=3   8[0,0]=2  9[1,1]=5   12[3,3]=4  13[4,4]=9   (10, 11 unused)

(b) leaf থেকে root পর্যন্ত একটি পথ: t[5] = 6, t[2] = 13, t[1] = 29 — log n-এর মতো তিনটি node. (c) [1, 4] ভাঙে node 9 ([1,1] = 5), node 5 ([2,2] = 6), node 6 ([3,4] = 13) — যোগফল 24. n ২-এর ঘাত না হলে কিছু index (এখানে 10, 11) ফাঁকা থাকে — তাই অ্যারের আকার 4n নেওয়া হয় (পর্ব ৩৪)।

(a) t[i] = a[i − lowbit(i) + 1..i]-এর যোগফল: [3, 5, −1, 10, 5, 9, −3, 19] (যেমন t[4] = 3 + 2 − 1 + 6 = 10, t[6] = 5 + 4 = 9, t[8] = সব = 19). (b) i = 3 → 4 → 8 (প্রতিবার lowbit যোগ): t = [3, 5, 1, 12, 5, 9, −3, 21]. (c) 7 → 6 → 4 → 0 (প্রতিবার lowbit বাদ): t[7] + t[6] + t[4] = −3 + 9 + 12 = 18. চেক: নতুন a[1..7] = 3 + 2 + 1 + 6 + 5 + 4 − 3 = 18 ✓.

(a) ক্রম 0 1 2 3 4 5 6. কিউ: 0 বের করার পর [1, 2]; 1 → [2, 3]; 2 → [3, 4]; 3 → [4, 5]; 4 → [5] (5 আগেই দেখা); 5 → [6]; 6 → []. dist = [0, 1, 1, 2, 2, 3, 4], parent = [−, 0, 0, 1, 2, 3, 5]. 3-এর parent 1, 2 নয় — কারণ 1 আগে কিউ থেকে বের হয়ে 3-কে আবিষ্কার করে।

(b) discovery: 0 1 3 2 4 5 6; finish: 6 5 4 2 3 1 0. সময় (d/f): 0: 1/14, 1: 2/13, 2: 4/11, 3: 3/12, 4: 5/10, 5: 6/9, 6: 7/8. চেক: প্রতিটি vertex-এর [d, f] হয় অন্যটির ভেতরে, নয়তো আলাদা (parenthesis theorem, পর্ব ৪১)।

(c) 0 2 4 5 6 3 1 — recursive DFS-এর মতো নয়! stack-এর ওপরে থাকে শেষে push করা, অর্থাৎ সবচেয়ে বড় প্রতিবেশী। recursive DFS-এর ক্রম পেতে প্রতিবেশী উল্টো ক্রমে push করুন। পরীক্ষায় “DFS” বললে সাধারণত recursive রূপ বোঝায়; stack রূপে লিখলে নিয়মটি স্পষ্ট লিখুন।

Settle ক্রম 0, 2, 1, 3, 4, 5; dist [0, 5, 2, 6, 7, 10]. ওজন −3 হলে আসল সবচেয়ে ছোট দূরত্ব dist[3] = 2 + (−3) = −1, dist[5] = 3. এই গ্রাফে Dijkstra-ও (lazy রূপে) ঠিক উত্তর দেয়, কারণ 2 settle হওয়ার সময়েই 3 আপডেট হয়ে যায় — কিন্তু এটা কাকতালীয়। Negative edge থাকলে “বের হওয়া মানেই চূড়ান্ত” invariant ভেঙে যায়, আর অন্য গ্রাফে ভুল আসে; তখন নিয়ম হলো Bellman-Ford (পর্ব ৪৪)। পরীক্ষায় “Dijkstra negative edge-এ কেন ব্যর্থ” প্রশ্নে এমন একটি ছোট পাল্টা-উদাহরণ নিজে বানিয়ে দেখানোই সেরা উত্তর।

In-degree: 0:1, 1:0, 2:0, 3:2, 4:2, 5:3, 6:1. প্রস্তুত {1, 2}. বের 1 → 3:1, 4:1 → {2}. বের 2 → 4:0, 6:0 → {4, 6}. বের 4 → 5:2, 0:0 → {0, 6}. বের 0 → 3:0 → {3, 6}. বের 3 → 5:1 → {6}. বের 6 → 5:0 → {5}. বের 5. ক্রম 1 2 4 0 3 6 5 — এটি lexicographically সবচেয়ে ছোট topological order. চেক: প্রতিটি edge u→v-তে u আগে ✓ (4→0-তে 4 আগে). সাধারণ কিউ দিলে ক্রম 1 2 4 6 0 3 5 হতো।

1-2 (1) take     1-3 (2) take     0-2 (3) take
0-1 (4) skip: 0 and 1 already joined (cycle 0-2-1)
3-4 (5) take     2-3 (6) skip     4-5 (7) take   -> 5 edges, stop
3-5 (8), 2-4 (9): not needed

MST-র ওজন 1 + 2 + 3 + 5 + 7 = 18. V − 1 = ৫টি edge হলেই থামা যায়। সব ওজন আলাদা বলে MST অনন্য; সমান ওজন থাকলে একাধিক সঠিক MST হতে পারে, কিন্তু মোট ওজন একই (পর্ব ৪৫)।

k = 1-এ শুধু সারি 1 আর কলাম 1 দিয়ে ছোট পথ: d[i][j] = min(d[i][j], d[i][1] + d[1][j]). বদলায় তিনটি ঘর: d[2][4] = 8 + 7 = 15, d[3][2] = 5 + 3 = 8, d[4][2] = 2 + 3 = 5.

after k = 1           final (k = 4)
   0   3   ∞   7         0   3   5   6
   8   0   2  15         5   0   2   3
   5   8   0   1         3   6   0   1
   2   5   ∞   0         2   5   7   0

কৌশল: k-তম ধাপে সারি k আর কলাম k কখনো বদলায় না (d[k][k] = 0), তাই খাতায় সেগুলো আগে কপি করে বাকি ঘরগুলো মেলান। d[4][3] k = 1-এ ∞ থাকে (d[1][3] = ∞), k = 2-এ 4 → 1 → 2 → 3 = 7 হয়।

সবসময় সবচেয়ে ছোট দুটি জোড়া: 2 + 3 = 5 (C, B); 5 + 5 = 10 (CB, D); 7 + 9 = 16 (A, E); 10 + 16 = 26 (root). দৈর্ঘ্য: A, D, E = ২ bit; B, C = ৩ bit. মোট bit = 7·2 + 9·2 + 5·2 + 3·3 + 2·3 = ৫৭ — আর এটি merge-গুলোর যোগফলের সমান: 5 + 10 + 16 + 26 = 57 ✓ (সহজ চেক)। Tie-এর কারণে আসল 0/1 code আলাদা হতে পারে, কিন্তু মোট bit সবসময় একই।

dp = [0, 1, 2, 1, 1, 2, 2] (dp[x] = 1 + min dp[x − c]). উত্তর ২টি coin (3 + 3). Greedy: 4 + 1 + 1 = ৩টি — ভুল। এই coin system “canonical” নয়, তাই greedy খাটে না (পর্ব ৫০, ৫৩)। এই ছোট পাল্টা-উদাহরণটি মনে রাখুন।

[3] → [3, 10] → [2, 10] → [1, 10] → [1, 10, 20] → [1, 4, 20] → [1, 4, 6] → [1, 4, 6, 7]. দৈর্ঘ্য ৪ (যেমন 3, 4, 6, 7). সাবধান: tails নিজে সাধারণত একটি আসল subsequence নয় — এখানে কাকতালীয়ভাবে 1, 4, 6, 7 বৈধ, কিন্তু মাঝপথের [1, 10] বৈধ নয় (1 আসে 10-এর পরে)। tails[k] মানে “দৈর্ঘ্য k + 1-এর বাড়ন্ত subsequence-এর সবচেয়ে ছোট সম্ভাব্য শেষ”.

capacity       0  1  2  3  4  5  6  7
after (1,1)    0  1  1  1  1  1  1  1
after (3,4)    0  1  1  4  5  5  5  5
after (4,5)    0  1  1  4  5  6  6  9
after (5,7)    0  1  1  4  5  7  8  9

উত্তর 9 = (3, 4) + (4, 5), ওজন ঠিক 7. লোভে সবচেয়ে মূল্যবান (5, 7) নিলে বাকি 2-এ শুধু (1, 1) — মোট 8. Capacity উল্টো দিকে (7 থেকে নিচে) ঘোরানোর কারণ: সামনে ঘোরালে একই জিনিস একাধিকবার নেওয়া হয়ে যায় (তখন সেটি unbounded knapsack).

        -  B  D  C  A  B  A
   -    0  0  0  0  0  0  0
   A    0  0  0  0  1  1  1
   B    0  1  1  1  1  2  2
   C    0  1  1  2  2  2  2
   B    0  1  1  2  2  3  3
   D    0  1  2  2  2  3  3
   A    0  1  2  2  3  3  4

দৈর্ঘ্য ৪, LCS BCBA. এই জোড়ায় দৈর্ঘ্য-৪-এর common subsequence একটিই (সব পথ খুঁজে যাচাই করা), তাই tie-নিয়ম বদলালেও একই উত্তর। অনেক ইনপুটে তা হয় না: X = ABC, Y = ACB-তে “ওপর আগে” নিয়ম দেয় AB, “বাঁ আগে” দেয় AC — দুটিই সঠিক, তাই উত্তরে নিজের tie-নিয়ম লিখুন। চেক: প্রতিটি সারি বাঁ থেকে ডানে কখনো কমে না, আর পাশের ঘরের পার্থক্য সর্বোচ্চ ১.

        -  D  A  C  C  A
   -    0  1  2  3  4  5
   D    1  0  1  2  3  4
   H    2  1  1  2  3  4
   A    3  2  1  2  3  3
   K    4  3  2  2  3  4
   A    5  4  3  3  3  3

উত্তর ৩: D ঠিক, H → A, A → C, K → C, শেষ A ঠিক — তিনটি replace. সূত্র: D[i][j] = min(D[i−1][j] + 1, D[i][j−1] + 1, D[i−1][j−1] + (অক্ষর আলাদা হলে 1, নইলে 0)). প্রথম সারি আর কলাম 0, 1, 2, … — খালি string থেকে বানাতে সব insert.

দৈর্ঘ্য ২: m[1][2] = 5·10·3 = 150, m[2][3] = 10·3·12 = 360, m[3][4] = 3·12·5 = 180. দৈর্ঘ্য ৩: m[1][3] = min(0 + 360 + 600, 150 + 0 + 180) = 330; m[2][4] = min(0 + 180 + 150, 360 + 0 + 600) = 330. দৈর্ঘ্য ৪: m[1][4] = min(k=1: 330 + 250 = 580, k=2: 150 + 180 + 75 = 405, k=3: 330 + 300 = 630) = 405, বন্ধনী (A1 A2)(A3 A4). টেবিল দৈর্ঘ্য ধরে ভরতে হয় (কোনাকুনি), সারি ধরে নয় — প্রচলিত ভুল।

(a) π = [0, 0, 1, 2, 0, 1, 2, 3, 4]. i = 4-এ C আগের কোনো border বাড়াতে পারে না — π নেমে 0; তারপর ABAB আবার গড়ে ওঠে, শেষে π[8] = 4 (ABAB হলো prefix আর suffix দুটোই)। (b) index 0, 2, 7. একটি মিলের পর k = π[k − 1] = 2 থেকে চলতে থাকে, তাই index 2-এর overlap-করা মিলও ধরা পড়ে।

নিচে নামা: (252, 198) q = 1 → (198, 54) q = 3 → (54, 36) q = 1 → (36, 18) q = 2 → (18, 0): gcd = 18. ওপরে ওঠা (x, y): (18, 0): (1, 0); (36, 18): (0, 1); (54, 36): (1, −1); (198, 54): (−1, 4); (252, 198): (4, −5). নিয়ম: নিচের (x′, y′) থেকে x = y′, y = x′ − q·y′. চেক: 252·4 − 198·5 = 1008 − 990 = 18 ✓.

p = 2: 4, 6, 8, …, 30 (১৪টি). p = 3: শুরু 9 থেকে; নতুন কাটা 9, 15, 21, 27 (12, 18, 24, 30 আগেই কাটা). p = 5: শুরু 25; নতুন শুধু 25 (30 আগেই). p = 7: 49 > 30 — থামুন (√30 < 6). মৌলিক: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 — ১০টি।