অ্যালগরিদম ঠিক কি না — loop invariant আর induction

১ · “চলছে” মানেই “ঠিক” নয় — testing-এর সীমা

একটি দৃশ্য ভাবুন। তানিয়া একটি সর্টিং ফাংশন লিখল। পাঁচটি ইনপুটে চালিয়ে দেখল — প্রতিবারই অ্যারে সুন্দরভাবে সাজানো আসছে। সে খুশি হয়ে কোডটি কনটেস্টে জমা দিল। ফল এলো: Wrong answer on test 37. পরীক্ষা করে দেখা গেল, অ্যারেতে একই সংখ্যা দুবার থাকলে (যেমন 3 1 3) তার ফাংশন একটি সংখ্যা হারিয়ে ফেলে। তানিয়ার পাঁচটি ইনপুটের কোনোটিতেই পুনরাবৃত্ত সংখ্যা ছিল না।

এই ঘটনার শিক্ষাটি সহজ, কিন্তু গভীর। একটি ইনপুটে ঠিক উত্তর পাওয়া মানে শুধু ওই ইনপুটে ঠিক। ১০টি সংখ্যার অ্যারেতেই সম্ভাব্য ইনপুট অসংখ্য; সবগুলো চালিয়ে দেখা অসম্ভব। তাহলে আমরা কীভাবে নিশ্চিত হব যে একটি অ্যালগরিদম correct — অর্থাৎ প্রতিটি বৈধ ইনপুটে ঠিক উত্তর দেয়?

ডাচ কম্পিউটার বিজ্ঞানী Edsger Dijkstra ১৯৬৯-৭০ সালের দিকে এই কথাটি বলেন ও লেখেন (তাঁর “Notes on Structured Programming”-এ)। বাংলায়: testing দেখাতে পারে যে বাগ আছে, কিন্তু কখনো দেখাতে পারে না যে বাগ নেই। ১০০টি test পাস করা মানে ১০০টি ইনপুটে বাগ পাওয়া যায়নি — ১০১ নম্বরে কী হবে, test তা বলে না।

এই পর্বে আমরা সেই “হিসাব” শিখব — অ্যালগরিদমের সঠিকতার প্রমাণ। ভয় পাওয়ার কিছু নেই; এখানে কঠিন গণিত লাগবে না। লাগবে তিনটি হাতিয়ার: loop invariant (লুপের জন্য), induction (রিকার্শনের জন্য) আর counterexample (ভুল ধরার জন্য)। সাথে থাকবে দুটি ব্যবহারিক কৌশল — assert আর stress testing — যা প্রমাণের চিন্তাকে সরাসরি কোডে নিয়ে আসে।

২ · “ঠিক” মানে কী — specification, partial আর total correctness

“অ্যালগরিদমটি ঠিক” বলার আগে বলতে হবে কীসের তুলনায় ঠিক। সেই মাপকাঠির নাম specification. এর দুটি অংশ:

সর্টিংয়ের উদাহরণটি খেয়াল করুন। শুধু “আউটপুট সাজানো” বললে specification অসম্পূর্ণ — যে ফাংশন সব ঘরে 0 বসিয়ে দেয়, তার আউটপুটও তো সাজানো! তাই পুরো postcondition হলো: আউটপুট সাজানো, এবং এটি ইনপুটেরই একটি পুনর্বিন্যাস (permutation) — কোনো সংখ্যা হারায়নি, নতুনও আসেনি। তানিয়ার বাগ ঠিক এই দ্বিতীয় অংশটি ভেঙেছিল।

দুই স্তরের সঠিকতা

একটি অ্যালগরিদম দুইভাবে ব্যর্থ হতে পারে: ভুল উত্তর দিয়ে, অথবা কোনো উত্তরই না দিয়ে (চিরকাল লুপে ঘুরে)। তাই সঠিকতাকে দুই ভাগে দেখা হয়:

