প্রোগ্রামিং

স্ট্রিং ম্যাচিং: নুথ-মরিসন-প্র্যাট (কেএমপি) অ্যালগরিদম

আজকে আমরা শিখবো কেএমপি (KMP) অ্যালগরিদম ব্যবহার করে স্ট্রিং ম্যাচিং করা। কেএমপি শব্দটি এসেছে ৩জন কম্পিউটার বিজ্ঞানী Donald Knuth, James H. Morris এবং Vaughan Pratt এর নাম থেকে। আমাদের প্রবলেম হলো একটা দুটি স্ট্রিং text এবং pattern দেয়া আছে, আমাদের বলতে হবে text এর ভিতর pattern স্ট্রিংটি সাবস্ট্রিং হিসাবে আছি কিনা। যেমন ধরো টেক্সটটি হলো "MOD", এই স্ট্রিংটার ৬টা সাবস্ট্রিং আছে "M", "O", "D", "MO", "OD" এবং "MOD", এখন যদি pattern = "MO" খুজতে বলে আমরা true রিটার্ন করবো। ব্রুটফোর্স অ্যালগরিদম ব্যবহার করে স্ট্রিং ম্যাচিং করার টাইম কমপ্লেক্সিটি $O(n*m)$, যেখানে $n$ এবং $m$ হলো টেক্সট ও ...
Read More

হতাশ প্রোগ্রামার

আগের লেখাটা ছিল কনফিউজড প্রোগ্রামারদের নিয়ে যারা ১০রকমের উপদেশের ভিড়ে বুঝতে পারছে না ডানে যাবে, নাকি বামে যাবে। এবারের লেখাটি হতাশ প্রোগ্রামারদের জন্য যাদের কোড লিখতে গেলেই মনে হয় "আমাকে দিয়ে কিছু হবে না"। প্রোগ্রামিং শিখতে গিয়ে এক পর্যায়ে হতাশ হয়ে যায় নি এমন কোনো মানুষ সম্ভবত ১টাও পাওয়া যায় না, পার্থক্য হলো অনেকে হতাশ হয়ে হাল ছেড়ে দেয়, অনেকে একগুয়ের মত লেগে থাকে। এই লেখার উদ্দেশ্য তোমাকে বড় বড় কথা বলে মোটিভেটেড করা না, বরং প্রোগ্রামিং করতে গিয়ে কেন মানুষ হতাশ হয় সেরকম কয়েকটা কারণ খুজে বের করা, অনেক সময় আমরা হতাশ হয়ে গেলে মাথাঠান্ডা করে চিন্তা করতে পারি না কেন হতাশ লাগছে আর তাই হতাশা...
Read More

কনফিউজড প্রোগ্রামার

প্রোগ্রামিং শেখা শুরু করার সময় আমাদের মনে হাজারটা প্রশ্ন আসে এবং আসাটাই স্বাভাবিক কারণ জিনিসটা আমাদের কাছে নতুন। কিন্তু সমস্যাটা হয় উত্তর খুজতে গিয়ে, দশজনকে জিজ্ঞেস করে আমরা দশটা উত্তর পাই। কেও বলবে আগে সি শিখো, কেও বলবো পিএইচপি শিখে আউটসোর্সিং এ নেমে যাও, কেও বলবে অ্যালগরিদম শিখে প্রোগ্রামিং কনটেস্ট করো। কিন্তু আমরা করবোটা আসলে কি? এই লেখার উদ্দেশ্য তোমাকে উপদেশ দিয়ে আরো কনফিউজড করা না, বরং কনফিউশন দূর করতে সাহায্য করা এবং নিজের কিছু অভিজ্ঞতা শেয়ার করা। কিছুদিন আগে প্রশ্ন-উত্তর ওয়েবসাইট Quora তে কিছু লেখা পড়ছিলাম যার বিষয় ছিল প্রোগ্রামিং শেখা আগের থেকে কঠিন হয়ে গেছে নাকি সহজ? ...
Read More

প্রোবাবিলিটি: এক্সপেক্টেড ভ্যালু

