Extended Euclid: Solving Linear Diophantine Equation

Motivating Problem: Suppose, you are at the invisible cafeteria of CUET. In cafeteria, each cup of tea and coffee cost a and b taka respectively. You can buy any non-negative integer number cups of tea and coffee. If you have c taka, find out if it is possible to buy some cups of tea and coffee spending exactly c taka. We can model this problem like: ax+by=c.

বেলম্যান ফোর্ড(Bellman-Ford) অ্যালগরিদমঃ

Bellman-Ford algorithm solves the single shortest path problem like BFS and Dijkstra. But if the input graph has negative edge weights, Dijkstra fails.

Motivating Problem: Given a weighted, directed Graph G with source s and weight w, the Bellman-Ford algorithm returns a boolean value whether or not there is a

ডায়াক্সট্রা(Dijkstra):

Dijkstra is a shortest path finding algorithm like BFS. BFS works only when the graph is unweighted.But if the graph is weighted, BFS doesn't work correctly. If the edges of a graph is non-negative and weighted, shortest path of the graph can be found by Dijkstra algorithm.

Motivating Problem:Given a weighted graph G and a starting source vertex s,what are the shortest paths from s to the other vertices of G?

স্প্র্যাগ-গ্রান্ডি সংখ্যা

Alice এবং Bob দুই ভাই।তারা এইবার ঈদে সেলামি হিসেবে রিলেটিভদের কাছে থেকে কতগুলো কয়েন পেয়েছে।কিন্তু তারা খেলনা উড়োজাহাজ কিনতে গিয়ে দেখল একজনের কয়েন দিয়ে কেনা যাচ্ছে না।তাই তারা দুজনের কয়েন গুলো এক জায়গায় রেখে স্তুপ করল এবং একটা গেম খেলার সিদ্ধান্ত নিল।খেলায় যে জিতবে সে সবগুলো নিয়ে নিবে,মানে উড়োজাহাজ তার। গেমটা হল তারা প্রতি চালে স্তুপ থেকে ১,২,অথবা ৩ টা কয়েন তুলে নিতে পারবে,শেষ কয়েন টা যে তুলতে পারবে সে জিতে যাবে।এখন কয়েনের সংখ্যা দেখেই তোমাকে বলতে হবে কে জিতবে(তারা কেউ কোন ভুল চাল দিবে না)।

Game Theory 1

নিম গেম

কনভেক্স হাল(Convex Hull)

If you don't know what Convex Hull is,read the following articles sequentially.Hope,you'll get vast knowledge.Since there are a lot of tutorials on Convex Hull,we'll rather discuss here some related problems & their solutions.

Tutorials on Convex Hull & it's prerequisites:

1.Orientation of 3 ordered points(prerequisite)
2.How to check if two given line segments intersect?(prerequisite)
3.Implementation of Graham Scan Algorithm for Convex Hull(Implementation)

STL Algorithm

Algorithm Used in Vector

(i) Non-Manipulating Algorithms:

          1. sort(first_iterator,last_iterator)-To sort a given vector.

          2. reverse(first_iterator,last_iterator)-To reverse a given vector.

          3. *max_element(first_iterator,last_iterator)-To find the maximum element of a vector

          4. *min_element(first_iterator,last_iterator)-To find the minimum element of a vector 

          5. accumulate(first_iterator,last_iterator.initial value of sum)-Does the summation of vector elements.

          6. count(first_iterator,last_iterator,x)-Count the occurrence in vector.

          7. find(first_iterator,last_iterator,x)-Points the last address of the vector if the element is not found

বাইনারি ইনডেক্সড ট্রি/ফেনউইক(Fenwick) ট্রি

Related Problems & Solution:

1. LightOj 1112 - Curious Robin Hood
            Solution: http://ideone.com/sIcaHD

লেজি প্রপাগেশন(সেগমেন্ট ট্রি)

আমরা আগের পর্বে সেগমেন্ট ট্রি বিল্ড,আপডেট এবং কুয়েরি করা শিখেছিলাম।আমরা এটাও জানি যে,সেগমেন্ট ট্রি প্রতি আপডেটের কমপ্লেক্সিটি O(log n)।তাহলে n টি আপডেট থাকলে সেক্ষেত্রে কমপ্লেক্সিটি হবে O(n log n)।কিন্তু লেজি প্রপাগেশন টেকনিক ব্যবহার করে এটা আমরা O(log n) কমপ্লেক্সিটিতেই করতে পারব।

Updating through Lazy:

নিচের ছবিটা দেখি,

সেগমেন্ট ট্রি