Tony Hoare এই ভাবনাকে একটি ছোট সংকেতে লেখেন, যাকে বলে Hoare triple: {P} S {Q} — “P সত্য থাকা অবস্থায় S চালালে, S থামলে Q সত্য হবে।” এখানে P হলো precondition, Q postcondition. পুরো কোর্সে আমরা এই সংকেত না লিখলেও চিন্তাটি বারবার ব্যবহার করব।

৩ · Loop invariant — তিন ধাপের প্রমাণ

বেশিরভাগ অ্যালগরিদমের প্রাণ একটি লুপ। লুপ হাজার, লাখ বার ঘুরতে পারে — প্রতিটি ঘোরা আলাদা করে দেখা সম্ভব নয়। তাই আমরা এমন একটি কথা খুঁজি, যা প্রতিটি ঘোরার শুরুতে (লুপের শর্ত যাচাইয়ের মুহূর্তে) সবসময় সত্য থাকে। সেটিই loop invariant — “অপরিবর্তনীয় সত্য”।

একটি invariant দিয়ে প্রমাণ করতে তিনটি জিনিস দেখাতে হয় (CLRS-এর মতো বিখ্যাত পাঠ্যবইও ঠিক এই কাঠামো ব্যবহার করে):

খেয়াল করুন, প্রথম দুটি ধাপ আসলে induction — ঘোরার সংখ্যার ওপর। তৃতীয় ধাপটিই invariant-কে “কাজের” বানায়: যে invariant থেকে শেষে উত্তর বের হয় না, তা সত্য হলেও অকেজো (যেমন “i ≥ 0” — সত্য, কিন্তু কিছুই প্রমাণ করে না)।

প্রথম উদাহরণ: অ্যারের সবচেয়ে বড় সংখ্যা

ধরুন একটি অ্যারে a[0..n-1] (এই পর্বে সব index ০ থেকে শুরু, আর a[l..r] মানে l থেকে r পর্যন্ত দুই প্রান্তসহ)। Precondition: n ≥ 1. Postcondition: ফেরত দেওয়া মান = অ্যারের সর্বোচ্চ। Invariant:

নিচে a = [3, 8, 2, 9, 4] দিয়ে লুপটি চালিয়ে দেখুন। প্রতিটি ধাপে “এ পর্যন্ত দেখা অংশ” আর best মিলিয়ে দেখুন invariant সত্য কি না:

1int best = a[0];2for (int i = 1; i < n; i++)3    if (a[i] > best) best = a[i];4return best;

লক্ষ্য করুন, প্রমাণের কোথাও “3, 8, 2, 9, 4” সংখ্যাগুলো লাগেনি। Stepper শুধু আপনাকে invariant-টি চোখে দেখাল; আসল প্রমাণ সাধারণ যুক্তি — যেকোনো অ্যারে, যেকোনো n-এর জন্য। এখানেই test আর proof-এর পার্থক্য।

৪ · Insertion sort-এর সম্পূর্ণ প্রমাণ

এবার একটু বড় উদাহরণ — insertion sort. এটি ঠিক পরীক্ষার খাতা সাজানোর পদ্ধতি: বাঁ দিকে একটি সাজানো অংশ, ডান দিক থেকে একটি করে উপাদান (key) নিয়ে সাজানো অংশে তার ঠিক জায়গায় ঢোকানো। (সর্টিংয়ের বিস্তারিত তুলনা পর্ব ২০-এ।) প্রথমে pseudocode (০-ভিত্তিক index):

Pseudocode: INSERTION-SORT(a[0..n-1])
for i = 1 to n-1:
    // invariant: a[0..i-1] holds the original first i items, sorted
    key = a[i]
    j = i
    while j > 0 and a[j-1] > key:
        a[j] = a[j-1]          // shift bigger item one step right
        j = j - 1
    a[j] = key

Invariant-এর দুটি অংশই জরুরি — “সাজানো” আর “সেই উপাদানগুলোই” — কারণ postcondition-ও দুই অংশের (সেকশন ২ মনে করুন)। নিচে CLRS বইয়ের বিখ্যাত উদাহরণ [5, 2, 4, 6, 1, 3] দিয়ে দেখুন। বন্ধনীর ভেতরের অংশ […] হলো invariant-এর সাজানো অংশ:

