Author: শাফায়েত

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

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

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

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

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

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

রবিন-কার্প স্ট্রিং ম্যাচিং

রবিন-কার্প (Rabin-carp) একটি স্ট্রিং ম্যাচিং অ্যালগোরিদম। দুটি স্ট্রিং দেয়া থাকলে এই অ্যালগোরিদমটি বলে দিতে পারে যে ২য় স্ট্রিংটি প্রথম স্ট্রিং এর সাবস্ট্রিং কিনা। রবিন-কার্প রোলিং হ্যাশ টেকনিক ব্যবহার করে স্ট্রিং ম্যাচিং করে। যদিও স্ট্রিং ম্যাচিং এর জন্য কেএমপি অ্যালগোরিদম ব্যবহার করাই ভালো, কিন্তু রবিন-কার্প শেখা গুরুত্বপূর্ণ মূলত রোলিং হ্যাশ কিভাবে কাজ করে সেটা শেখার জন্য। এই লেখাটা পড়ার আগে মডুলার অ্যারিথমেটিক সম্পর্কে জেনে আসতে হবে। স্ট্রিং ম্যাচিং করার সময় প্রথম স্ট্রিং টাকে আমরা বলবো টেক্সট (Text) এবং দ্বিতীয়টিকে প্যাটার্ন (Pattern)। আমাদের কাজ হলো টেক্সট এর মধ্যে প্যাটার্ন...
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

Intro to Staircase Nim

Let's learn about Staircase Nim by solving move the coins problem that appeared in HackerRank April World Codesprint. Among the problems I have ever created, its one of my favorites. If you don't want to solve that problem but want to learn about staircase-nim, just read the first part of this blog. Lets start with some backgrounds. Staircase Nim This problem is a variation of Staircase Nim problem, which is a not-very-well-known variation of classic Nim problem. If you don't know what Nim Game is, I suggest you first to learn about it. In Staircase nim, there is a staircase with n...
Read More

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

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

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

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

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

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

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

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