মনে করো তুমি লুডু খেলতে গিয়ে একটা ডাইস বা ছক্কা নিয়ে রোল করছো। এখন তোমার যেকোনো একটা সংখ্যা পাবার প্রোবাবিলিটি কত? বেসিক প্রোবাবিলিটি যদি জেনে থাকো তাহলে তুমি সহজেই বলতে পারবে যে উত্তরটা হলো $\frac{1}{6}$। প্রোবালিটি $\frac{1}{6}$ এর মানেটা কী এখানে? এর মানে হলো, তুমি যদি ছক্কাটা নিয়ে অসীম সংখ্যকব বার খেলতে থাকো তাহলে ছয় ভাগের এক ভাগ বার তুমি $1$ পাবে, অন্য আরেকভাগ বার তুমি $2$ পাবে, অন্য আরেকভাগ বার তুমি $3$ পাবে ইত্যাদি। যেমন তুমি $600$ বার খেললে, $1$ থেকে $6$ পর্যন্ত প্রতিটা সংখ্যা $100$ বার করে পাবে। এটাতো গেলে গাণিতিক হিসাব, বাস্তবে $600$ বার খেলতে গেলে দেখা যাবে প্রতিটা $10...
Read More

গ্রাফ অ্যালগরিদম বই!

৮ অক্টোবর আমার প্রথম বই গ্রাফ অ্যালগরিদম প্রকাশিত হয়েছে। বইটি যারা গ্রাফ থিওরি শুরু থেকে শিখতে চায় তাদের কথা ভেবে লেখা হয়েছে। বইয়ের সূচিপত্র নিচে তুলে দিলাম: সূচীপত্র অধ্যায় ১ – গ্রাফ থিওরিতে হাতেখড়ি অধ্যায় ২ – গ্রাফ উপস্থাপন অধ্যায় ৩ – ব্রেডথ ফার্স্ট সার্চ (Breadth First Search) অধ্যায় ৪ – ডায়াক্সট্রা অ্যালগরিদম (Dijkstra Algorithm) অধ্যায় ৫ – ফ্লয়েড ওয়ার্শল অ্যালগরিদম (Floyd Warshall Algorithm) অধ্যায় ৬ – ডিসজয়েন্ট সেট (Disjoint Set) অধ্যায় ৭ – মিনিমাম স্প্যানিং ট্রি (Minimum Spanning Tree) অধ্যায় ৮ – টপোলজিকাল সর্টিং (Topological Sorting) অধ্যায় ৯ – বেলম্যান ফোর্ড অ্যালগরি...
Read More

ডাটা স্ট্রাকচার: কিউ এবং সার্কুলার কিউ

কিউ একটা বেসিক ডাটা স্ট্রাকচার। এটাকে তুমি চিন্তা করতে পারো বাসের লাইনের মত, যে সবার সামনে দাড়িয়ে আছে সে সবার আগে উঠবে, নতুন কোনো যাত্রী আসলে সে লাইনের পিছনে দাড়াবে। কিউতে দুইরকম অপারেশন থাকে। এনকিউ(Enqueue) মানে হলো কিউতে নতুন এলিমেন্ট যোগ করা এবং ডিকিউ(Dequeue) বা পপ মানে হলো সবথেকে পুরোনো এলিমেন্টটা কিউ থেকে সরিয়ে ফেলা। অ্যারে ব্যবহার করে আমরা ফিক্সড সাইজের কিউ ইমপ্লিমেন্ট করতে পারি। আমাদেরকে সবসময় দুইটা পয়েন্টার রাখতে হবে, হেড (Head) পয়েন্টার নির্দেশ করবে কিউয়ের সামনের এলিমেন্টের পজিশন এবং টেইল (Tail) পয়েন্টার নির্দেশ করবে পিছনের এলিমেন্টের পজিশন। একদম শুরুতে Head = -1, Tail ...
Read More

হাল্টিং প্রবলেম

গণিত বা কম্পিউটার বিজ্ঞানের সব সমস্যাই কি সমাধানযোগ্য? আমরা জানি NP ক্যাটাগরির সমস্যাগুলোকে পলিনোমিয়াল সময়ে সমাধান করার সম্ভব নাকি সেটা জানা এখন পর্যন্ত সম্ভব হয় নি, কিন্তু ইনপুটের আকার যথেষ্ট ছোট হলে অথবা তোমার হাতে অসীম সময় এবং মেমরি থাকলে NP সমস্যাও এক্সপোনেনশিয়াল সময়ে সমাধান করা সম্ভব। কিন্তু এমন কিছু সমস্যা আছে যেটা তোমার হাতে যত বড় সুপার কম্পিউটারই থাকুক সমাধান করা সম্ভব না। এখানে আমি ধরে নিচ্ছি আমাদের কম্পিউটারগুলো টুরিং মেশিন কম্পিউটেবল। (টুরিং মেশিন কি মনে না থাকলে আগে আমার এই লেখাটা পড়ো) হাল্টিং প্রবলেম (Halting Problem) এমনই একটা সমস্যা যার কোনো সমাধান নেই। তোমাকে একট...
Read More

ব্যাকট্র্যাকিং: পারমুটেশন জেনারেটর