1for (i = 1; i < n; i++) {2    key = a[i]; j = i;3    while (j > 0 && a[j-1] > key)4        { a[j] = a[j-1]; j--; }5    a[j] = key;6}

প্রমাণটি সাধারণ ভাষায় লিখলে

Initialization: i = 1-এ a[0..0] একটি উপাদান, তাই সাজানো। Maintenance: ধরা যাক ঘোরার শুরুতে a[0..i-1] সাজানো। ভেতরের লুপ a[i-1], a[i-2], … থেকে key-এর চেয়ে বড় প্রতিটি উপাদানকে এক ঘর ডানে সরায় এবং প্রথম যে ঘরে a[j-1] ≤ key (বা j = 0) সেখানে থামে। Key সেখানে বসলে তার বাঁয়ের সবাই ≤ key, ডানের সবাই > key, আর দুই পাশ আগে থেকেই সাজানো — তাই a[0..i] সাজানো, এবং উপাদানগুলো শুধু জায়গা বদলেছে। i এক বাড়লে invariant আবার সত্য। Termination: i = n-এ invariant-ই postcondition.

পুরোপুরি কঠোর হতে চাইলে ভেতরের while লুপেরও আলাদা invariant লাগে (যেমন “a[j+1..i]-এর সবাই key-এর চেয়ে বড় এবং সাজানো”)। বিশ্ববিদ্যালয়ের পরীক্ষায় সাধারণত বাইরের লুপের তিন ধাপই চাওয়া হয়, তবে ভেতরের লুপের যুক্তিটি এক লাইনে বলে দিলে উত্তর সম্পূর্ণ হয়।

Invariant-কে কোডে পাহারায় বসানো

প্রমাণ কাগজে থাকে; কিন্তু কোড বদলায়। কেউ পরে কোড বদলে ভুল করলে কি প্রমাণ আমাদের সতর্ক করবে? করবে, যদি invariant-কে assertion হিসেবে কোডেই লিখে রাখি। assert(শর্ত) চলার সময় শর্তটি যাচাই করে; মিথ্যা হলে প্রোগ্রাম সঙ্গে সঙ্গে থেমে কোন লাইনে ভাঙল তা জানায়। নিচে insertion sort, প্রতিটি ঘোরার শুরুতে invariant যাচাইসহ। আপনার ভাষার ট্যাবটি বেছে নিন:

#include <bits/stdc++.h>
#include <cassert>
using namespace std;
void show(const vector<int>& a, size_t i) {
    cout << "i=" << i << ":";
    for (size_t k = 0; k < a.size(); ++k) cout << (k == i ? " | " : " ") << a[k];
    cout << '\n';
}

int main() {
    vector<int> a = {5, 2, 4, 6, 1, 3};
    for (size_t i = 1; i < a.size(); ++i) {
        assert(is_sorted(a.begin(), a.begin() + i));   // invariant: a[0..i-1] sorted
        show(a, i);
        int key = a[i];
        size_t j = i;
        while (j > 0 && a[j - 1] > key) { a[j] = a[j - 1]; --j; }
        a[j] = key;
    }
    assert(is_sorted(a.begin(), a.end()));             // postcondition
    show(a, a.size());
    cout << "invariant held at every step\n";
}

i=1: 5 | 2 4 6 1 3
i=2: 2 5 | 4 6 1 3
i=3: 2 4 5 | 6 1 3
i=4: 2 4 5 6 | 1 3
i=5: 1 2 4 5 6 | 3
i=6: 1 2 3 4 5 6
invariant held at every step

def show(a, i):
    parts = [(" | " if k == i else " ") + str(x) for k, x in enumerate(a)]
    print(f"i={i}:" + "".join(parts))

