Latest News
0

ট্রাই ট্রি ( Trie Tree )

~

আগে জেনে আসা উচিত : ট্রি, লিঙ্কড লিস্ট, Prefix কাকে বলে

সূচনা

গুগল সার্চ করার সময়ে দেখা যায় কোন কিছু লিখলে গুগল আমাদের কে কিছু সাজেশন দেখায় যেমন লিখলাম, যেমনটি নিচের মতো –

google suggestion

 

এটা কিভাবে করে গুগল ? এই টাকে যদি একটি প্রব্লেম হিশেবে চিন্তা করি , তাহলে সহজভাবে বলা যায় –

তোমাকে অনেকগুলি শব্দের অভিধান ( Dictionary ) দেয়া আছে, এখন তোমাকে আবার কতগুলো শব্দ দেয়া হবে, প্রতিটি শব্দ এর জন্য তোমাকে বলতে হবে যে অই শব্দ টি তোমার অভিধানের কতগুলো শব্দের Prefix ?

ধরো, তোমার অভিধানে এই শব্দ গুলো আছে –

ABBA

ABC

ACCA

ANA

ANACONDA

BAAB

এখন যদি তোমাকে জিজ্ঞাশা করা হয় যে “AB” শব্দটি অভিধানের কতটি শব্দের Prefix ? উত্তর হবে ২, শুধু “A” এর ক্ষেত্রে উত্তর হবে ৫।

এবার এই প্রব্লেম এর সল্যুশন বের করি-

অবশ্যই Brute Force একটি উপায় যার Order হবে প্রায় O(n^3) , কিন্তু যদি আমরা  আরও ভালো উপায় খুজতে চাই তখন কি হতে পারে ? একটি উপায় হতে পারে আমার ডিকশনারির সব গুলো শব্দ কে Lexicographically সাজায়ে বাইনারি সার্চ। কিন্তু সে উপায়ে Order হবে O(nlogn)। এর চেয়ে ভালো উপায় আছে কি ?

হুম… আছে। আরেকটি উপায় হচ্ছে ট্রাই ট্রি ( Trie Tree ). যা O(n) [ আসলে O( given word’s length ) ] এ কাজ করে।

ট্রাই ট্রি কি জিনিশ ?

ট্রাই ট্রি একটি ডাটা স্ট্রাকচার, যার নাম টি এসেছে “Retrieval” শব্দটি থেকে । ট্রাই ট্রি কে প্রেফিক্স ট্রি ও বলা হয়ে থাকে। ট্রাই ট্রি এর বৈশিষ্ট্য হচ্ছে-

১। ট্রাই ট্রি এর প্রতিটি ভারটেক্স একটি সম্পূর্ণ শব্দ বা একটি শব্দের Prefix কে প্রকাশ বা নির্দেশ করে।

২। এই ট্রি এর রুট (Root) একটি Empty String, এবং রুট থেকে তার প্রতিটি সন্তান এর মধ্যে Shortest Path Distance অই দৈর্ঘ্য এর প্রেফিক্স কে নির্দেশ করে। যদি রুট থেকে কোন সন্তান এর মধ্যে সবচেয়ে কাছাকাছি পথ এর দৈর্ঘ্য ২ হয় তার মানে হচ্ছে অই vertex টি কোন এক বা একাধিক শব্দের ২ দৈর্ঘ্য এর prefix কে নির্দেশ করে।

৩। যদি A এবং B ট্রাই ট্রি এর দুটি ভারটেক্স হয়, এবং A যদি B এর সবচেয়ে নিকটবর্তী পিতা হয় তাহলে A অবশ্যই B এর প্রেফিক্স কে নির্দেশ করে।

ট্রাই ট্রি দেখতে কিরকম ?

যদি আমরা “HOME”, “HOUSE”, “HOMEWORKER”, “MOUNTAIN” শব্দ গুলি নিয়ে একটি ট্রাই ট্রি বানাই , তাহলে দেখতে এরকম হবে –

trie2খেয়াল করে দেখ, প্রত্যেক টি ভারটেক্স কিন্তু একটি প্রেফিক্স কে নির্দেশ করছে। HOME, HOUSE দুটি শব্দেরই কিন্তু ২ দৈর্ঘ্য এর প্রেফিক্স সমান, এ কারনে ৩ দীর্ঘের প্রেফিক্স এর সময় দুটি চাইল্ড নোড আসছে। আর প্রত্যেকটি কমলা রঙ করা ভারটেক্স বা নোড একটি সম্পূর্ণ শব্দ কে নির্দেশ করে।

ট্রাই এর কোড

নিচে Reference অংশে কিছু লিঙ্ক দেয়া আছে, ওখান থেকে কোড পাবে।

ট্রাই দিয়ে প্রব্লেম সল্ভিং

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