[পুরানো লেখা, নতুন করে গুছিয়ে লিখে আবার প্রকাশ করা হলো] ব্যাকট্র্যাকিং একধরণের ব্রুটফোর্স টেকনিক। ব্রুটফোর্সের মতই এটা সম্ভাব্য সবধরণের বিন্যাস-সমাবেশ থেকে ফলাফল খুজে নিয়ে আসে। যেমন ধর তোমাকে ঢাকা থেকে চট্টগ্রামার যাবার সবথেকে ছোটো পথ খুজে বের করতে বলা হলো। তুমি ডায়াক্সট্রার দেয়া অ্যালগোরিদম ব্যবহার না করে উত্তরা থেকে শাহবাগে যাবার যত পথ আছে সবগুলো খুজে বের করলে এবং তারপর তারমধ্যে থেকে সবথেকে ছোট কোনটা সেটা বের করলে, এটা হলো ব্রুটফোর্স বা কমপ্লিট সার্চ। এই লেখাটা পড়ার আগে অবশ্যই রিকার্সন সম্পর্কে ভালো ধারণা থাকতে হবে। সার্চস্পেসের আকার ছোটো হলে এটা খুবই কার্যকর একটা প...
Read More

ফ্লয়েডের সাইকেল ফাইন্ডিং অ্যালগোরিদম

তোমাকে একটা লিংকড লিস্ট দেয়া আছে, বলতে হবে লিংকড লিস্টে কোনো সাইকেল আছে নাকি। এটা খুবই কমন একটা ইন্টারভিউ প্রশ্ন, আমরা ফ্লয়েডের সাইকেল ফাইন্ডিং অ্যালগোরিদম দিয়ে এই সমস্যাটা সমাধান করা শিখবো। ছবির লিংকড লিস্টে দেখা যাচ্ছে ৭ দৈর্ঘ্যের একটা সাইকেল আছে। সাইকেল ডিটেক্ট করার সবথেকে সহজ উপায় হলো ডিকশনারি বা হ্যাশম্যাপ ব্যবহার করা। প্রথম নোড থেকে এক এক ঘর আগাতে হবে এবং প্রতিটা নোডকে ডিকশনারিতে সেভ করে রাখতে হবে। যদি কোনো নোডে গিয়ে দেখা যায় নোডটা আগে থেকেই ডিকশনারিতে আছে তাহলে বুঝতে হবে লিংকড লিস্টটা সাইক্লিক। এই অ্যালগোরিদমের টাইম কমপ্লেক্সিটি আর মেমরি কমপ্লেক্সিটি দুইটাই $O(n)$। ...
Read More

লংগেস্ট পাথ প্রবলেম

তোমাকে একটা আনওয়েটেড গ্রাফ এবং একটা সোর্স নোড দেয়া আছে। তোমাকে সোর্স নোড থেকে সর্বোচ্চ দৈর্ঘ্যের পাথ বের করতে হবে। এটাই হলো লংগেস্ট পাথ প্রবলেম। প্রশ্ন হলো কিভাবে প্রবলেমটা সলভ করবে? এটা আমার খুবই প্রিয় একটা ইন্টারভিউ প্রশ্ন। এখন পর্যন্ত প্রায় ৭-৮টা ইন্টারভিউতে আমি এই প্রশ্ন করেছি, মাত্র ২জন সহজেই উত্তর দিতে পেরেছে, ১জন হিন্টস দেয়ার পর পেরেছে, বাকিরা সবাই ভুল উত্তর দিয়েছে। অ্যালগোরিদম কোর্সে এ+ অনেকেই পায়, কিন্তু এধরণের প্রশ্ন করলে বোঝা যায় ক্যান্ডিডেট আসলে কতখানি জানে। প্রশ্নটা করার পর সবাই প্রথমে যে ভুল করে সেটা হলো জিজ্ঞেস করে না সর্বোচ্চ দৈর্ঘ্যের পাথের সংজ্ঞা কি, আমি চ...
Read More

অ্যালগোরিদম গেম থিওরি ৩ (স্প্র্যাগ-গ্রান্ডি সংখ্যা)