ধর, একটি ৫০ ওভারের ক্রিকেট ম্যাচের কোন ওভারে কত রান হয়েছে তা একটি অ্যারে তে স্টোর করা আছে ।এখন যদি জানতে চাওয়া হয় ম্যানডেটরি পাওয়ার প্লে তে(১-১০ ওভার) কত রান এসেছে বা বোলিং/ব্যাটিং পাওয়ার প্লে(ধর,৩৫-৪০ ওভার) তে কত রান এসেছে বা যে কোন একটি রেঞ্জ দিয়ে বলা হয় ঐ রেঞ্জের ওভারে কত রান এসেছে? এটা আমরা খুব সহজেই কিউমুলেটিভ সাম বের করে বলে দিতে পারব।কিন্তু ধর কোন কারণে কোন একটি ওভারের রান টা আপডেট করা লাগবে(হয়ত বলার সময় ভুল হইছিল!😂)।তাহলে কি করব?এখন তো আর কিউমুলেটিভ সাম দিয়ে কাজ হবে না।এরকম ক্ষেত্রে অর্থাৎ যেখানে একটা নির্দিষ্ট রেঞ্জ কুয়েরি করতে হবে এবং আপডেটও থাকবে,সেখানে সেগমেন্ট ট্রি লাগবেই লাগবে।

সেগমেন্ট ট্রি হল একটি ট্রি ডাটা স্ট্রাকচার,যেটা কতগুলো interval/segment কে স্টোর করে রাখে এবং সেখান থেকে একটা নির্দিষ্ট রেঞ্জের মধ্যকার সল্যুশন কুয়েরি করে বের করা যায়।এটা একটা Height Balanced Binary Tree এবং গঠনগতভাবে স্থিতিশীল।এই গাঠনিক স্থিতিশীলতার কারণে এটা Balanced Binary Tree এর চেয়ে কম ইফিশিয়েন্ট,কিন্তু এর রিকার্সিভ অপারেশনের কারণে এটা চিন্তা করা এবং কোড করা অপেক্ষাকৃত সহজ।

সেগমেন্ট ট্রি বুঝতে হলে রিকার্সন সম্পর্কে ভাল ধারণা থাকতে হবে।আর মার্জ সর্ট জানলে সেগমেন্ট ট্রি খুবই সহজ লাগবে।কারণ সেগমেন্ট ট্রি মার্জ সর্টের মতই Divide And Conquer পদ্ধতিতে কাজ করে।

মার্জ সর্ট

ধর,তোমরা কয়েক জন বন্ধু দার্জিলিং ঘুরতে গিয়ে ক্যাটরিনার দেখা পাইলা।কিন্তু তোমাদের সবাই ক্যাট কে চায়ই চায়।ক্যাট ও তোমাদের সবাই কে চায়💚 কারণ তোমরা সবাই অনেক স্মার্ট😂।কিন্তু ক্যাট ভাবল সবাইকে নিলে, ব্যাপারটা কেমন অনৈতিক হয়ে যায়💘 তাই সে তোমাদের একটা প্রস্তাব দিল,কত গুলো নাম্বার কে যে যত কম টাইম কমপ্লেক্সিটি তে সর্ট করতে পারবে,তাকেই সে বফ বানাবে😙। তো তুমি চিন্তা করলে,বাবল সর্ট করলে নিশ্চিত ধরা খাব,তার চেয়ে বরং মার্জ সর্ট মেরে দেয়(কারণ তুমি ল্যাব ভাইভার জন্য মুখস্ত করছিলা🙌 যে মার্জ সর্টের কমপ্লেক্সিটি(worst case: O(N log N)),অন্ততপক্ষে বাবল সর্টের(worst case: O(N^2)) চেয়ে কম)।দেখা যাক,কপালে কি আছে!😰কিন্তু তুমি তো মার্জ সর্টও জানো না।তাইলে চলো শিখে নেই,ক্যাট কে পাবার জন্য হলেও!😍

মার্জ সর্ট হল খুবই কার্যকরী একটি সর্টিং অ্যালগরিদম।এটা Divide and Conquer পদ্ধতিতে কাজ করে। মানে ইনপুট অ্যারে টাকে কতগুলো ক্ষুদ্র ক্ষুদ্র সাব-প্রবলেমে ভাগ করে ফেলে,তারপর সেই ক্ষুদ্র ক্ষুদ্র অংশ গুলো কে মার্জ করে যে সমাধাণ গুলো পায়,সেগুলো একত্রিত করে মূল সর্টেড অ্যারে প্রডিউস করে।

ধর,নিচের অ্যারে টাকেই সর্ট করতে হবে।
                   
এখন এই অ্যারে টাকে আমরা Left এবং Right নামে সমান দুই ভাগে ভাগ করব।

এখন কেউ যদি কোনভাবে আমাদের কে এই Left[] এবং Right[] সাব-অ্যারে দুটি সর্ট করে দেয় তাহলে কিভাবে আমরা এই দুটি সর্টেড সাব-অ্যারে কে মার্জ করে মূল অ্যারে কে সর্ট করতে পারি,সেটাই আগে দেখব।ঐ সাব-অ্যারে দুটি কিভাবে সর্ট করব সেটা এখন ভাবনার বিষয় না।আপাততঃ ধরে নাও কোন এক অলৌকিক শক্তি দিয়ে আমরা সেটা করতে পারব😎।

ক্রুসকাল অ্যালগরিদম