এখন যদি তোমাকে কোন Query String দিয়ে যদি বলা হয় যে এই String টা তোমার অভিধানে আছে কিনা ? তাহলে কিভাবে ট্রাই দিয়ে বের করবো ? সহজ ব্যাপার, প্রতিটি নোড এ একটি ফ্ল্যাগ রাখবো যা নির্দেশ করবে যেই অই নোড টি কোন শব্দের শেষ কিনা মানে অই নোড এ কোন শব্দ শেষ হয়েছে কিনা। এখন আমরা যখন একেকটি শব্দ অভিধানে Insert করবো তখন যেই নোড এ আমাদের শব্দ টা শেষ হবে সেই নোড এর ফ্ল্যাগ টা 1 করে দিবো। এখন Query String এর জন্য আমরা ট্রাভারস করবো আমাদের ট্রি টা এবং দেখবো যে যেই নোড এ আমাদের query string শেষ হয়েছে তার ফ্ল্যাগ অন কিনা। সোজা না ?

রেফারেন্স

  1.  http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=usingTries
  2.  http://www.toptal.com/java/the-trie-a-neglected-data-structure
  3. http://en.wikipedia.org/wiki/Trie

প্রোগ্রামিং প্রব্লেম

  1. http://www.lightoj.com/volume_problemcategory.php?category=Trie%20Tree
  2. http://www.spoj.com/problems/PHONELST/
  3. http://www.spoj.com/problems/SUBXOR/%5B/embed

ধন্যবাদান্তে

সাব্বির ইউসুফ সানি ভাই,যার কাছ থেকে এই ডাটা স্ট্রাকচার শিখেছিলাম।

 

[ কোন কিছু বুঝতে অসুবিধা হলে , এখানে কমেন্ট করতে পারো অথবা ইমেইল করতে পারো faiyaz26 [at] gmail [dot] com এ ]

0

বাইকানেক্টেড কম্পোনেন্ট , ব্রিজ, আরটিকুলেশন পয়েন্ট [ থিওরি ]

~

আগে জেনে আসা উচিত:    বেসিক গ্রাফ থিওরি , গ্রাফ কানেক্টিভিটি , DFS

এই পোস্ট এ আমরা থিওরি জানবো , পরে আরেকটি পোস্ট এ আমরা বাইকানেক্টেড কম্পোনেন্ট , ব্রিজ, আরটিকুলেশন পয়েন্ট বের করার অ্যালগোরিদম নিয়ে আলোচনা করব।

ধরো, তোমার একজন বন্ধুর নাম সাফওয়াত। তুমি এখন তার বাসায়ে যাবে, এখন তুমি একটা ম্যাপ বের করলে যেখানে তুমি থাকো 0 নং নোডে , এবং তোমার বন্ধু থাকে ৬ নং নোডে। নিচের গ্রাফ টি দেখঃ

bcc1

এখন খেয়াল কর , তুমি ০ থেকে ৫ নং নোডে ২ ধরনের রাস্তা ব্যবহার করতে পার। সেগুলো হচ্ছে-

১। ০ – > ১ – >৪ – > ৫

২। ০ -> ২ -> ৩ -> ৫

দুটো পথের কোন টাই কিন্তু কেউ কারো উপর দিয়ে যাচ্ছে না, তাই না ? কিন্তু যদি আমি ৬ নং নোডে যেতে চাই, তাহলেও দুটি পথ আছে,

১। ০ -> ১ -> ৪-> ৫-> ৬

২। ০ -> ২ -> ৩ -> ৫ ->৬

এখন দেখ, আমাকে ৫->৬ এই খানে দুটি পথ এক হয়ে গেছে। এক হয়ে গেছে তো কি হয়েছে ? একটা সমস্যা হয়ে যাচ্ছে, ধরো তুমি বন্ধুর বাসায়ে যাচ্ছ , ১ নং পথ ধরে, হঠাত ভুমিকম্প হল, আর ৪ থেকে ৫ এ যাওয়ার রাস্তা গেল ভেঙ্গে , তুমি গিয়ে দেখলে ৪ নং নোড থেকে ৫ নং  এ যাওয়া যাচ্ছে না, কিন্তু তোমাকে তো ৫ এ যেতেই হবে , নাইলে ৬ নং নোড এ যাওয়া যাবে না !

bcc9

কিন্তু তোমার কাছে তো ম্যাপ আছে, এবং তুমি দেখলে যে আরেক টা রাস্তা আছে , যেই টা ব্যবহার করে ৫ নং নোড এ যাওয়া যায়, তো তুমি ঘুরে আবার তোমার বাসায় এসে, ২য় পথ ধরে তুমি তোমার বন্ধুর বাসায় পৌছাইলা।

ব্রিজঃ