আমরা এখন নিম-গেম কিভাবে সমাধান করতে হয় জানি, এখন আমরা গ্রান্ডি সংখ্যা দিয়ে কিছু কম্পোজিট গেম এর সমাধান করবো। একটা গেম এর কথা চিন্তা করি যেখানে $s$ টা পাথরের একটা স্তুপ(pile) আছে, প্রতিবার কোনো খেলোয়াড় ১টা বা ২টা পাথর তুলে নিতে পারে, শেষ পাথরটা যে তুলে নিবে সে জিতবে। পাথরের সংখ্যা দেখে তোমাকে বলতে হবে অপটিমাল পদ্ধতিতে খেললে প্রথম খেলোয়াড় জিততে পারবে কিনা। প্রথম পর্ব পড়ে থাকলে এটা সমাধান করা তোমার জন্য খুবই সহজ। আমাদের সুডোকোডটা হবে এরকম: [crayon-5ba3faa6b39bb476456416/] এখন ধরো পাথরের স্তুপের সংখ্যা একটার বদলে যদি $n$ টা এবং প্রতিটা স্তুপে $s_1,s_2......s_n$ টা পাথর আছে। কোনো ...
Read More

ডাটা স্ট্রাকচার : লিংকড লিস্ট

লিংকড লিস্ট বেসিক একটা ডাটা স্ট্রাকচার। আমরা সাধারণত তথ্য রাখার জন্য অ্যারে ব্যবহার করি, তবে অ্যারের কিছু সীমাবদ্ধতা আছে যে কারণে অনেক সময় লিংকড লিস্ট ব্যবহারের দরকার হয়। লিংকড লিস্ট নিয়ে জানতে হলে অবশ্যই পয়েন্টার সম্পর্কে ধারণা থাকতে হবে। লিংক লিস্টের প্রতিটা এলিমেন্ট কে বলবো আমরা নোড। প্রতিটা নোডে সাধারণত দুইটা তথ্য থাকে: ১) যে তথ্যটা আমরা সংরক্ষণ করতে চাচ্ছি ২) পরবর্তি তথ্যটা কোথায় আছে তার ঠিকানা।   ছবিতে দেখা যাচ্ছে প্রথম নোড এ একজন ছাত্রের রোল নম্বর লেখা আছে, এবং পরবর্তি ছাত্রের তথ্য কোন নোড এ আছে সেটা দেখিয়ে দিচ্ছে next নামের একটা পয়েন্টার। দ্বিতীয় নোডটাই শেষ ন...
Read More

অ্যালগোরিদম গেম থিওরি-২ (নিম গেম)

আগের পর্বে গেম থিওরি কিছু বেসিক শিখেছি, এবারের পর্বে আমরা জানবো নিম-গেম নিয়ে। নিম-গেম খুবই গুরুত্বপূর্ণ কারণ অনেক ধরণের গেমকে নিম গেম এ রূপান্তর করে ফেলা যায়। নিম-গেম এ দুইজন খেলোয়ার আর কিছু পাথরের স্তুপ(pile) থাকে। প্রতি চালে একজন খেলোয়াড় যেকোনো একটা স্তুপ থেকে এক বা একাধিক পাথর তুলে নিতে পারে। কেও চাল দিতে ব্যার্থ হলে হেরে যাবে। অর্থাৎ শেষ পাথরটা যে তুলে নিয়েছে সে গেমে জিতবে। উপরের ছবিতে ৩টা পাথরের স্তুপ দেখা যাচ্ছে, প্রথমটায় ৬টা, দ্বিতীয়টায় ৯টা এবং তৃতীয়টায় ৩টা পাথর আছে। আগের গেমগুলার মতো এখানেও প্রত্যেক খেলোয়াড় অপটিমাল পদ্ধতিতে খেলবে, কেও কোনো ভুল চাল দিবে না। তোমাকে...
Read More

গ্রাফ থিওরিতে হাতেখড়ি ১৪ – স্ট্রংলি কানেক্টেড কম্পোনেন্ট

  একটা ডিরেক্টেট গ্রাফের স্ট্রংলি কানেক্টেড কম্পোনেন্ট বা SCC হলো এমন একটা কম্পোনেন্ট যার প্রতিটা নোড থেকে অন্য নোডে যাবার পথ আছে।  নিচের ছবিতে একটা গ্রাফের প্রতিটা স্ট্রংলি কানেক্টেড কম্পোনেন্ট আলাদা রঙ দিয়ে দেখানো হয়েছে। ডেপথ ফার্স্ট সার্চ এর ফিনিশিং টাইমের ধারণা ব্যবহার করে আমরা $O(V+E)$ তে একটা গ্রাফের স্ট্রংলি কানেক্টেড কম্পোনেন্ট গুলোকে আলাদা করে ফেলতে পারি। এই লেখাটা পড়ার আগে অবশ্যই টপলোজিকাল সর্টিং আর ডেপথ ফার্স্ট সার্চ এর ডিসকভারি এবং ফিনিশিং টাইম সম্পর্কে ধারণা থাকতে হবে। নিচের গ্রাফটা দেখ: প্রথমেই একটা ভুল পদ্ধতিতে অনেকে SCC বের করার চেষ্টা করে...
Read More