প্রোগ্রামিং কনটেস্ট ডেটা স্ট্রাকচার ও অ্যালগরিদম

ভূমিকা

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

তরুণ প্রজন্মের মধ্যে আমার দেখা সর্বশ্রেষ্ঠ শিক্ষক মনে হয় মনিরুল হাসান (তমাল)। কিন্তু আরেকটু তরুণ প্রজন্মের মধ্যে যদি খুঁজে দেখি তাহলে দুটো নামই মাথায়ে আসে- মোহাম্মদ মাহমুদুর রহমান এবং মোঃ মাহবুবুল হাসান শান্ত। মোটামুটি ভালো শিক্ষক হলেই যে সবসময় ভালো লেখক হয়না সেটা নিজেকে দিয়েই বুঝি কিন্তু শান্ত তার বুঝানোর ক্ষমতাকে বই এর মধ্যে আনতে পেরেছে ভালোভাবেই তাই এই বইটি তরুণ প্রজন্মের জন্য অনেক উপকারী হবে সন্দেহ নেই। আজকে কেবলই মনে হচ্ছে কেন আমার বয়স আরো বিশ বছর কম হলো না, তাহলে এই বই দেখে আরো ভালোভাবে সবকিছু অনেক কম বয়সে শিখে ফেলতে পারতাম।

শান্তর প্রোগ্রামিং কনটেস্ট ক্যারিয়ার অনেক দীর্ঘ। তবে তাকে প্রথম ভালো ভাবে চিনি যখন “Dhaka Regional ২০০৫” এ শান্ত ও নাফি এর IOI গামী দল বাংলাদেশের সব বিশ্ববিদ্যালয়কে পেছনে ফেলে দ্বিতীয় স্থান দখল করে। “Lattice triangle” গণনার একটি সমস্যা সমাধান করে তারা সবাইকে তাক লাগিয়ে দিয়েছিল। সৌভাগ্যক্রমে সেই প্রবলেমের স্রষ্টা ছিলাম আমি। ভিসা জটিলতার কারণে তাদের IOI এ অংশগ্রহন করা হয় নাই, নাহলে বাংলাদেশের IOI পদক অনেক আগেই আসতে পারত। শান্ত সম্ভবত এখনো নানান কনটেস্টে অংশগ্রহন করে, তাই তার চেয়ে দীর্ঘ কনটেস্ট ক্যারিয়ার খুব কম লোকেরই আছে। তার উপর শান্তর রয়েছে সমস্যার সমাধান করার সীমাহীন উৎসাহ ও ধৈর্য। জনশ্রুতি রয়েছে যে শান্ত তার বিয়ের দিনও বিভিন্ন সমস্যার সমাধান করেছে। কাজেই এত দীর্ঘ ক্যারিয়ার ও সময়ে শান্ত কী পরিমান সমস্যা সমাধান করেছে তা আন্দাজ করাও অনেকের পক্ষে কঠিন হবে। এই বইয়ে তাই নানা ধরনের সমস্যা সমাধান এর কথা উঠে এসেছে। বাংলা ভাষায় এমন বই আগে প্রকাশিত হয়নি এমনকি ইংরেজিতে অনুদিত হলেও এই বই যথেষ্ট সমাদৃত হবে বলে আমার বিশ্বাস।

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

সূচিপত্র

অধ্যায় ১ – প্রোগ্রামিং প্রতিযোগিতায় হাতেখড়ি

• ১.১ শুরুর কথা
• ১.২ প্রোগ্রামিং প্রতিযোগিতা কী?
• ১.৩ কেন করব?
• ১.৪ কীভাবে শুরু করব?
• ১.৫ কী কী জানতে হবে?

অধ্যায় ২ – C ঝালাই

• ২.১ একটি ছোট প্রোগ্রাম এবং ইনপুট আউটপুট
• ২.২ ডেটা টাইপ এবং math.h হেডার ফাইল
• ২.৩ if – else if – else
• ২.৪ লুপ (Loop)
• ২.৫ অ্যারে (Array) ও স্ট্রিং (String)
• ২.৬ টাইম কমপ্লেক্সিটি (Time Complexity) এবং মেমোরী কমপ্লেক্সিটি (Memory Complexity)
• ২.৭ ফাংশন এবং রিকার্শন (Recursion)
• ২.৮ ফাইল (File) ও স্ট্রাকচার (Structure)
• ২.৯ বিটওয়াইজ অপারেশন (bitwise operation)

অধ্যায় ৩ – গণিত