সাধারণ মানুষ হইলে , তুমি বন্ধুর বাসায় গিয়ে আড্ডা মেরে সুন্দর মত নিজের বাসায়ে চলে যাইতা! সমস্যা হইল তুমি একজন প্রব্লেম সল্ভার , তোমার মাথায়ে সবসময় চিন্তা আসে যে যদি এইটা হইত তাহলে কি হইত, অইটা কেন হইত না…..

একি কারনে তোমার মাথায়ে চিন্তা আসল যে যদি ভুমিকম্পে ৫->৬ এর রাস্তা টা নস্ট হয়ে যাইত, তাহলে কি করতা ? তাহলে কি আর কোন পথ ছিল বন্ধুর বাসায় যাওয়ার ? না, আর কোন পথ থাকত না । 😦

আমি যদি গ্রাফ এর ৫ থেকে ৬ নং নোড এ যাওয়ার রাস্তা  টাকে বাদ দেই, তাহলে গ্রাফ টা দাড়ায় এরকম – 

bcc2

bcc8

তুমি এখন নিজেকেই প্রশ্ন করলা যে, যদি ভুমিকম্পে শুধুমাত্র একটি রাস্তা নষ্ট হয়, তারপরেও তোমার বাসা থেকে কোন কোন নোড এ যাওয়া যাবে এবং রাস্তা যেটাই নষ্ট হোক না কেন তুমি সবসময়ে অই নোড গুলা তে যেতে পারবে ? যেমন ধরো, যখন ৪ থেকে ৫ এর রাস্তা টা নষ্ট হইল , তখন কিন্তু তুমি ৬ নং নোড এ যেতে পারসো। কিন্তু যদি ৫ থেকে ৬ এর রাস্তা নষ্ট হইত , তাইলে কিন্তু ৬ নং নোড এ যেতে পারতা না। তারমানে যেকোনো একটি রাস্তা নষ্ট হলেও, সবসময়  তোমার বাসা থেকে  ৬ নং নোড এ যেতে পারবে না। তাহলে কোন কোন নোড এ যেতে পারবা ? গ্রাফ টার দিকে ভালো করে খেয়াল কর, নিজেই বের করতে পারো কিনা দেখ।

উত্তরঃ ১, ২, ৩, ৪, ৫ এই নোড গুলা তে যাইতে পারবা।

তাহলে দেখ যদি আমরা ৫ থেকে ৬ এ যাওয়ার রাস্তা গ্রাফ থেকে সরায়ে দেই, তাহলে গ্রাফ থিউরি এর ভাষায়ে গ্রাফ টা কিন্তু কানেক্টেড না। যেই রাস্তাকে [ edge ] বাদ দিলে পুরো গ্রাফ টি ডিস্কানেক্টেড হয়ে যাবে মানে সব নোড থেকে সব নোডে যাওয়া যাবে না,  অই রাস্তা বা edge কে বলা হয় ব্রিজ [Bridge] , আমাদের পদ্মা ব্রিজ এর কথা চিন্তা করতে পার। 🙂

ফরমাল ভাষায় বললে, যদি কোন এজ [ edge ]  কে একটি গ্রাফ থেকে বাদ দিলে,যদি গ্রাফ টা ডিস্কানেক্টেড হয় পরে বা দুই বা তার বেশী সাব গ্রাফ এ ভাগ হয়ে যায়, তাহলে অই এজ [edge] কে বলা হবে ব্রিজ [ Bridge ].

আরটিকুলেশন পয়েন্টঃ

এতক্ষন ০, ১, ২ এইগুলাকে নোড বললাম, ধরো এই গুলা একেক টা শহর, এখন ধরো, ৩ নং শহরে কারফিউ জারি করা হইল, তার মানে তুমি কারফিউ এর সময় অই শহর দিয়ে যেতে পারবা না। তাহলে ধরা যায় যে, ৩ নং নোড টা গ্রাফেই নাই ।

bcc4

bcc5

তাহলে দেখ এর পরেও কিন্তু তুমি সব নোড থেকে সব নোড এ  যেতে পারছ তাই না ? মানে তারা এখনও কানেক্টেড।

কিন্তু যদি ৫ নং নোড / শহরে কারফিউ জারি করা থাকতো , তখন গ্রাফ টা কেমন হইত ?

bcc6

bcc7

এই খানে দেখ, সব নোড থেকে সব নোড এ যাওয়া যাচ্ছে না। তারমানে গ্রাফ টা ডিসকানেক্টেড হয়ে যাচ্ছে। এই রকম অবস্থায় অই কারফিউ জারি করা নোড টা কে বলা হয় আরটিকুলেশন পয়েন্ট [ Articulation Point ] ।

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

এতক্ষন তো Articulation Point এবং Bridge নিয়া বললাম কিন্তু বাইকানেক্টেড কম্পোনেন্ট টা কি ? 

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

bcc11

