অ্যালগরিদম

সর্টিং থেকে ডায়নামিক প্রোগ্রামিং — ইন্টারেক্টিভ উদাহরণ সহ ধাপে ধাপে গাইড।

জটিলতা ও বিশ্লেষণ
অ্যালগরিদম কেন শিখবেন?
যেকোনো সার্চ রেজাল্ট, জিপিএস রুট বা রেকমেন্ডেশনের পেছনের জাদুকরী রেসিপি
→
বিগ-ও, থিটা, ওমেগা (Big-O, Theta, Omega)
অতিথির সংখ্যা বাড়লে আপনার রান্নার রেসিপি কতটা ধীর হয়ে যায়?
→
অ্যামোর্টাইজড অ্যানালাইসিস (Amortized Analysis)
একটি বড় বিল, ছোট ছোট কিস্তিতে পরিশোধ করা
→
রিকারেন্স রিলেশন (Recurrence Relations)
নিজে নিজেকে ডাকা একটি রেসিপি — সমাধান করতে পারার মতো সহজ না হওয়া পর্যন্ত
→
সর্টিং
বেসিক সোর্টস (Basic Sorts)
হাতের তাসগুলো সাজানো — তিনটি উপায়, একটি গতিপথ
→
মার্জ সর্ট (Merge Sort)
ভাগ করুন, প্রতি অর্ধেক সাজান, তারপর একত্রিত (merge) করুন — প্রতিবারই \(O(n \log n)\) এর নিশ্চয়তা
→
কুইক সর্ট (Quick Sort)
একটি পিভট (pivot) বেছে নিন, জনতাকে ভাগ করুন — ছোটরা বাঁয়ে, বড়রা ডানে
→
হিপ সর্ট (Heap Sort)
এমন একটি টুর্নামেন্ট ব্র্যাকেট যেখানে চ্যাম্পিয়ন সবসময় সবার ওপরে উঠে আসে
→
লিনিয়ার-টাইম সর্টিং (Linear-Time Sorting)
তুলনা ছাড়াই সর্ট করুন — \(O(n \log n)\) এর দেয়াল ভেঙে ফেলার কৌশল
→
কম্পারিজন লোয়ার বাউন্ড (Comparison Lower Bound)
কেন কোনো কম্পারিজন সর্ট (comparison sort) কখনোই \(O(n \log n)\)-কে হারাতে পারে না — তার একটি গাণিতিক প্রমাণ (mathematical proof)
→
সার্চিং ও সিলেকশন
বাইনারি সার্চ (Binary Search)
সমস্যাটিকে অর্ধেক করে ফেলুন — এবং তা প্রতিবারই
→
উত্তরের ওপর বাইনারি সার্চ (Binary Search on Answer)
যখন আপনি অ্যারেতে সার্চ করতে পারেন না — তখন সরাসরি উত্তরের ওপরই সার্চ করুন
→
এক্সপোনেনশিয়াল এবং ইন্টারপোলেশন সার্চ (Exponential & Interpolation Search)
প্রথমে পরিসীমা বা রেঞ্জ খুঁজে বের করুন, তারপর সেটিতে বাইনারি সার্চ চালান
→
কুইক-সিলেক্ট (QuickSelect)
পুরোপুরি না সাজিয়েই k-তম ছোট উপাদানটি খুঁজে বের করুন
→
মিডিয়ান অফ মিডিয়ানস (Median of Medians)
একটি নিশ্চিতভাবে ভালো পিভট — একদম প্রতিবার
→
ডিভাইড অ্যান্ড কঙ্কার
ডিভাইড অ্যান্ড কঙ্কার (D&C) প্যাটার্ন (Divide and Conquer Pattern)
সমস্যাটিকে ছোট ছোট টুকরাতে বিভক্ত করুন, টুকরোগুলোকে সমাধান করুন এবং তারপর সব ফলাফলগুলোকে একত্রিত করুন
→
ইনভার্সন গণনা (Count Inversions)
একটি সিকোয়েন্স (sequence) বা ক্রম ঠিক কতটা এলোমেলো অবস্থায় আছে তা পরিমাপ করুন — \(O(n \log n)\) সময়ে
→
ফাস্ট পাওয়ার বা দ্রুত ঘাত (Fast Power)
\(x^n\) গণনা করুন \(O(\log n)\) সময়ে — \(O(n)\) সংখ্যক গুণফল বা মাল্টিপ্লিকেশন নয়
→
কারাতসুবা গুণন (Karatsuba Multiplication)
প্রতিটি রিকার্সিভ লেভেলে ৪টির বদলে ৩টি গুণ — বড় সংখ্যার গুণের আধুনিক পদ্ধতি
→
ক্লোজেস্ট পেয়ার অফ পয়েন্টস (Closest Pair of Points)
একটি মানচিত্রে সবচেয়ে কাছের দুটি শহর খুঁজে বের করুন — প্রতিটি জোড়া পরিমাপ না করেই বা না মেপেই
→
গ্রিডি অ্যালগরিদম
গ্রিডি প্যাটার্ন বা লোভী পদ্ধতি (Greedy Pattern)
দাওয়াতের মাংসের সবচেয়ে বড় টুকরোটি সবসময় তুলে নিন — কখনো এটি সেরা সমাধান দেয়, আবার কখনো দেয় না
→
ইন্টারভাল শিডিউলিং (Interval Scheduling)
সর্বোচ্চ সংখ্যক মিটিং সিডিউল করুন — সবসময় সেই মিটিংটি আগে বেছে নিন যা সবচেয়ে আগে শেষ হয়
→
ফ্র্যাকশনাল ন্যাপস্যাক বা ভগ্নাংশ ন্যাপস্যাক (Fractional Knapsack)
একটি ব্যাকপ্যাক সোনার ধুলো দিয়ে ভরছেন — প্রতি গ্রামের সর্বোচ্চ মূল্যের বস্তু আগে নিন
→
হাফম্যান এনকোডিং (Huffman Encoding)
যে অক্ষরগুলো আপনি সবচেয়ে বেশি ব্যবহার করেন সেগুলোকে ছোট কোড দিন — ফাইলে জায়গা সাশ্রয় করুন
→
টাস্ক শিডিউলিং (Task Scheduling)
কাছের ডেডলাইন অনুযায়ী আগে কাজ করুন — কোনো কাজ মিস হবে না, সবচেয়ে বেশি লাভ হবে
→
এমএসটি (MST) — গ্রিডি দৃষ্টিভঙ্গি (Greedy Lens)
সবচেয়ে কম রাস্তা ব্যবহার করে সব শহর সংযুক্ত করুন — সবসময় সবচেয়ে সস্তা রাস্তাটি নিন যা কোনো লুপ তৈরি করে না
→
ডায়নামিক প্রোগ্রামিং
ডিপি প্যাটার্ন (DP Pattern)
একই পাজলের (puzzle) টুকরো বা সমস্যার সমাধান কখনোই দু'বার করবেন না — বরং সেটিকে লিখে রাখুন এবং দরকার হলে পরের বার সেখান থেকেই দেখে নিন
→
মেমোইজেশন বনাম ট্যাবুলেশন (Memoization vs Tabulation)
টপ-ডাউন (Top-down) হলো এমন এক বন্ধুর কাছে কল করা যে আবার অন্য এক বন্ধুকে কল করে। আর বটম-আপ (Bottom-up) হলো সারি ধরে ধরে একটি স্প্রেডশিট পূরণ করার মতো ব্যাপার।
→
1D ডিপি (1D DP)
সিঁড়ি বেয়ে ওপরে ওঠার মতোই — ধাপে ধাপে নিজের উত্তর তৈরি বা নির্মাণ করুন
→
0/1 ন্যাপস্যাক (0/1 Knapsack)
সর্বোচ্চ মূল্যের (value) জন্য একটি ব্যাগ বা স্যুটকেস প্যাক করুন — যেখানে প্রতিটি জিনিস বা আইটেম হয় পুরোপুরি নিতে হবে নতুবা একদমই নেওয়া যাবে না (all-or-nothing)
→
আনবাউন্ডেড ন্যাপস্যাক (Unbounded Knapsack)
প্রতিটি আইটেম যত খুশি ততবার নিতে পারেন — অনেকটা অফুরন্ত স্টকের কোনো বিশাল মুদি দোকানের মতো
→
লংগেস্ট কমন সাবসিকোয়েন্স বা দীর্ঘতম সাধারণ উপক্রম (Longest Common Subsequence)
দুটি সিকোয়েন্সের বা অনুক্রমের মধ্যে থাকা দীর্ঘতম একই অংশ বা গল্পটি খুঁজে বের করুন — যেখানে মাঝখানের কিছু অংশ এড়িয়ে যাওয়া বা স্কিপ (skip) করা সম্ভব
→
লংগেস্ট ইনক্রিজিং সাবসিকোয়েন্স বা দীর্ঘতম ক্রমবর্ধমান উপক্রম (Longest Increasing Subsequence)
একটি এলোমেলো অনুক্রমের বা সিকোয়েন্সের ভেতর লুকিয়ে থাকা দীর্ঘতম সিঁড়িটিকে খুঁজে বের করুন
→
এডিট ডিসট্যান্স (Edit Distance)
একটি শব্দকে অন্য শব্দে রূপান্তর করতে কতগুলো টাইপো-ফিক্স বা সংশোধনের প্রয়োজন হয়?
→
ম্যাট্রিক্স চেইন মাল্টিপ্লিকেশন (Matrix Chain Multiplication)
যে ক্রমে আপনি ম্যাট্রিক্স গুণ করেন তা অত্যন্ত গুরুত্বপূর্ণ — সবচেয়ে কম খরচের বা চিপেস্ট (cheapest) ক্রমটি খুঁজে বের করুন
→
ইন্টারভালের উপর ডিপি (DP on Intervals)
প্রথমে ছোট ছোট অংশগুলোকে সমাধান করুন, তারপর সেগুলোকে বড় অংশে একত্রিত করে ফেলুন বা মার্জ (merge) করুন
→
গাছে বা ট্রি-তে ডিপি (DP on Trees)
প্রতিটি নোডের উত্তর তার চাইল্ড বা সন্তানদের ওপর নির্ভর করে — নিচ থেকে ওপরে বা বটম-আপ পদ্ধতিতে হিসেব করুন
→
বিটমাস্ক ডিপি (Bitmask DP)
মাত্র একটি সিঙ্গেল পূর্ণসংখ্যায় বা ইনটিজারে সমস্ত সম্ভাব্য সাবসেটের পছন্দগুলো ট্র্যাক করুন
→
ডিজিট ডিপি (Digit DP)
ডিজিট বা অঙ্কের ক্ষেত্রে কোনো বাধা বা সীমাবদ্ধতা যুক্ত থাকলে সেই সংখ্যাগুলোকে গণনা করুন — প্রতিটিকে একে একে চেক না করেই
→
গ্রাফ অ্যালগরিদম
বিএফএস এবং ডিএফএস পুনর্বিবেচনা (BFS & DFS Revisited)
গ্রাফ অন্বেষণের দুটি উপায় — স্তর অনুযায়ী, অথবা একদম গভীরে গিয়ে
→
টপোলজিক্যাল সর্ট (Topological Sort)
কাজগুলোকে তাদের নির্ভরতা অনুযায়ী সাজান — ডিম আগে না মুরগি আগে, এমন দ্বন্দ্ব থাকবে না
→
ডাইকস্ট্রার অ্যালগরিদম (Dijkstra's Algorithm)
সর্বদা প্রথমে সবচেয়ে সস্তা রাস্তাটি বেছে নিন — গ্রাফের জন্য জিপিএস নেভিগেশন
→
বেলম্যান-ফোর্ড এবং এসপিএফএ (Bellman-Ford & SPFA)
নেগেটিভ ওয়েটগুলো হ্যান্ডেল করুন এবং নেগেটিভ সাইকেল ধরে ফেলুন
→
ফ্লয়েড-ওয়ার্শল অ্যালগরিদম (Floyd-Warshall)
এক চক্করে প্রতিটি শহরের জোড়ার মধ্যে সবচেয়ে ছোট পথ খুঁজে বের করুন
→
এ* (A*) সার্চ
ডাইকস্ট্রার চেয়ে বুদ্ধিমান — সঠিক দিকে এগোতে একটি ইঙ্গিত ব্যবহার করুন
→
টারজানের অ্যালগরিদম (Tarjan's Algorithm)
একটি ডিরেক্টেড গ্রাফের (directed graph) সমস্ত ঘনিষ্ঠভাবে যুক্ত গ্রুপকে (tightly-knit groups) একবার অতিক্রম করেই (one pass) খুঁজে বের করুন
→
কোসারাজু অ্যালগরিদম (Kosaraju's Algorithm)
দুটি চমৎকার গ্রাফ সার্চের মাধ্যমে পরস্পর সংযুক্ত বা 'mutual-follow' গ্রুপ খুঁজে বের করুন
→
অয়লারীয় পথ ও সার্কিট (Eulerian Path & Circuit)
আপনি কি প্রতিটি সেতু বা ব্রিজ ঠিক একবার করে পার হতে পারবেন? ১৭৩৬ সালে অয়লার এই প্রশ্নের উত্তর দিয়েছিলেন
→
হ্যামিল্টোনীয় পথ (Hamiltonian Path)
প্রতিটি ঘর ঠিক একবার করে ভ্রমণ করুন — এটি প্রতিটি সেতু ভ্রমণের চেয়ে অনেক বেশি কঠিন
→
নেটওয়ার্ক ফ্লো
ম্যাক্স ফ্লো / মিন কাট (Max Flow / Min Cut)
আপনার পাইপের নেটওয়ার্ক দিয়ে কতটুকু পানি যেতে পারবে? সেটির সিদ্ধান্ত নেবে বটলনেক (bottleneck) বা সরু পথটি
→
এডমন্ডস-কার্প (Edmonds-Karp)
BFS সহকারে ফোর্ড-ফুলকারসন (Ford-Fulkerson) — গ্যারান্টিযুক্ত পলিনোমিয়াল টাইম বা বহুপদী সময় (polynomial time), যেখানে কোনো অসীম চক্র বা ইনফিনিট লুপ (infinite loops) থাকে না
→
ডিনিকের অ্যালগরিদম (Dinic's Algorithm)
এক ধাপে সমস্ত ক্ষুদ্রতম অগমেন্টিং পাথগুলো (augmenting paths) একসাথে বা ব্যাচে (batch) সম্পন্ন করে — যা একটি একটি করে বের করার চেয়ে নাটকীয়ভাবে দ্রুতগতির
→
বাইপার্টাইট ম্যাচিং (Bipartite Matching)
ইন্টার্নশিপগুলোর সাথে শিক্ষার্থীদের মেলান — সুখী জুটির সর্বোচ্চ সংখ্যা খুঁজে বের করুন
→
হাঙ্গেরিয়ান অ্যালগরিদম (Hungarian Algorithm)
সর্বনিম্ন খরচে কর্মীদের কাজ বরাদ্দ করুন — নিখুঁত সমন্বয় বা পারফেক্ট ম্যাচ
→
স্ট্রিং অ্যালগরিদম
কেএমপি অ্যালগরিদম (KMP Algorithm)
স্ট্রিং বা লেখা খোঁজার সময় কখনোই পিছনে ফিরবেন না — পুরনো জ্ঞান কাজে লাগিয়ে এগিয়ে যান
→
রবিন-কার্প (Rabin-Karp)
ফিঙ্গারপ্রিন্ট দিয়ে বইয়ের ভেতর শব্দ খুঁজুন — কেবল ফিঙ্গারপ্রিন্ট মিললেই অক্ষর ধরে ধরে মিলিয়ে দেখুন
→
জেড-অ্যালগরিদম (Z-Algorithm)
জেড-অ্যারে (Z-array): প্রতিটি অবস্থানে হিসাব মেলানোর দৈর্ঘ্য — লিনিয়ার প্যাটার্ন ম্যাচিং
→
বয়ার-মুর (Boyer-Moore)
প্যাটার্নটি পিছন থেকে পড়ুন, এবং বড় বড় অংশ বাদ দিয়ে যান — বাস্তবে সাবলিনিয়ার (sublinear) পারফরম্যান্স
→
সাফিক্স অ্যারে কনস্ট্রাকশন (Suffix Array Construction)
সমস্ত সাফিক্স বা প্রত্যয় সাজানো — O(m log n) সাবস্ট্রিং সার্চ
→
আহো-কোরাসিক (Aho-Corasick)
একসাথে সব প্যাটার্ন খুঁজুন — এক পাস, O(n + matches)
→
র‍্যান্ডমাইজড অ্যালগরিদম
লাস ভেগাস বনাম মন্টি কার্লো (Las Vegas vs Monte Carlo)
সর্বদা-সঠিক বনাম সম্ভাব্য-সঠিক — র্যান্ডমাইজড অ্যালগরিদমের (randomized algorithms) দুটি ভিন্ন স্বাদ
→
র‍্যান্ডমাইজড কুইক সর্ট (Randomized Quick Sort)
একটি র‍্যান্ডম পিভট প্রতিকূল সবচেয়ে খারাপ ক্ষেত্রের ইনপুটগুলো ধ্বংস করে দেয়
→
রিজার্ভার স্যাম্পলিং (Reservoir Sampling)
এমন একটি স্ট্রিম থেকে ন্যায্যভাবে k টি আইটেমের নমুনা নিন যা আপনি কেবল একবারই দেখেন
→
স্কিপ লিস্ট (Skip List)
প্রোবাবিলিস্টিক বিএসটি-র বিকল্প — প্রত্যাশিত সময় O(log n)
→
ব্লুম ফিল্টার (Bloom Filter)
সম্ভবত হ্যাঁ, নিশ্চিতভাবে না — একটি মেমরি-সাশ্রয়ী মেম্বারশিপ পরীক্ষক
→
অ্যাডভান্সড টপিক
ব্যাকট্র্যাকিং (Backtracking)
প্রতিটি সম্ভাব্য পথ ঘুরে দেখুন, তবে ডেড এন্ড বা অন্ধগলি পেলেই পেছনে ফিরে আসুন
→
ব্রাঞ্চ অ্যান্ড বাউন্ড (Branch & Bound)
ভবিষ্যত দেখার ক্ষমতাসহ ব্যাকট্র্যাকিং (Backtracking) — যে শাখাগুলো বা ব্রাঞ্চ কোনোভাবেই জিততে পারবে না, সেগুলোকে কেটে ছেঁটে ফেলুন (prune)
→
অ্যাপ্রক্সিমেশন অ্যালগরিদম (Approximation Algorithms)
১% সময়ে ৯০% কাছাকাছি পৌঁছানো — সাথে গাণিতিক প্রমাণ
→
এনপি (NP), এনপি-কমপ্লিট (NP-Complete), এনপি-হার্ড (NP-Hard)
দ্য মিলিয়ন-ডলার প্রশ্ন: কোনো উত্তর খুঁজে বের করা কি কখনো তা যাচাই করার মতো সহজ হতে পারে?
→
বিট ম্যানিপুলেশন (Bit Manipulation)
বিদ্যুতের গতিতে সুইচ উল্টান বা ফ্লিপ (flip) করুন — এবং তা করুন \(O(1)\) সময়ে
→
মো-এর অ্যালগরিদম (Mo's Algorithm)
রেঞ্জ কুয়েরিগুলোকে (range queries) ক্রমানুসারে উত্তর দেওয়ার বদলে সেগুলোকে বুদ্ধিমানের মতো সাজিয়ে হাজার হাজার কুয়েরির উত্তর দিন
→
স্কয়ার রুট ডিকম্পোজিশন (Sqrt Decomposition)
অ্যারেকে √n আকারে ভাগ করুন — প্রতিটা উপাদান চেক করার জন্য খুব বড়, আবার জটিল ট্রি বানানোর জন্য খুব ছোট
→