• ৩.১ সংখ্যাতত্ত্ব (Number Theory)
  • ৩.১.১ মৌলিক সংখ্যা (Prime Number)
  • ৩.১.২ একটি সংখ্যার গুণনীয়কসমূহ
  • ৩.১.৩ গ.সা.গু. (GCD) ও ল.সা.গু. (LCM)
  • ৩.১.৪ অয়লার এর টোশেন্ট ফাংশন (Euler’s Totient Function)
  • ৩.১.৫ BigMod
  • ৩.১.৬ মডুলার ইনভার্স (Modular Inverse)
  • ৩.১.৭ Extended GCD
• ৩.২ কম্বিনেটরিক্স (Combinatorics)
  • ৩.২.১ ফ্যাক্টোরিয়ালের পেছনের 0
  • ৩.২.২ ফ্যাক্টোরিয়ালের অঙ্ক (Digit) সংখ্যা
  • ৩.২.৩ সমাবেশ (Combination)
  • ৩.২.৪ কিছু বিশেষ সংখ্যা
    • ডিরেঞ্জমেন্ট সংখ্যা (Derangement Number)
    • কাটালান সংখ্যা (Catalan Number)Stirling Number of Second Kind
    • Stirling Number of First Kind
  • ৩.২.৫ ফিবোনাচি সংখ্যা (Fibonacci Number)
  • ৩.২.৬ ইনক্লুশন এক্সক্লুশন নীতি (Inclusion Exclusion Principle)
• ৩.৩ সম্ভাব্যতা (Probability) ও এক্সপেক্টেশন (Expectation)
  • ৩.৩.১ সম্ভাব্যতা (Probability)
  • ৩.৩.২ এক্সপেক্টেশন (Expectation)
• ৩.৪ বিবিধ
  • ৩.৪.১ ভিত্তি পরিবর্তন (Base Conversion)
  • ৩.৪.২ বিগ ইন্টিজার (Big Integer)
  • ৩.৪.৩ চক্র বা সাইকেল (Cycle) নির্ণয়ের অ্যালগরিদম
  • ৩.৪.৪ গাউসের এলিমিনেশন (Gaussian elimination)
• ৩.৫ প্রোগ্রামিং সমস্যা
  • ৩.৫.১ অনুশীলনী

অধ্যায় ৪ – সর্টিং (Sorting) ও সার্চিং (Searching)

• ৪.১ সর্টিং (Sorting)
  • ৪.১.১ ইনসার্শন সর্ট (Insertion Sort)
  • ৪.১.২ সিলেকশন সর্ট (Selection Sort)
  • ৪.১.৩ বাবল সর্ট (Bubble Sort)
  • ৪.১.৪ মার্জ সর্ট (Merge Sort)
  • ৪.১.৫ কাউন্টিং সর্ট (Counting Sort)
  • ৪.১.৬ STL এর sort ফাংশন
• ৪.২ বাইনারি সার্চ (Binary Search)
• ৪.৩ টারনারি সার্চ(Ternary Search)
• ৪.৪ ব্যাকট্র্যাকিং (Backtracking)
  • ৪.৪.১ সবরকম বিন্যাস বের করা (Permutation Generation)
  • ৪.৪.২ সবরকম সমাবেশ বের করা (Combination Generation)
  • ৪.৪.৩ Eight Queen সমস্যা
  • ৪.৪.৪ Knapsack সমস্যা
• ৪.৫ প্রোগ্রামিং সমস্যা
  • ৪.৫.১ অনুশীলনী

অধ্যায় ৫- ডেটা স্ট্রাকচার

• ৫.১ লিঙ্কড লিস্ট (Linked List)
• ৫.২ স্ট্যাক (Stack)
  • ৫.২.১ 0-1 ম্যাট্রিক্সে সব 1-ওয়ালা সবচেয়ে বড় আয়তক্ষেত্র
• ৫.৩ কিউ (Queue)
• ৫.৪ গ্রাফ (graph) এর উপস্থাপন
• ৫.৫ ট্রি (Tree)
• ৫.৬ বাইনারি সার্চ ট্রি (Binary Search Tree – BST)
• ৫.৭ হীপ (Heap) বা প্রায়োরিটি কিউ (Priority Queue)
• ৫.৮ ডিসজয়েন্ট সেট ইউনিয়ন (Disjoint set Union)
• ৫.৯ Square Root segmentation
• ৫.১০ স্ট্যাটিক (Static) ডেটাতে কুয়েরি
• ৫.১১ সেগমেন্ট ট্রি (Segment Tree)
  • ৫.১১.১ সেগমেন্ট ট্রি তৈরী করা
  • ৫.১১.২ সেগমেন্ট ট্রি আপডেট করা
  • ৫.১১.৩ সেগমেন্ট ট্রি তে কুয়েরি করা
  • ৫.১১.৪ Lazy without Propagation
  • ৫.১১.৫ Lazy With Propagation
  • ৫.১১.৬ একটি উদাহরণ