নিচের দুইটা গ্রাফ এর পুরোটা কিন্তু বাইকানেক্টেড না , কেন ? কারন গ্রাফ গুলো তে আরটিকুলেশন পয়েন্ট আছে – 

bcc10

বরং তাদের সাব গ্রাফ গুলো একেকটা বাইকানেক্টেড কম্পোনেন্ট , যেমন –

bcc13

লাল রঙ এর নোড গুলো কিন্তু বামের নীল এবং সবুজ দুই রঙের বাইকানেক্টেড কম্পোনেন্ট এর ই অংশ, কিন্তু পুরো গ্রাফ টা বাইকানেক্টেড কম্পোনেন্ট না, কারন লাল রঙের নোড টা একটি আরটিকুলেশন পয়েন্ট।

সব সংজ্ঞা এক সাথে:

 ব্রিজ: যদি কোন এজ [ edge ]  কে একটি গ্রাফ থেকে বাদ দিলে,যদি গ্রাফ টা ডিস্কানেক্টেড হয় পরে বা দুই বা তার বেশী সাব গ্রাফ এ ভাগ হয়ে যায়, তাহলে অই এজ [edge] কে বলা হবে ব্রিজ [ Bridge ].

আরটিকুলেশন পয়েন্ট: যদি কোন নোড কে গ্রাফ থেকে বাদ দেয়া হয় , এর ফলে যদি গ্রাফ টা ডিস্কানেক্টেড হয় পরে বা দুই বা তার বেশী সাব গ্রাফ এ ভাগ হয়ে যায়, তাহলে অই নোড টা কে বলা হবে আরটিকুলেশন পয়েন্ট।

 বাইকানেক্টেড কম্পোনেন্ট: যদি একটি গ্রাফে কোন আরটিকুলেশন পয়েন্ট না থাকে, তাহলে অই গ্রাফ টি একটি বাইকানেক্টেড কম্পোনেন্ট।

নিচে কয়েকটি গ্রাফ দেয়া হবে উত্তর বের করে মিলাও, উত্তর মিললে বুঝা যাবে যে , হ্যাঁ তুমি BCC, Bridge, Articulation point কি বুঝেছ।

১। নিচের গ্রাফ টা কি বাইকানেক্টেড ?

২। নিচের গ্রাফ টা কি বাইকানেক্টেড ? 

bcc6

৩। নিচের গ্রাফ টা কি বাইকানেক্টেড ?

৪। নিচের গ্রাফে কোন গুলো আরটিকুলেশন পয়েন্ট এবং কোন কোন সাব গ্রাফ বাইকানেক্টেড কম্পোনেন্ট?

 

৫। নিচের গ্রাফ এ কয়টি ব্রিজ এবং আরটিকুলেশন পয়েন্ট আছে ?

 

উত্তরঃ

১। হ্যাঁ

২। হ্যাঁ

৩। না,

৪। A, H, G, J এরা হচ্ছে AP, আর বাইকানেক্টেড কম্পোনেন্ট গুলো হচ্ছে – 

{A, C, G, D, E, F}, {G, J, L, B।}, B, H, I, K

৫। ৩ টা Bridge, ২ টা AP.

আরও জানতে:

১। http://en.wikipedia.org/wiki/Biconnected_component

২। http://www.ics.uci.edu/~dan/class/161/notes/8/Bicomps.html

৩। http://www.scribd.com/doc/56802813/Bridge-Algorithm

0

কিউ বেসিক ডাটা স্ট্রাকচার

~

সামনে বাংলাদেশ প্রিমিয়ার লিগ এর খেলা, ব্যাংক এ টিকেট পাওয়া যাচ্ছে। তুমি সকাল সকাল ব্যাংক এর সামনে গেলে, গিয়ে দেখলে তোমাকে কাউন্টার এর সামনে দাড়াতে হবে। এখন নিয়ম হচ্ছে, কাউন্টার খালি থাকলে তুমি সবার প্রথমে দাঁড়াবে, আর তা না হলে , যারা দাড়িয়ে আছে তাদের একদম পিছনে দাড়াতে হবে। আর কাউন্টার থেকে প্রথমে যে আশবে , তাকে প্রথমে টিকেট দেয়া হবে। যে শেষে আশবে সে সবার শেষে টিকেট পাবে। হুম , আমাদের দৈনন্দিন জীবনে যেভাবে কোন সার্ভিস নেয়ার জন্য লাইনে দাঁড়াই , ব্যাপার টা আসলে তাই। এই লাইনে দাঁড়ানোর ব্যাপার টাই কিউ ডাটা স্ট্রাকচার প্রকাশ করে।

কিউ ডাটা স্ট্রাকচার এর ধর্ম

১। নতুন কোন ডাটা আশলে , পুরাতন ডাটা থাকলে তাদের সবার পিছনে থাকবে।

