ডাইনামিক প্রোগ্রামিং ৯ (ট্রি, মিনিমাম ভারটেক্স কভার)

(সবগুলো পর্ব) ডাইনামিক প্রোগ্রামিং দিয়ে ট্রি(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$ দে...
বিস্তারিত

ডাইনামিক প্রোগ্রামিং ৫ (কয়েন চেঞ্জ, ০-১ ন‍্যাপস‍্যাক)

(আগের পর্ব) আজকে আরো দুটি ক্লাসিকাল ডাইনামিক প্রোগ্রামিং প্রবলেম শিখবো। প্রথমটা হলো কয়েন চেঞ্জ। প্রবলেমটার নাম শুনেই বোঝা যাচ্ছে এটা টাকা ভাংতি করা নিয়ে প্রবলেম, তোমাকে সবথেকে কম সংখ‍্যক কয়েন ব‍্যবহার করে নির্দিষ্ট পরিমাণ টাকা ভাংতি করতে হবে। মনে করো তোমার কাছে $n$ টা ভিন্ন ভিন্ন কয়েন আছে, কয়েনগুলোর ভ‍্যালুকে $C_{0},  C_{1}...C{n-1}$ দিয়ে প্রকাশ করা যায়। আর তোমাকে  একটা অ‍্যামাউন্ট দেয়া আছে $W$। এখন  তোমাকে বলতে সর্বনিম্ন কয়টা কয়েন ব‍্যবহার করে তুমি $W$ অ‍্যামাউন্টটা বানাতে পারবে। প্রতিটা ভ‍্যালুর কয়েন আছে মাত্র ১টা করে। একটা উদাহরণ দেখি। ধরা যাক কয়েনগুলোর ভ‍্যালু হলো $C = \...
বিস্তারিত

ডাইনামিক প্রোগ্রামিং ৪ (লংগেস্ট কমন সাবসিকোয়েন্স)

আগের পর্ব গুলোতে আমরা যেসব প্রবলেম দেখে এসেছি সেগুলোর সাবপ্রবলেমের স্টেট ছিল মাত্র ১টা। এইবার আমরা আরেকটু জটিল সমস‍্যা সমাধান করবো যার নাম লংগেস্ট কমন সাবসিকোয়েন্স বা LCS। এটা শেখার পরে আমি এডিট ডিসটেন্স প্রবলেম নিয়ে অল্প কিছু কথা বলবো এবং তোমার কাজ হবে সেটা নিজে নিজে সমাধান করা। এই প্রবলেমে তোমাকে দুটি স্ট্রিং দেয়া থাকবে $S$ এবং $W$। তোমাকে তাদের মধ‍্যে লংগেস্ট কমন সাবসিকোয়েন্স এর দৈর্ঘ‍্য বের করতে হবে। সাবসিকোয়েন্সের সংজ্ঞাটা মনে করিয়ে দেই, একটা স্ট্রিং থেকে কিছু ক‍্যারেক্টার মুছে দিলে যা বাকি থাকে সেটাই স্ট্রিংটা সাবসিকোয়েন্স। একটা স্ট্রিং এর $2^{n}$ টা সাবসিকোয়েন্স থাকতে পার...
বিস্তারিত

ডাইনামিক প্রোগ্রামিং-৩ (লংগেস্ট ইনক্রিজিং সাবসিকোয়েন্স, পাথ প্রিন্টিং)

আমরা এরই মধ‍্যে ডাইনামিক প্রোগ্রামিং এর বেসিক শিখে গিয়েছি, আমরা ফিবোনাচ্চি এবং DAG এ শর্টেস্ট পাথ বের করতে পারি। এবার আমরা শিখবো Longest Increasing Subsequence বা LIS বের করা। এতদিন আমরা শুধু অপটিমাল সলিউশনটা বের করতে শিখেছি, কোন পথ ধরে সলিউশনে পৌছাতে হয় সেটা বের করা শিখিনি। এবার আমরা নেক্সট-পয়েন্টার ব‍্যবহার করে সেটা বের করাও শিখবো। ধরা যাক আমাদের নিচের ছবির মতো একটা অ‍্যারে আছে যার নাম $A$। একটা অ‍্যারের সাবসিকোয়েন্স বলতে বুঝায় অ‍্যারে থেকে কিছু এলিমেন্ট মুছে দিলে বাকি যে সিকোয়েন্সটা থাকে সেটা। এলিমেন্টগুলোর অর্ডারিং পরিবর্তন করা যাবে না। $n$ সাইজের একটা অ‍্যারের $2^{n}$ টি স...
বিস্তারিত

ডাইনামিক প্রোগ্রামিং-২ (শর্টেস্ট পাথ)

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

ডাইনামিক প্রোগ্রামিং – ১ (ফিবোনাচ্চি)

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

প্রোবাবিলিস্টিক ডাটা স্ট্রাকচার: কাউন্ট-মিন স্কেচ

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

ক‍্যাশিং অ‍্যালগরিদম: এল-আর-ইউ ক‍্যাশ

আজকে আমরা জানবো ক‍্যাশিং কি এবং এল-আর-ইউ ক‍্যাশ কিভাবে কাজ করে। তুমি যদি ক‍্যাশিং সম্পর্কে আগে থেকেই জানো তাহলে প্রথম অংশটা দ্রুত পড়ে পরের অংশে চলে যেতে পারো। ধরা যাক তুমি একটি অ‍্যান্ড্রয়েড অ‍্যাপ তৈরি করছো। অ‍্যাপের ইউজারদের তুমি ৩টা রকমের লেভেল অ‍্যাসাইন করেছো, প্লাটিনাম, গোল্ড আর সিলভার। যখনই কোনো ইউজার অ‍্যাপ চালু করে তখনই তোমার ডেটাবেসে ইউজারের লেভেল চেক করতে হয়। তোমার অ‍্যাপ এ ইউজার আছে এক লাখ এবং প্রতি ঘন্টায় কয়েক হাজার ইউজার অ‍্যাপটি ব‍্যবহার করে। একসময় তুমি দেখলে ডাটাবেজের রিকুয়েস্ট খুব বেশি বেড়ে যাচ্ছে এবং পেজ লোড স্লো হয়ে যাচ্ছে। এই সমস‍্যার সমাধান হলো কিছু ইউজারের ...
বিস্তারিত

প্রোবাবিলিস্টিক ডাটা স্ট্রাকচার: ব্লুম ফিল্টার

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

বাগ ফ্রি কোডিং – অপরিবর্তনীয় বা ইমিউটেবল ভ‍্যারিয়েবল

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

স্কয়ার-রুট ডিকম্পোজিশন

স্কয়ার-রুট ডিকম্পোজিশন টেকনিক ব‍্যবহার করে বেশ কিছু প্রবলেমের টাইম কমপ্লেক্সিটি $O(Sqrt(n))$ এ নামিয়ে আনা যায়। একটা উদাহরণ দিয়ে শুরু করি। ধরা যাক তোমাকে একটা ইন্টিজার অ‍্যারে দেয়া আছে এবং কিছু অপারেশন দেয়া আছে। অপারেশন দুই ধরণের হতে পারে, একটা হলো $[l, r]$ ইনডেক্সের ভিতর সবগুলো সংখ‍্যার যোগ ফল বের করতে হবে, অন‍্যটা হলো i তম ইনডেক্সের মান আপডেট করতে হবে। অনেকে হয়তো সেগমেন্ট ট্রি বা বাইনারি ইনডেক্সড ট্রি ব‍্যবহার করে এটা সমাধান করতে পারবে। আজকে আমরা এটা সমাধান করার আরেকটা নতুন পদ্ধতিতে শিখবো। একেবারেই সাধারণ পদ্ধতিতে আমরা কি করবো? প্রতিবার যোগফল বের করতে বললে $[l, r]$ রেঞ্জে একট...
বিস্তারিত