def insertion_sort(a):
    for i in range(1, len(a)):
        # invariant: a[0..i-1] is sorted
        assert all(a[k] <= a[k + 1] for k in range(i - 1)), "invariant broken"
        show(a, i)
        key, j = a[i], i
        while j > 0 and a[j - 1] > key:
            a[j] = a[j - 1]
            j -= 1
        a[j] = key

a = [5, 2, 4, 6, 1, 3]
insertion_sort(a)
assert a == sorted(a)  # postcondition
show(a, len(a))
print("invariant held at every step")

i=1: 5 | 2 4 6 1 3
i=2: 2 5 | 4 6 1 3
i=3: 2 4 5 | 6 1 3
i=4: 2 4 5 6 | 1 3
i=5: 1 2 4 5 6 | 3
i=6: 1 2 3 4 5 6
invariant held at every step

দুই সংস্করণেই প্রতিটি লাইনের শুরুতে |-এর বাঁ অংশ সাজানো — stepper-এ যা দেখেছেন, কোড নিজেই তা যাচাই করছে। এবার একটি পরীক্ষা করুন: ভেতরের লুপের শর্তে a[j - 1] > key-এর জায়গায় a[j - 1] < key লিখে চালান। দ্বিতীয় ঘোরাতেই assert ভেঙে প্রোগ্রাম থেমে যাবে — ভুলটি যেখানে জন্ম নিল, ঠিক সেখানেই ধরা পড়ল, শেষের ভুল আউটপুটে নয়।

৫ · Binary search — invariant ছাড়া off-by-one অনিবার্য

Binary search-এর ধারণা এক বাক্যের: সাজানো অ্যারের মাঝখানে দেখুন, লক্ষ্য ছোট হলে বাঁ অর্ধেকে, বড় হলে ডান অর্ধেকে খুঁজুন। অথচ এটি সঠিকভাবে লেখা কুখ্যাতভাবে কঠিন। Jon Bentley তাঁর “Programming Pearls” বইয়ে লিখেছেন, পেশাদার প্রোগ্রামারদের ক্লাসে binary search লিখতে দিয়ে তিনি দেখেছেন বেশিরভাগের কোডেই বাগ ছিল। Donald Knuth উল্লেখ করেছেন, ধারণাটি ১৯৪৬ সালে (John Mauchly) প্রথম বর্ণিত হওয়ার পর সব n-এর জন্য সঠিক সংস্করণ আসতে আরও প্রায় দেড় দশক লেগেছিল — সাধারণত এর কৃতিত্ব দেওয়া হয় D. H. Lehmer-এর ১৯৬০ সালের সংস্করণকে।

সমস্যার মূলে off-by-one ভুল: lo = mid নাকি mid + 1? শর্ত lo < hi নাকি lo <= hi? এসব প্রশ্নের উত্তর মুখস্থ না করে একটি invariant ঠিক করে নিলেই প্রতিটি লাইন নিজে থেকে বেরিয়ে আসে। আমরা দুই প্রান্তসহ বন্ধ পরিসর [lo, hi] নেব:

এখন প্রতিটি লাইন যাচাই করুন: শুরুতে lo = 0, hi = n-1 — পুরো অ্যারে, invariant সত্য। a[mid] < x হলে a[0..mid]-এর সবাই ≤ a[mid] < x, তাই x সেখানে থাকতে পারে না — lo = mid + 1 (শুধু mid নয়!)। উল্টোটিতে hi = mid - 1. পরিসর ফাঁকা হলে (lo > hi) invariant বলছে “x থাকলে ফাঁকা পরিসরে আছে” — অর্থাৎ নেই। নিচে a = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]-এ x = 20 খুঁজে দেখুন (20 অ্যারেতে নেই — এটাই কঠিন ক্ষেত্র):

1int lo = 0, hi = n - 1;2while (lo <= hi) {3    int mid = lo + (hi - lo) / 2;4    if (a[mid] == x) return mid;5    if (a[mid] < x) lo = mid + 1;6    else hi = mid - 1;7}8return -1;