২। কোন ডাটা কে নিতে হলে, সবার প্রথমে যে ডাটা টি আসছিল তাকেই প্রথমে নিতে হবে, একে বলে First In First Out [FIFO] ।

কিউ এর অপারেশানঃ

১। Push: নতুন কোন ডাটা আনলে সবার শেষে রাখতে হবে।

২। Pop: কোন ডাটা নিতে হলে , সবার প্রথমে যে থাকবে তাকে নিতে হবে।

Human queue

Queue

কিউ এর সিমুলেশন

১। Push(1): ১ কিউ তে ঢুকাতে হবে।

কিউঃ ১

২। Push(2): ২ কিউ তে ঢুকাতে হবে

কিউঃ ১ ২

৩। Push(3): ৩ কিউ তে ঢুকাতে হবে

কিউঃ ১ ২ ৩

৪। Pop(): সবার আগে যে আছে, তাকে বের করে ফেলতে হবে , এক্ষেত্রে ১ বের হবে

কিউঃ ২ ৩

৫। pop(): এবার ও সবার আগে যে আছে, তাকে বের করতে হবে। এক্ষেত্রে ২ বের হবে।

কিউঃ ৩

৬। Push(4): ৪ কিউ তে ঢুকাতে হবে।

কিউঃ ৩ ৪

৭। Pop(): নিজে কর

৮। Push(6): নিজে কর।

অ্যালগোরিদম এনালাইসিস

Push আর Pop , O(1) এ করা যায়।

কিউ এর ব্যাবহার

Breadth First Search (Graph Algorithm) এ কিউ ব্যবহার করতে হয়। Operating System এ কিউ একটি প্রয়োজনীয় ডাটা স্ট্রাকচার

0

স্ট্যাক বেসিক ডাটা স্ট্রাকচার

~

ডাটা স্ট্রাকচার কি জিনিশ ?

ধরি , মাহমুদ নামের একটি ছেলের কাছে অনেক গুলো বই আছে, এখন সেই সব বই ছড়ায়ে, ছিটিয়ে রেখেছে। এখন তার মা , তাকে বই গুলো সুন্দর ভাবে সাজায়ে রাখতে বলল। মাহমুদ খুবি চিন্তায় পরল, কারন এখন বই গুলা কে কিভাবে সাজালে তার জন্য সুবিধা হবে। সে অনেক গুলা বুদ্ধি বের করলো। একটি হচ্ছে, সেই সব গুলো বই একটার উপর আরেকটা রাখবে। আর তা না হলে, বই গুলো লাইব্রেরি তে যেভাবে থাকে মানে দাঁড় করিএ রাখবে। এখন মাহমুদ কিছু বই প্রথম ভাবে, কিছু বই দ্বিতীয় পদ্ধতিতে রাখল। এতে মাহমুদ অ খুশি, তার মা ও খুশি। কারন বই গুলো সুন্দর ভাবে সাজানো আছে, আবার মাহমুদ এর যখন যেই বই দরকার সে তখন সেই বইটি খুজে বের করে নিতে পারবে।

এখন তুমি যদি অই বই গুলো কে ডাটা ( অনেক তথ্য ) হিসেবে চিন্তা করো। তো বই যেভাবে সাজানো লাগছে, ডাটা ও সাজানো দরকার যাতে আমরা আমাদের সুবিধা মতো খুজে পেতে পারি। তো ডাটা সাজিয়ে সুন্দর ভাবে উপস্থাপন এর নাম ই ডাটা স্ট্রাকচার।

ডাটা স্ট্রাকচার অনেক অ্যালগোরিদম কে সুন্দর ভাবে এবং আরও দক্ষ ভাবে প্রকাশ করতে সাহায্য করে।

স্ট্যাক

একটু আগে আমরা দেখলাম, মাহমুদ একটার উপর আরেকটা রেখে বই গুলো গুছাচ্ছিল । এখন মাহমুদ কে কোন বই নিতে হলে , অই বই এর উপরের সব গুলো বই কে সরাতে হবে [ যদি উপরে আরও বই থাকে ]। আবার কোন নতুন বই রাখতে হলে তাকে সব গুলো বই এর উপরে রাখতে হবে।  তাহলে মাহমুদ কে যদি জিজ্ঞাসা করা হয়, ভাই তুমি সবার শেষে কোন বইটা রাখস ? আমাকে দাও। মাহমুদ এর কোন কষ্টই হবে না বের করতে, কারন সে জানে সবার উপরে যে বই টা আসে সেইটাই সে সবার শেষে রাখসিল। হুম, বুঝা গেলো মাহমুদ কি করেছে ? যদি বুঝা যায়, তাহলে এখন আমরা আবার বই গুলো কে ডাটা ধরি, তাহলে ব্যাপার টা কি দাঁড়াচ্ছে , আমাদের কাছে এক গাদা ডাটা আছে, আমরা সে গুলো একটার উপর আরেকটা রাখতে চাই।

  • নতুন কোন ডাটা রাখতে হলে, সবার উপরে রাখতে হবে। তাতে কষ্ট কম হবে।
  • কোন ডাটা কে নিতে চাইলে, তার উপরের সব গুলো ডাটাকে কে সরাতে হবে। মানে যাকে সবার শেষে রাখা হয়েছে, তাকে সবার আগে বের করে নিতে হবে । এটাকে বলে LIFO [Last in First Out ].
  • খুব সহজেই বলতে পারবো যে কোন ডাটা টি সবার শেষে নেয়া হয়েছে।

