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

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

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

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

অবজেক্ট ওরিয়েন্টেড প্রোগ্রামিং: ইন্টারফেস এবং পলিমর্ফিজম

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

টেইল-কল রিকার্শন অপটিমাইজেশন

রিকার্শন ব‍্যবহার করতে গেলে অনেক সময় দেখা যায় রিকার্শনের গভীরতা অনেক বেশি হয় গেলে মেমরি শেষ হয়ে যায় এবং কোড ক্র‍্যাশ করে। আমরা আজকে একটি অপটিমাইজেশন টেকনিক শিখবো যেটা ব‍্যবহার করে কোনো কোনো সময় রিকার্শনের মেমরি ব‍্যবহার অনেক কমিয়ে আনা সম্ভব। প্রথমে জানা দরকার টেইল-কল  (Tail call)  জিনিসটা কি। সহজভাবে বলতে গেলে, টেইল-কল হলো একটা ফাংশনের শেষ লাইন। অর্থাৎ যে কাজটি করার পর ফাংশনের আর কোনো কাজ থাকে না সেটাই টেইল-কল। যেমন নিজের ফাংশনটি দেখ: [crayon-5dcb606eb941f682788863/] এটা ফ‍্যাক্টরিয়াল বের করার একটি ফাংশন। এই ফাংশনে return ans  এর পর  ফাংশনটির আর কোনো কাজ নেই, তাই এটাই হলো টেইল...
বিস্তারিত

ট্রাভেলোকা এবং আমার সফটওয়্যার ইঞ্জিনিয়ারিং এ হাতেখড়ি

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

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

আজকে আমরা শিখবো কেএমপি (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$ হলো টেক্সট ও ...
বিস্তারিত

অয়লার ট্যুর (ফ্লিরি এবং হেয়ারহজলার অ্যালগরিদম)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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