• ৫.১২ বাইনারি ইনডেক্সড ট্রি (Binary Indexed Tree)
• ৫.১৩ প্রোগ্রামিং সমস্যা
  • ৫.১৩.১ অনুশীলনী

অধ্যায় ৬ – গ্রীডি টেকনিক (Greedy Technique)

• ৬.১ Fractional Knapsack
• ৬.২ মিনিমাম স্প্যানিং ট্রি (Minimum Spanning Tree)
  • ৬.২.১ প্রিম এর অ্যালগরিদম (Prim’s Algorithm)
  • ৬.২.২ ক্রুসকাল এর অ্যালগরিদম (Kruskal’s Algorithm)
• ৬.৩ ওয়াশিং মেশিন ও ড্রায়ার
• ৬.৪ হাফম্যান কোডিং (Huffman Coding)
• ৬.৫ প্রোগ্রামিং সমস্যা
  • ৬.৫.১অনুশীলনী

অধ্যায় ৭ – ডায়নামিক প্রোগ্রামিং (Dynamic Programming)

• ৭.১ আবারও ফিবোনাচি
• ৭.২ কয়েন চেঞ্জ (Coin Change)
  • ৭.২.১Variant 1
  • ৭.২.২ Variant 2
  • ৭.২.৩ Variant 3
  • ৭.২.৪ Variant 4
  • ৭.২.৫ Variant 5
• ৭.৩ ট্রাভেলিং সেলসম্যান সমস্যা (Travelling Salesman Problem)
• ৭.৪ দীর্ঘতম ক্রমবর্ধমান সাবসিকোয়েন্স (Longest Increasing Subsequence)
• ৭.৫ দীর্ঘতম সাধারণ সাবসিকোয়েন্স (Longest Common Subsequence)
• ৭.৬ ম্যাট্রিক্স চেইন মাল্টিপ্লিকেশন (Matrix Chain Multiplication)
• ৭.৭ অপটিমাল বাইনারি সার্চ ট্রি (Optimal Binary Search Tree)
• ৭.৮ প্রোগ্রামিং সমস্যা
  • ৭.৮.১ অনুশীলনী

অধ্যায় ৮ – গ্রাফ

• ৮.১ ব্রেডথ ফার্স্ট সার্চ (Breadth First Search – BFS)
• ৮.২ ডেপথ ফার্স্ট সার্চ (Depth First Search – DFS)
• ৮.৩ DFS ও BFS এর কিছু সমস্যা
  • ৮.৩.১ কম্পোনেন্ট (Component) বের করা
  • ৮.৩.২ দুটি নোডের দূরত্ব
  • ৮.৩.৩ তিনটি গ্লাস ও পানি
  • ৮.৩.৪ UVa 10653
  • ৮.৩.৫ UVa 10651
  • ৮.৩.৬ 0 ও 1 মূল্য (cost) এর গ্রাফ
• ৮.৪ সিঙ্গল সোর্স শর্টেস্ট পাথ (Single Source Shortest Path)
  • ৮.৪.১ ডায়াকস্ট্রা’র অ্যালগরিদম (Dijkstra’s Algorithm)
  • ৮.৪.২ বেলম্যান ফোর্ড অ্যালগরিদম (Bellman Ford Algorithm)
• ৮.৫ অল পেয়ার শর্টেস্ট পাথ (All pair shortest path) বা ফ্লয়েড ওয়ার্শাল অ্যালগরিদম (Floyd Warshall Algorithm)
• ৮.৬ ডায়াকস্ট্রা, বেলম্যান ফোর্ড, ফ্লয়েড ওয়ার্শাল অ্যালগরিদম কেন সঠিক?
• ৮.৭ আর্টিকুলেশন ভার্টেক্স (Articulation vertex) বা আর্টিকুলেশন বাহু (Articulation edge)
• ৮.৮ অয়লার পাথ (Euler path) এবং অয়লার সাইকেল (euler cycle)
• ৮.৯ টপোলজিক্যাল সর্ট (Topological sort)
• ৮.১০ স্ট্রংলি কানেক্টেড কম্পোনেন্ট (Strongly Connected Component – SCC)
• ৮.১১ 2-satisfiability (2-sat)
• ৮.১২ বাইকানেক্টেড কম্পোনেন্ট (Biconnected component)
• ৮.১৩ ফ্লো (Flow) সম্পর্কিত অ্যালগরিদম
  • ৮.১৩.১ ম্যাক্সিমাম ফ্লো (Maximum flow)
  • ৮.১৩.২ মিনিমাম কাট (Minimum cut)
  • ৮.১৩.৩ মিনিমাম কস্ট ম্যাক্সিমাম ফ্লো (Minimum cost maximum flow)
  • ৮.১৩.৪ ম্যাক্সিমাম বাইপারটাইট ম্যাচিং (Maximum Bipartite Matching)
  • ৮.১৩.৫ ভার্টেক্স কাভার (Vertex cover) ও ইনডিপেন্ডেন্ট সেট (Independent set)
  • ৮.১৩.৬ ওয়েইটেড ম্যাক্সিমাম বাইপারটাইট ম্যাচিং (Weighted maximum bipartite matching)