এই ভাবে আমরা যদি ডাটা উপস্থাপন করি , তাহলে তাকে বলে স্ট্যাক।

books-stack

এখন স্ট্যাক এর দুইটি অপারেশন বা প্রক্রিয়া আছে-

১। Push

২। Pop

Push হচ্ছে আমরা যে নতুন ডাটা পেলে তা একদম উপরে রাখছি, এটাই ।

আবার Pop হচ্ছে স্ট্যাক থেকে ডাটা নিতে হলে সবার উপর থেকে নিচ্ছি এই প্রক্রিয়া টিই।

তাহলে এবার আমরা হাতে হাতে করে দেখি স্ট্যাক এ কোন অপারেশন এর জন্য কি হয়।

১। Push(1) : প্রথমে স্ট্যাক টি খালি ছিল, তাহলে স্ট্যাক এ ১ ঢুকাই।

স্ট্যাক : 1

২। Pop(): স্ট্যাক এর সব চেয়ে উপরের সংখ্যা টি বের করে ফেলতে হবে । আর কোন সংখ্যা স্ট্যাক এ নাই বলে স্ট্যাক টি আবার খালি হয়ে যাবে

স্ট্যাক:

৩। Push(2): স্ট্যাক টি এখন খালি বিধায়ে ২ স্ট্যাক এ ঢুকাই।

স্ট্যাক: 2

৪। Push(3): 3 স্ট্যাক এ ঢুকাই। তাহলে স্ট্যাক টির অবস্থা দাঁড়াচ্ছে

স্ট্যাক: 2 3

৫। Push(4): 4 স্ট্যাক এ ঢুকাই। স্ট্যাক টির বর্তমান অবস্থা –

স্ট্যাক: 2 3 4

৬। Pop(): স্ট্যাক এর সবচেয়ে উপরের সংখ্যা টি বের করে ফেলতে হবে , তাহলে বের হবে 4. স্ট্যাক টির অবস্থা দাঁড়াচ্ছে

স্ট্যাক: 2 3

৭। Pop(): আবারো স্ট্যাক এর সবচেয়ে উপরের সংখ্যা টি বের করে ফেলতে হবে , তাহলে বের হবে 3. স্ট্যাক টির অবস্থা দাঁড়াচ্ছে

স্ট্যাক: 2

৮। Push(5): 5 স্ট্যাক এ ঢুকাই।

স্ট্যাক: 2 5

৯। Push(1): এটা নিজে করে দেখো,এবং আমার সাথে উত্তর মিলাও

স্ট্যাক: 2 5 1

১০। Pop():এটা নিজে করে দেখো,এবং আমার সাথে উত্তর মিলাও

স্ট্যাক: 2 5

অ্যালগোরিদম এনালাইসিস

প্রতি Push বা Pop করতে O(1) সময়ে লাগে

স্ট্যাক এর ব্যবহার

স্ট্যাক অনেক দরকারি এবং খুবি সোজা একটি ডাটা স্ট্রাকচার। এটি ব্যবহার করে Depth First Search (Graph Algorithm) কাজ করে। স্ট্যাক দিয়ে expression evaluation(postfix-infix) করা যায় । এছাড়া Compiler বানাতে স্ট্যাক অত্যাবশ্যক একটি ডাটা স্ট্রাকচার।

0

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

~

মীর ওয়াসি আহমেদ

তুমি বাংলাদেশ ইনফরম্যাটিক্স অলিম্পিয়াড ২০১৩ এর বিভাগীয় প্রতিযোগিতার খবর হয়তো জেনেছ। কিন্তু প্রশ্নের ধরণ – কি কি থাকবে, কিভাবে প্রস্তুতি নিতে হবে – কিছুই জানো না এখনো। তোমাকে সাহায্য করবার জন্যেই এই লেখা।

বিভাগীয় প্রতিযোগিতায় দুটো অংশে প্রশ্ন হয়ঃ অ্যানালিটিকাল আর প্রোগ্রামিং। এই পর্বে অ্যানালিটিকাল প্রশ্নই থাকে বেশিরভাগ। আর পুরো পরীক্ষাটাই হয় কাগজ কলমের। প্রোগ্রামিং অংশে প্রশ্নের সাথে কিছু ইনপুট দেওয়া থাকে যেগুলোর উত্তর কম্পিউটারে বের করে প্রশ্নপত্রের উত্তরের জন্যে নির্ধারিত ফাঁকা জায়গায় লিখতে হয়।