এবার দেখুন ভুল সংস্করণ কেন ভুল। যদি লেখেন lo = mid, তাহলে lo = 5, hi = 6-এ mid = 5; a[5] < x হলে (ধরুন x = 30) আবার lo = 5 — পরিসর একটুও ছোট হয় না, লুপ চিরকাল চলে। Invariant ঠিক থাকলেও termination ভেঙেছে! আর শর্ত lo < hi লিখলে একটি-ঘরের পরিসর (lo == hi) কখনো যাচাই হয় না — invariant-এর termination ধাপ “ফাঁকা পরিসর” দাবি করতে পারে না, তাই উত্তর ভুল।

৬ · লুপ কি থামবে? — variant function দিয়ে termination

Invariant বলে “থামলে ঠিক”; থামার নিশ্চয়তা আলাদা যুক্তি চায়। সবচেয়ে প্রচলিত হাতিয়ার variant function (বা “কমতে থাকা মাপ”): এমন একটি পূর্ণসংখ্যা খুঁজুন যা

• লুপ চলাকালীন কখনো ঋণাত্মক হয় না (নিচে একটি দেয়াল আছে), এবং
• প্রতিটি ঘোরায় অন্তত ১ করে কঠোরভাবে কমে।

একটি অঋণাত্মক পূর্ণসংখ্যা অসীমবার কমতে পারে না — ১০ থেকে শুরু করলে সর্বোচ্চ ১০ বার। তাই লুপ থামবেই, এবং variant-এর শুরুর মান ঘোরার সংখ্যার একটি ঊর্ধ্বসীমাও দেয়।

শেষ সারিটি দেখুন। Euclid-এর পদ্ধতি — প্রায় ২,৩০০ বছর আগে তাঁর “Elements” গ্রন্থে লেখা, এখনো ব্যবহৃত সবচেয়ে পুরোনো অ্যালগরিদমগুলোর একটি:

Pseudocode: GCD(a, b)        // precondition: a ≥ 0, b ≥ 0
if b == 0: return a
return GCD(b, a mod b)

এখানে দুটি জিনিস প্রমাণ করতে হবে। Termination: প্রতিটি ডাকে দ্বিতীয় আর্গুমেন্ট b থেকে a mod b হয়, যা সবসময় b-এর চেয়ে ছোট এবং ≥ ০ — variant b কঠোরভাবে কমে, তাই একসময় ০ হবেই। Correctness: মূল সূত্র gcd(a, b) = gcd(b, a mod b) — কারণ a mod b = a − q·b, তাই যে সংখ্যা a আর b দুটোকেই ভাগ করে সে a mod b-কেও ভাগ করে, আর উল্টোটাও সত্য। দুই জোড়ার সাধারণ গুণনীয়কের সেট হুবহু এক, তাই GCD-ও এক। এটি একরকম “রিকার্শনের invariant”: প্রতিটি ডাকে উত্তরটি বদলায় না।

৭ · Mathematical induction — রিকার্সিভ অ্যালগরিদমের প্রমাণ

লুপের জন্য invariant; রিকার্শনের জন্য induction. আসলে দুটো একই চিন্তার দুই রূপ। Induction-এর কাঠামো:

1. Base case: সবচেয়ে ছোট ইনপুটে (যেমন n = 0) দাবিটি সত্য।
2. Inductive step: n = k-তে সত্য ধরে নিয়ে (একে বলে inductive hypothesis) n = k + 1-এ সত্য দেখানো।

Weak induction: রিকার্সিভ যোগফল

Pseudocode: SUM(n)           // precondition: n ≥ 0
if n == 0: return 0
return n + SUM(n - 1)

দাবি: সব n ≥ ০-এর জন্য SUM(n) = n(n+1)/2. Base: SUM(0) = 0 = 0·1/2 ✓. Step: ধরা যাক SUM(k) = k(k+1)/2. তাহলে SUM(k+1) = (k+1) + SUM(k) = (k+1) + k(k+1)/2 = (k+1)(k+2)/2 ✓. Induction অনুযায়ী দাবিটি সব n-এর জন্য সত্য। (Termination: প্রতিটি ডাকে n এক কমে, ০-তে থামে — variant n.)