• ৮.১৪ প্রোগ্রামিং সমস্যা
  • ৮.১৪.১ অনুশীলনী

অধ্যায় ৯ – কিছু অ্যাডহক পদ্ধতি (Adhoc Technique)

• ৯.১ কিউমিউলেটিভ যোগফল পদ্ধতি (Cumulative sum technique)
• ৯.২ সর্বোচ্চ যোগফল পদ্ধতি (Maximum sum technique)
  • ৯.২.১ একমাত্রিক সর্বোচ্চ যোগফল সমস্যা (One dimensional Maximum sum problem)
  • ৯.২.২ দ্বিমাত্রিক সর্বোচ্চ যোগফল সমস্যা (Two dimensional Maximum sum problem)
• ৯.৩ প্যাটার্ন (Pattern) খোঁজা
  • ৯.৩.১ LightOJ 1008
  • ৯.৩.২ জোসেফাস সমস্যা (Josephus Problem)
• ৯.৪ একটি নির্দিষ্ট সীমায় সর্বোচ্চ উপাদান
  • ৯.৪.১ একমাত্রিক (One Dimensional বা 1D)
  • ৯.৪.২ দ্বিমাত্রিক (Two Dimensional বা 2D)
• ৯.৫ লীস্ট কমন অ্যানসেস্টর (Least Common Ancestor)
• ৯.৬ প্রোগ্রামিং সমস্যা
  • ৯.৬.১ অনুশীলনী

অধ্যায় ১০ – জ্যামিতি (Geoemetry) এবং কম্পিউটেশনাল জ্যামিতি (Computational Geometry)

• ১০.১ মৌলিক জ্যামিতি ও ত্রিকোণমিতি
• ১০.২ স্থানাঙ্কভিত্তিক জ্যামিতি (Coordinate Geometry) এবং ভেক্টর (Vector)
• ১০.৩ কিছু কম্পিউটেশনাল জ্যামিতির অ্যালগরিদম
  • ১০.৩.১ কনভেক্স হাল (Convex Hull)
  • ১০.৩.২ নিকটতম বিন্দুজোড় (Closest pair of points)
  • ১০.৩.৩ পরস্পরচ্ছেদী রেখাংশ (Line segment intersection)
  • ১০.৩.৪ পিকের থেওরেম (Pick’s theorem)
  • ১০.৩.৫ বহুভুজ সম্পর্কিত টুকিটাকি
  • ১০.৩.৬ লাইন সুইপ (Line sweep) এবং রোটেটিং ক্যালিপার্স (Rotating Calipers)
  • ১০.৩.৭ কিছু স্থানাঙ্ক সম্পর্কিত গণনা
• ১০.৪ প্রোগ্রামিং সমস্যা
  • ১০.৪.১ অনুশীলনী

অধ্যায় ১১ – স্ট্রিং (String) সম্পর্কিত ডেটা স্ট্রাকচার ও অ্যালগরিদম

• ১১.১ হ্যাশিং (Hashing)
• ১১.২ নুথ-মরিস-প্র্যাট (Knuth-Morris-Pratt) বা KMP অ্যালগরিদম
  • ১১.২.১ KMP সম্পর্কিত কিছু সমস্যা
• ১১.৩ Z অ্যালগরিদম
  • ১১.৩.১ Z অ্যালগরিদম সম্পর্কিত কিছু সমস্যা
• ১১.৪ ট্রাই (Trie)
• ১১.৫ আহো-কোরাসিক অ্যালগরিদম (Aho-corasick Algorithm)
• ১১.৬ সাফিক্স অ্যারে (Suffix Array)
  • ১১.৬.১ সাফিক্স অ্যারে সম্পর্কিত কিছু সমস্যা
• ১১.৭ প্রোগ্রামিং সমস্যা
  • ১১.৭.১ অনুশীলনী