অ্যানালিটিকাল অংশটা বেশ গুরুত্বপূর্ণ। দেখা গেছে শুধু অ্যানালিটিকাল অংশে ভালো করে অনেকেই বিভাগীয় পর্যায় উতরে যায়। এই অ্যানালিটিকাল অংশে ভালো করতে হলে নিচের বিষয়গুলো দেখা যেতে পারে। পরে মনে পড়লে আরো যোগ করব।

১) গাণিতিক সমস্যা – এইচ এস সি লেভেলের জ্ঞান দিয়েই পারার কথা। কয়েকটা টপিক হতে পারেঃ

ক) সংখ্যাতত্বঃ বিভাজ্যতা, মৌলিক সংখ্যা, উৎপাদক, ল.সা.গু ও গ.সা.গু।

খ) কম্বিনেটরিক্সঃ বিন্যাস, সমাবেশ ও সম্ভাব্যতা।

ঘ) বীজগণিতঃ ধারা, অনুক্রম ও সমীকরণের সমাধান।

গ) প্রমাণঃ গাণিতিক আরোহ…

View original post 211 more words

3

C/C++ Struct

~

C++ Struct একটি অত্যন্ত জরুরি ফিচার C/C++ programming language এর। এই আর্টিকেল এ আমরা জানবো C structure বা C++ struct এর ব্যবহার।

প্রথমেই জানি  কখন আমাদের এই ফিচার ব্যবহার করা লাগতে পারে। ধরলাম আমরা একটি ফোন বুক প্রোগ্রাম বানাবো, যেখানে একাধিক ব্যাক্তির নাম, ঠিকানা, মোবাইল নাম্বার save করে রাখব। এখন সাধারনত আমরা কি করতাম ?


char name[1000][1001]; // each name can be upto 1000 character
int mobile [1000]; // we can store 1000 person's info
int home [1000];

এখন একটা ব্যাপার খেয়াল হতে পারে, আমি একি লোক এর জন্য, ৩ টি array ব্যবহার করছি, এখন ধরলাম, আমি এই প্রোগ্রাম এ আসল ডাটা গুলোর ব্যাকআপ হিশেবে আরো ৩ টা array  বানাবো। তাহলে কোড টা দাঁড়াচ্ছে এরকম-


char name[1000][1001]; // each name can be upto 1000 character
int mobile [1000]; // we can store 1000 person's info
int home [1000];

char backup_name[1000][1001]; // backup array
int backup_mobile [1000];
int backup_address [1000];

একি ব্যক্তি এর জন্য আমরা ৬ টা array declare করলাম, এখন কখনো যদি কোন array এর নাম পরিবর্তন করা লাগে, বা এরকম আরও ব্যাকআপ বানানো লাগে, তাহলে আমরা কিছু ঝামেলা তে পরব। তখন আমাদের মনে হতে পারে, যদি এই ৩ টা array কে একটা গ্রুপ এ রাখা যেতো, coding এ ঝামেলা কমতো। এই সমস্যা সমাধানে আমরা struct ব্যবহার করতে পারি।

এখন দেখা যাক, অই ৩ টা array কে কিভাবে একটি struct এ প্রকাশ করা যায়।


struct telephone{
char name[1001];
int mobile;
int home;
};

খেয়াল করো, struct লেখার পর একটা নাম দিতে হয়, [যেমন এখানে telephone] এই নাম দিয়েই আমরা পরে নতুন নতুন struct declare করতে পারবো। আর খেয়াল করতে হবে } এর শেষে ; [সেমিকোলন] দিতেই হবে, নাহলে compilation error হবে। এবার দেখা যাক, struct declare করা যায় কিভাবে-


struct telephone entry [1000];

এবার আমরা struct এর ভিতরের element গুলা কে access করতে চাই, কিভাবে করব, কোড দেখাই-


for(i=0;i<100;i++){
scanf(" %s",entry[i].name);
scanf("%d",&entry[i].mobile);
scanf("%d",&entry[i].home);
}

for(i=0;i<100;i++){
printf("%s",entry[i].name);
printf("%d",&entry[i].mobile);
printf("%d",&entry[i].home);
}

কাজ সহজ হয়ে গেলো অনেক , তাই না ?

এই struct feature ব্যবহার করে অনেক ডাটা স্ট্রাকচার , গ্রাফ প্রব্লেম এর অ্যালগরিদম সহজেই ইমপ্লেমেনট করা যায়।

2

UVA 12501: Bulky process of Reduction

~

UVA 12501: Bulky process of Reduction

Link: http://uva.onlinejudge.org/contests/310-4bd11ede/12501.html