Strong induction: দ্রুত power

কখনো রিকার্শন ঠিক আগের মান নয়, অনেক ছোট কোনো মান ডাকে — যেমন n/2. তখন লাগে strong induction: k + 1-এর জন্য প্রমাণ করতে ০ থেকে k পর্যন্ত সব মানে দাবি সত্য ধরে নেওয়া যায়।

Pseudocode: POWER(x, n)      // precondition: n ≥ 0; returns x^n
if n == 0: return 1
h = POWER(x, n div 2)        // n div 2 = floor(n / 2)
if n is even: return h * h
else:         return h * h * x

দাবি: সব n ≥ ০-এ POWER(x, n) = xⁿ. Base: n = ০-তে ১ = x⁰ ✓. Step: ধরা যাক n ≥ ১, আর n-এর চেয়ে ছোট সব m-এ POWER(x, m) = xᵐ. যেহেতু m = ⌊n/2⌋ < n, hypothesis অনুযায়ী h = x^⌊n/2⌋. n জোড় হলে h·h = x^(n/2 + n/2) = xⁿ; বিজোড় হলে ⌊n/2⌋ = (n−1)/2, তাই h·h·x = x^(n−1+1) = xⁿ ✓. লক্ষ করুন, weak induction এখানে যথেষ্ট নয় — n − ১-এ সত্য জেনে লাভ নেই, কারণ ডাকটি যায় ⌊n/2⌋-এ। প্রতিটি ডাকে n অর্ধেক হয়, তাই ডাকের সংখ্যা ⌊log₂ n⌋ + ২-এর বেশি নয় — সময় O(log n), আর call stack-এর জন্য জায়গা O(log n).

Euclid-এর GCD-ও strong induction-এর উদাহরণ: দ্বিতীয় আর্গুমেন্ট b-এর ওপর induction. b = ০-তে উত্তর a — ঠিক। b > ০ হলে পরের ডাকের দ্বিতীয় আর্গুমেন্ট a mod b < b, তাই hypothesis অনুযায়ী সেই ডাক gcd(b, a mod b) ঠিক ফেরত দেয়, আর সূত্র অনুযায়ী সেটিই gcd(a, b). রিকার্শন আর call stack-এর ভেতরের কাজ পর্ব ০৭-এ, আর রিকার্শনের সময় হিসাবের (recurrence) পদ্ধতি পর্ব ০৮-এ দেখবেন।

সংক্ষেপে: proof by contradiction

আরেকটি প্রচলিত কৌশল proof by contradiction: দাবিটি মিথ্যা ধরে নিন, তারপর দেখান এতে অসম্ভব কিছু ঘটে। উদাহরণ — “অসাজানো অ্যারের সর্বোচ্চ খুঁজতে প্রতিটি ঘর অন্তত একবার পড়তেই হবে।” ধরুন কোনো অ্যালগরিদম কোনো একটি ঘর a[k] না পড়েই উত্তর দেয়। তাহলে a[k]-এ অন্য সবার চেয়ে বড় একটি সংখ্যা বসিয়ে দিন — অ্যালগরিদমের কাছে ইনপুট “একই রকম দেখায়”, তাই সে আগের উত্তরই দেবে, যা এখন ভুল। বিরোধ! সুতরাং যেকোনো সঠিক অ্যালগরিদমকে n-টি ঘরই পড়তে হয় — সময় Ω(n). এই ধরনের যুক্তি দিয়েই পর্ব ২৪-এ তুলনা-ভিত্তিক সর্টিংয়ের নিম্নসীমা দেখানো হবে।

৮ · একটি counterexample-ই যথেষ্ট — ভুল অ্যালগরিদম ধরা

