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

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

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

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

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

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

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

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

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

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

গ্রাফ থিওরিতে হাতেখড়ি ১৩: আর্টিকুলেশন পয়েন্ট এবং ব্রিজ

আর্টিকুলেশন পয়েন্ট হলো আনডিরেক্টেড গ্রাফের এমন একটা নোড যেটা গ্রাফ থেকে মুছে ফেললে বাকি গ্রাফটুকু একাধিক কম্পোনেন্ট এ ভাগ হয়ে যায়।   উপরের ছবিতে ১, ৩ অথবা ৪ নম্বর নোড এবং সেই নোডের অ্যাডজেসেন্ট এজগুলোকে মুছে দিলে গ্রাফটা একাধিক ভাগ হয়ে যাবে, তাই ১, ৩ ও ৪ হলো এই গ্রাফের আর্টিকুলেশন পয়েন্ট। আর্টিকুলেশন পয়েন্টকে অনেকে কাট-নোড(cut node) , আর্টিকুলেশন নোড বা ক্রিটিকাল পয়েন্ট (critical point) ও বলে। আর্টিকুলেশন পয়েন্ট বের করার একটা খুব সহজ উপায় হলো, ১টা করে নোড গ্রাফ থেকে মুছে দিয়ে  দেখা যে গ্রাফটি একাধিক কম্পোনেন্ট এ বিভক্ত হয়ে গিয়েছে নাকি। [crayon-5d8099d862e8d372178...
বিস্তারিত

ডাটা স্ট্রাকচার : স্ট্যাক

যেকোনো ডাটা স্ট্রাকচার কোর্সে একদম শুরুর দিকে যেসব ডাটা স্ট্রাকচার পড়ানো হয় তার মধ্যে স্ট্যাক অন্যতম। স্ট্যাককে বলা হয় LIFO বা লাস্ট-ইন-ফার্স্ট-আউট ডাটা স্ট্রাকচার। তুমি এভাবে চিন্তা করতে পারো, তোমার কাছে অনেকগুলো বই একটার উপর আরেকটা সাজানো আছে, তুমি চাইলে সবার উপরের বইটা সরিয়ে ফেলতে পারো(Pop), অথবা সবার উপরে আরেকটা বই রাখতে পারো(Push)। এটা হলো বইয়ের একটা স্ট্যাক। তুমি এই স্ট্যাকের উপরে ছাড়া কোনো জায়গায় বই ঢুকাতে পারবে না, উপরের বই ছাড়া কোনো বই সরাতে পারবে না, এগুলো করলে সেটা আর স্ট্যাক থাকবে না। স্ট্যাক হলো কিছু বস্তুর(এলিমেন্ট) একটা সংগ্রহ। এখানে দুইরকম অপারেশন করা যায়: ...
বিস্তারিত

অ্যালগরিদম গেম থিওরি – ১

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

স্লাইডিং রেঞ্জ মিনিমাম কুয়েরি

মনে করো তোমাকে একটা অ্যারে দেয়া হয়েছে যেখানে $n$ টা সংখ্যা আছে। তোমাকে বলা হলো সেই অ্যারের m=৩ আকারের যতগুলো সাবঅ্যারে আছে সবগুলো থেকে সবথেকে ছোটো সংখ্যাটা বের করতে হবে। যেমন অ্যারেটা যদি হয় ১০,২,৫,৯,৬,৪ তাহলে m=৩ সাইজের সবগুলো সাবঅ্যারে হলো: ১০,২,৫ , সর্বনিম্ন সংখ্যা ২ ২,৫,৯ , সর্বনিম্ন সংখ্যা ২ ৫,৯,৬,  সর্বনিম্ন সংখ্যা ৫ ৯,৬,৪ , সর্বনিম্ন সংখ্যা ৪ তাহলে তোমার আউটপুট হবে [২,৫,৫,৪]। $m$ এর মান ৩ না হয়ে ১ থেকে $n$ পর্যন্ত যেকোনো সংখ্যা হতে পারে। $n$ এর মান যদি ছোটো হয় তাহলে আমরা সহজেই প্রতিটা সাবঅ্যারের উপর লুপ চালিয়ে সমস্যাটা সমাধান করতে পারি। নিচের পাইথন কোডটি দে...
বিস্তারিত

বাইনারি সার্চ – ২

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

বাইনারি সার্চ – ১

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

হাইস্কুল প্রোগ্রামিং প্রতিযোগিতার প্রাথমিক প্রস্তুতি

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

গ্রাফ থিওরিতে হাতেখড়ি-১২ – ম্যাক্সিমাম ফ্লো (২)

আগের পর্বে আমরা দেখেছি কিভাবে ফোর্ড-ফুলকারসন পদ্ধতি ব্যবহার করে ম্যাক্সিমাম ফ্লো বের করতে হয়। এই পর্বে ম্যাক্সিমাম ফ্লো সমস্যার সহজ কিছু ভ্যারিয়েশন দেখবো। একাধিক সোর্স/সিংক: আগের পর্বে একটা প্রশ্ন করেছিলাম এরকম "আমাদের প্রবলেমে সোর্স এবং সিংক ছিলো একটা। কিন্তু গ্রাফে একাধিক নোড দিয়ে পানি প্রবেশ করলে এবং একাধিক নোড দিয়ে পানি বের হয়ে গেলে কিভাবে অ্যালগোরিদমটা পরিবর্তন করবে?" অর্থাৎ একাধিক সোর্স বা সিংক থাকলে কি করতে হবে সেটা জানতে চাওয়া হয়েছে। চিত্র-১ এ বাম পাশের নীল নোডগুলো হলো সোর্স এবং ডানের সবুজ নোডগুলো হলো সিংক। চিত্র -১: একাধিক সোর্স এবং সিংক সহ একটি গ্রা...
বিস্তারিত

গ্রাফ থিওরিতে হাতেখড়ি ১২ – ম্যাক্সিমাম ফ্লো (১)

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