Topic: Segment Tree with Lazy Propagation

This problem was given on BGC Trust University Programming Contest 12. But during the contest my team could not solve it. Later I tried this problem, got an analysis from Progkriya.com. But did not understand it properly, mayb I am newbie. 😦 Got TLE with that approach [ maybe implementation problem].

But after some googling, I have found this way. And this approach is easy to catch and a new trick to attack segment tree.

Problem Description Summary:

You will be given an array of N size, initialized with 100.

Then two of types of operation will be given.

1. change i j u

for this operation, you need to increase the numbers between index I and j by u.

for an example:

change 1 3 3

Index 1 2 3
Before Operation 100 100 100
After Operation 103 103 103

2. query i j

for this operation , you need to give some output according to the interval

for an example:

query 1 3

Index 1 2 3
Before Operation 100 106 104

Output will be

1*a[i]+ 2*a[i+1]+… +n*a[j]

So for this query output will be

1*100+2*106+3*104= 100+212+312=624

You need to print 624.

How to solve this problem??

After reading the problem, you might think, update can be done, but how to do the query. Crap!!

As we might think that, we need to traverse all the node between I and j. that would take O(nlogn). For n query, worst case will be O(n2logn).

That will give you TLE for sure.

Then how to solve it, any Mathematical formulation? So far I haven’t found any direct mathematical formula for this. But there is a Mathematical equation approach. Let’s find it out…

What if we initialize the array with this way.

Index 1 2 3 4 5
Primary Sum 100 100 100 100 100
Secondary Sum 100 200 300 400 500
Formula Index*100= 1*100 2*100 3*100 4*100 5*100

Remember this pattern of secondary sum, we need that later.

Hmm, now if a query comes for this interval [3, 5], output can be found with this formula

Secondary Sum of [3,5] – Primary sum of [3,5] * (3-1)

Generalized Equation:

For interval [ i , j ],

Output will be: Secondary sum of [ i , j] – Primary sum of [ i, j] * (i-1)

Solve this equation for arbitrary interval; check that you really get the correct output.

Now update process is kinda complex. For update process, you need to update both primary sum and secondary sum. Updating primary sum is trivial, but secondary sum is some Mathematical.

For secondary sum, we need to preserve the pattern property as we gave during the initialization.

If the operation comes like this way:

change 3 5 3

Index 1 2 3 4 5
Primary Sum Before Change 100 100 100 100 100
Secondary Sum before Change 100 200 300 400 500
Primary Sum After Change 100 100 103 103 103 
Secondary Sum after Change 100 100 Secondary Sum before Change+ index*u=300+ 3*3=309

 

 400+4*3=412 500+5*3=515

So now its upon you that how do you handle the lazy propagation.

Again If you need the code, please let me know.  🙂

2

SPOJ YODANESS LEVEL

~

SPOJ YODANESS LEVEL

Problem Statement is here: http://www.spoj.pl/problems/YODANESS/

Summary:  at first you will be given an order of strings, and then you will be given another order of strings. You need to find that how many pairs of words in the order are not in relative order.

Algorithm: Segment Tree [http://wcipeg.com/wiki/Segment_tree ], BIT

This Problem is solvable with both Segment tree and BIT. But I don’t know BIT very well, that’s why I am describing the segment tree approach.

Let’s check the first sample case first line:

in the force strong you are

We can give the words some number id, so that we can identify them easily.

If id of the word in is 1, then id of the word the is 2 and so on, then we can rewrite the sentence with numbers like this way

1 2 3 4 5 6

Now let’s see the second line:

you are strong in the force

Now we can change this to integers with the value of the first order. Then we can rewrite it as-

5 6 4 1 2 3

As you word have id of 5, are word have id of 6 and so on.

Now what’s the benefit of this? Let’s check.

We will use Segment Tree now-

We will sort the value in Descending order with keeping the index information. Here’s the table will become-

Value

 6 5 4 3 2 1
Index 2 1 3 6 5 4

Now we will run loop on this sequence then do some query and update.

Initially we will assume that our array is empty.

First iteration:

I get value of 6 and index of 2. So we will do sum query on this [1, 2] interval, then add it with ultimate result. Now update the index 2 with 1. Array becomes

Index

 1 2 3 4 5 6
Value 1

Second Iteration:

I have value of 5, and index of 1, So again do a sum query on the interval [1,1] and add the result with ultimate result. And obviously update the index with 1. So the array becomes

Index 1 2 3 4 5 6
Value 1 1

Third Iteration:

Now Value is 4, index is 3, now do the query on [1,3], you will get 2, because before 4, we have 5,6 which are not in relative order with 4. So add 2 with the ultimate result. Update the index 3 with 1.

Index 1 2 3 4 5 6
Value 1 1 1

So on….

I am not showing the segment tree code… If you really need it… I will add it up…