“ঠিক” প্রমাণ করতে সব ইনপুটের জন্য যুক্তি লাগে। কিন্তু “ভুল” প্রমাণ করতে লাগে মাত্র একটি ইনপুট, যেখানে অ্যালগরিদম ভুল উত্তর দেয়। একেই বলে counterexample. এটি অসমতার একটি সুন্দর দিক: প্রমাণ কঠিন, খণ্ডন সহজ।

ক্লাসিক উদাহরণ — খুচরা দেওয়ার সমস্যা: কিছু কয়েনের মান দেওয়া আছে, একটি অঙ্ক বানাতে সবচেয়ে কম কয়টি কয়েন লাগে? স্বাভাবিক বুদ্ধি বলে একটি greedy নিয়ম: “প্রতিবার সবচেয়ে বড় যে কয়েনটি ধরে, সেটি নাও।” দোকানে ৮৭ টাকা ফেরত দিতে আমরা ঠিক এভাবেই ৫০, ২০, ১০, ৫, ২ নিই — এবং বাংলাদেশের টাকার মানের ক্ষেত্রে এটি আসলেই সবচেয়ে কম নোট দেয়। কিন্তু এটি কি সবসময় কাজ করে?

কিন্তু counterexample খুঁজে পাব কীভাবে? মাথা খাটিয়ে, অথবা — আরও নির্ভরযোগ্যভাবে — কম্পিউটারকে দিয়ে। একটি brute force সমাধান লিখুন যা ধীর হলেও নিশ্চিতভাবে ঠিক (এখানে প্রতিটি অঙ্কের জন্য “শেষ কয়েনটি কোনটি” সব সম্ভাবনা যাচাই), তারপর ছোট ছোট সব ইনপুটে দুটির উত্তর মিলিয়ে দেখুন। নিচের কোডটি পাতাতেই চলবে — “Run” চাপুন:

const coins = [4, 3, 1];            // greedy tries the largest coin first
function greedy(amount) {
  let cnt = 0;
  for (const c of coins) { cnt += Math.floor(amount / c); amount %= c; }
  return cnt;
}
function optimal(amount) {          // brute force over the last coin (DP)
  const best = [0];
  for (let v = 1; v <= amount; v++) {
    best[v] = Infinity;
    for (const c of coins) if (c <= v) best[v] = Math.min(best[v], best[v - c] + 1);
  }
  return best[amount];
}
let bad = 0;
for (let amount = 1; amount <= 15; amount++) {
  const g = greedy(amount), b = optimal(amount);
  if (g !== b) { bad++; console.log(`amount ${amount}: greedy ${g} coins, optimal ${b} coins`); }
}
console.log(bad ? `${bad} counterexamples in 1..15` : "no counterexample in 1..15");

amount 6: greedy 3 coins, optimal 2 coins
amount 10: greedy 4 coins, optimal 3 coins
amount 14: greedy 5 coins, optimal 4 coins
3 counterexamples in 1..15

এই কোডটি আসলে একটি ছোট stress test: দ্রুত (কিন্তু সন্দেহজনক) সমাধানকে ধীর (কিন্তু নিশ্চিত) সমাধানের সাথে অনেক ইনপুটে মেলানো। এখানে brute force-এর সময় O(A·k) — A অঙ্ক, k কয়েনের সংখ্যা — যা ছোট A-তে নগণ্য। কনটেস্ট প্রোগ্রামাররা ঠিক এই কৌশলে নিজের “Wrong answer”-এর কারণ খুঁজে বের করেন। পরের সেকশনে কৌশলটি সাধারণভাবে দেখব।

৯ · কোডের ভেতরে প্রমাণ — assert আর stress testing

প্রমাণ মাথায় বা খাতায় থাকে; বাগ থাকে কোডে। দুটিকে জোড়ার দুটি ব্যবহারিক উপায় আছে।

১. Assertion: চলমান invariant

যেখানে আপনার যুক্তি বলে “এখানে এটা সত্য হতেই হবে”, সেখানে assert লিখুন। C++-এ <cassert>-এর assert(cond), Python-এ assert cond, "message". সাধারণ তিনটি জায়গা: ফাংশনের শুরুতে precondition, লুপের ভেতরে invariant, আর ফেরত দেওয়ার আগে postcondition.

