শাফায়েতের ব্লগ

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

(সবগুলো পর্ব) ডাইনামিক প্রোগ্রামিং দিয়ে ট্রি(Tree) সংক্রান্ত অনেক সমস‍্যার সমাধান করা যায়। সাধারণ গ্রাফে পলিনোমিয়াল টাইমে সমাধান করা যায় না এমন অনেক প্রবলেম ট্রি গ্রাফে সহজেই ডাইনামিক প্রোগ্রামিং দিয়ে সমাধান করা যায় কারণ ট্রি তে কোন সাইকেল থাকে না। এই পর্বে আমরা সেরকমই একটা ক্লাসিক প্রবলেম দেখবো যার নাম মিনিমাম ভারটেক্স কভার। ধরা যাক একটি শহরে কিছু রাস্তা আছে, এখন প্রতি রাস্তায় মোড় বা জাংশনে আমরা পাহারাদার বসাতে চাই। কোনো মোড়ে পাহারাদার বসালে সে মোড়ের সাথে যুক্ত রাস্তাগুলো একাই পাহারা দিতে পারে। এখন তোমাকে বলতে হবে সব কয়টা রাস্তা পাহারা দিতে নূন্যতম কয়জন পাহারাদার দরকার? একট...

(সবগুলো পর্ব) বিটমাস্ক ব‍্যবহার করে বেশ কিছু NP-Complete/NP-Hard প্রবলেম সলভ করা যায়। বিটমাস্কের ব‍্যবহার জানা থাকলে এটা তেমন কঠিন কিছু নয়। এই লেখা পড়ার আগে তোমার জানা লাগবে কিভাবে বিট ম‍্যানিপুলেশন করতে হয়, সেজন‍্য তুমি এই লেখাটা পড়তে পারো। এই প্রবলেম সলভ করতে গ্রাফ থিওরি জানার দরকার নেই। আজকে আমরা বিখ‍্যাত ট্রাভেলিং সেলসম‍্যান প্রবলেম বিটমাস্ক দিয়ে সলভ করবো।  প্রবলেমটা হলো তোমাকে কিছু শহর এবং রাস্তা একটা গ্রাফ হিসাবে দেয়া আছে। তোমাকে প্রথম শহর থেকে শুরু করে সবগুলো শহর ঠিক একবার করে ভ্রমণ করে প্রথম শহরে ফিরে আসতে হবে। প্রশ্ন হলো সর্বনিম্ন কত দূরত্ব অতিক্রম করে তুমি কাজটা করতে পারব...

(সবগুলো পর্ব) ম‍্যাট্রিক্স চেইন মাল্টিপ্লিকেশন আরেকটা ক্লাসিক ডাইনামিক প্রোগ্রামিং প্রবলেম যেখানে আমাদেরকে বের করতে হবে কিছু ম‍্যাট্রিক্সকে কিভাবে সবথেকে কম অপারেশন ব‍্যবহার করে গুণ করা যাবে।  ডিভাইড এন্ড কনকোয়ার পদ্ধতির খুবই চমৎকার একটা উদাহরণ এই প্রবলেমটা। আমি আশা করবো ম‍্যাট্রিক্স কিভাবে গুণ করতে হয় সেটা সবাই জানো, আমি সেটা নিয়ে বিস্তারিত বলবো না। আমি খালি কয়েকটা প্রোপার্টির কথা মনে করিয়ে দিতে চাই। ধরা যাক আমাদের দুটি ম‍্যাট্রিক্স আছে $A_{1}$ এবং $A_{2}$ এবং তাদের ডাইমেনশন হলো $(r_{1} \times c_{1})$ এবং $(r_{2} \times c_{2})$। $A_{1}$ এবং $A_{2}$ গুণ করা যাবে শুধুমাত্র যদি $...

আগের পর্বগুলোয় যেসব প্রবলেম দেখেছি তার মধ‍্যে ফিবোনাচ্চি সবগুলোতেই আমাদেরকে কিছু না কিছু ম‍্যাক্সিমাইজ বা মিনিমাইজ করতে হয়। এগুলো ছাড়া ডাইনামিক প্রোগ্রামিং এর আরো কিছু ব‍্যবহার আছে, একটা হলো কোন একটা কাজ কত ভাবে করা যায় সেটা বের করা, আরেকটা হলো ডিসিশন প্রবলেম সলভ করা (অর্থাৎ কোন একটা কাজ করা যাবে কি যাবে না সেটা বের করা)। শুরুতেই দেখবো সাবসেট সাম প্রবলেম। এই প্রবলেমটা অনেকটাই কয়েন চেঞ্জ প্রবলেমের মত, আশা করবো তুমি কয়েন চেঞ্জ নিয়ে লেখাটা পড়ে ফেলেছো, কারণ এবার আমি আগের মত এত বিস্তারিত বর্ণনা করবো না। সাবসেট সাম তোমাকে একটা ইন্টিজার অ‍্যারে $C$ দেয়া আছে এবং একটা ভ‍্যালু $W$ দে...