Spanning Tree হল এমন একটি  সাবগ্রাফ যেখানে মূলগ্রাফের সবগুলো নোড থাকে এবং n-1 সংখ্যক এজ থাকে কিন্তু কোন সাইকেল থাকে না। n যেখানে হল নোডসংখ্যা।একটা গ্রাফের অনেকগুলো Spanning Tree হতে পারে,কিন্তু তাদের মধ্যে যে Spanning Tree এর এজগুলোর কস্ট/ওয়েট এর যোগফল সবচেয়ে কম সেটিই হল  Minimum Spanning Tree(MST)/Minimum Weight Spanning Tree.

Minimum Spanning Tree(MST) বের করার দুইটা অ্যালগরিদম আছে, ক্রুসকাল এবং প্রিমস অ্যালগরিদম।এখানে আমরা দেখব ক্রুসকাল অ্যালগরিদম দিয়ে কিভাবে Minimum Spanning Tree(MST) বের করা যায়। এ সম্পর্কে বিশদভাবে জানার জন্য শাফায়েত ভাইয়ের ব্লগের বিকল্প নাই।

ফাংশন প্যারামিটার

দুইভাবে ফাংশনে প্যারামিটার/আর্গুমেন্ট পাস করা যায়।
1.Call by Value
2.Call by Reference

Call by Value এবং Call by Reference এর মধ্যে প্রধান পার্থক্য হল Call by Value তে শুধু আসল প্যারামিটার/ আর্গুমেন্টেরই একটা কপি পাস হয়।তাই ফাংশনে পাস হওয়া ঐ কপি প্যারামিটার/ আরগুমেন্টের চেইঞ্জ করলেও আসল প্যারামিটারের কোন চেইঞ্জ হয় না।কিন্তু Call by Reference এ প্যারামিটারের কপি পাস না হয়ে অ্যাড্রেস পাস হয়। তাই ফাংশনের মধ্যে ঐ প্যারামিটারের কোন চেইঞ্জ হলে আসল প্যারামিটারেও সেই চেইঞ্জ হবে।

প্যাটার্ন ম্যাচিং অ্যালগরিদম

প্যাটার্ন ম্যাচিং অ্যালগরিদম কম্পিউটার সায়েন্সে খুবই গুরুত্বপূর্ণ।আমরা যখন ডাটাবেসে বা ওয়েব ব্রাউজারে স্ট্রিং সার্চ করি তখন সার্চ রেজাল্ট দেখানোর জন্য এই অ্যালগরিদম ইউজ হয়।একটা বেসিক প্যাটার্ন ম্যাচিং প্রবলেম হলঃ একটা টেক্সট স্ট্রিং এবং প্যাটার্ন স্ট্রিং দেওয়া থাকবে,খুঁজে দেখতে হবে টেক্সট স্ট্রিং এর মধ্যে প্যাটার্ন স্ট্রিং টা আছে কি না।এই প্রবলেম টা "The needle in a haystack problem" নামেও পরিচিত।

Naive Approach:

Naive method টা হল straightforward।টেক্সট স্ট্রিং এর প্রতিটা পজিশনকে প্যাটার্ন স্ট্রিং এর শুরুর পজিশন বিবেচনা করে দেখতে হবে ম্যাচ পাওয়া যায় কি না।

ট্রাই(প্রিফিক্স/রেডিক্স ট্রি)

ট্রাই(Trie) হল বহুল ব্যবহৃত একটা ডাটা স্ট্রাকচার।ট্রাই এর সবচেয়ে প্রচলিত প্রয়োগ হল ডিকশনারিতে শব্দ স্টোর করা, সার্চ করা, ডিলিট করা ইত্যাদি।ধরা যাক,ডাটাবেসে বাংলাদেশের সব মানুষের নাম আছে।এখন ডাটাবেস যতই বিশাল হোক না কেন,সেখান থেকে ABUL নামটা খুঁজে বের করতে ৪ টার বেশি অপারেশন লাগবে না(ক্যামনে?😮)।এবার আমরা একটা ওয়েব ব্রাউজারের কথা চিন্তা করি।আমরা যখন ব্রাউজারে সার্চ করার জন্য কিছু লিখি,তখন অনেক টেক্সট অটো কমপ্লিট হয়ে যায় বা যে টেক্সট লিখার পসিবিলিটি আছে তার অনেক গুলো অপশন দেখায়(ক্যামনে বুঝে,আমি কি চায়?😕)। হুম,এইসব ক্ষেত্রে ট্রাই ই হল নাটের গুরু 😉।

ট্রাই(Trie)  হল 'Retrieval' ওয়ার্ড টার একটা Infix।কারণ ট্রাই ডিকশনারি থেকে একটা ওয়ার্ড কে শুধুমাত্র ওয়ার্ডটার একটা প্রিফিক্স দিয়েই খুঁজে বের করতে সক্ষম। Edward Fredkin প্রথমে 'Retrieval' শব্দের এই  Infix নিয়ে এটাকে ট্রি(Tri) বলেন।কিন্তু গ্রাফ থিওরিতে ব্যাপকভাবে প্রচলিত 'ট্রি' থেকে আলাদা করার জন্যই এটাকে ট্রাই বলা হয়ে থাকে।