int binary_search(const vector<int>& a, int x) {
    assert(is_sorted(a.begin(), a.end()));        // precondition (debug only: O(n))
    int lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        assert(lo <= mid && mid <= hi);           // mid stays inside the range
        if (a[mid] == x) return mid;
        if (a[mid] < x) lo = mid + 1; else hi = mid - 1;
    }
    return -1;
}

২. Stress testing: brute force-এর সাথে হাজারো তুলনা

কনটেস্ট আর ইন্টারভিউতে সবচেয়ে কাজের যাচাই-কৌশল এটি। চারটি অংশ:

1. দ্রুত সমাধান — যেটি আপনি যাচাই করতে চান।
2. Brute force — সরলতম, ধীর, কিন্তু স্পষ্টভাবে ঠিক সমাধান (সব সম্ভাবনা যাচাই)।
3. ছোট এলোমেলো ইনপুট তৈরি — যেমন ১ থেকে ৮ আকারের অ্যারে, মান ০ থেকে ৫; ছোট মানে পুনরাবৃত্ত সংখ্যা, শূন্য আর সীমানার ক্ষেত্র ঘন ঘন আসে।
4. মিলিয়ে দেখা — অমিল হলেই সেই ইনপুট ছাপিয়ে থামুন। ছোট ইনপুট বলে হাতে trace করা সহজ।

import random

def fast(a): ...            # your clever solution
def brute(a): ...           # obviously-correct slow solution

for t in range(10000):
    a = [random.randint(0, 5) for _ in range(random.randint(1, 8))]
    if fast(a[:]) != brute(a[:]):
        print("counterexample:", a, fast(a[:]), brute(a[:]))
        break
else:
    print("10000 random tests passed")

তানিয়ার পুনরাবৃত্ত সংখ্যার বাগ এই পদ্ধতিতে কয়েক মিলিসেকেন্ডেই ধরা পড়ত — মান ০ থেকে ৫-এর মধ্যে রাখলে দশ হাজার অ্যারের অনেকগুলোতেই একই সংখ্যা দুবার আসবে। মনে রাখবেন, stress testing প্রমাণ নয়; এটি counterexample খোঁজার যন্ত্র। প্রমাণ আর stress test একে অপরের পরিপূরক: প্রমাণ বলে “কেন ঠিক”, stress test ধরে “প্রমাণে বা কোডে কোথায় ফাঁক”।

১০ · AI-এর যুগে — কোড নয়, প্রমাণ চান

AI এখন সেকেন্ডে binary search, DP বা greedy সমাধান লিখে দেয়, সাথে আত্মবিশ্বাসী ব্যাখ্যাও। সমস্যা হলো, আত্মবিশ্বাস আর সঠিকতা এক জিনিস নয়। DSA-তে AI-এর সবচেয়ে প্রচলিত ভুলগুলো ঠিক এই পর্বের বিষয়: সীমানায় < বনাম <= (off-by-one), প্রমাণ ছাড়াই greedy, আর ভুল complexity দাবি। এই পর্বের হাতিয়ারগুলো দিয়েই এগুলো ধরা যায়।

AI-এর অ্যালগরিদম হাতে পেলে — যাচাইয়ের চেকলিস্ট

• Precondition আর postcondition নিজের ভাষায় লিখেছি — “ঠিক উত্তর” মানে কী, তা স্পষ্ট
• প্রতিটি লুপের invariant আর variant বলতে পারি, এবং কোডের প্রতিটি সীমানা (<, +1, -1) invariant-এর সাথে মেলে
• ফাঁকা ইনপুট, এক উপাদান, সব সমান, সবচেয়ে ছোট ও বড় মান — এগুলো হাতে trace করেছি
• Brute force লিখে হাজারো ছোট এলোমেলো ইনপুটে stress test চালিয়েছি
• Greedy হলে হয় প্রমাণ আছে, নয়তো counterexample খুঁজে দেখেছি