বাংলা টিউটোরিয়াল

বাংলা টিউটোরিয়াল

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

সাধারণ ধারণা

কেন আমি প্রোগ্রামিং শিখবো?

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

প্রোগ্রামিং কনটেস্ট এবং অনলাইন জাজে হাতেখড়ি

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

শুরুর আগে
প্রোগ্রামিং চর্চার বিষয়। ইন্টারনেটে বেশ কিছু ওয়েবসাইট আছে, যেখানে প্রচুর সমস্যা দেওয়া আছে যেগুলো প্রোগ্রামের সাহায্যে সমাধান করতে হয়। সব জায়গাতেই তুমি সি ল্যাঙ্গুয়েজে প্রোগ্রামিং করতে পারবে। এর মধ্যে কিছু কিছু ওয়েবসাইট আবার নিয়মিত প্রোগ্রামিং প্রতিযোগিতারও আয়োজন করে।

প্রথম প্রোগ্রাম
আমরা এখন একটি প্রোগ্রাম লিখে ফেলব, যেটি তোমার কম্পিউটারের স্ক্রিনে Hello World দেখাবে বা প্রিন্ট করবে। এটি হচ্ছে প্রোগ্রামিংয়ের একটি ঐতিহ্য।

ডাটা টাইপ, ইনপুট ও আউটপুট (Data type, input, output)
সব প্রোগ্রামিং ল্যাঙ্গুয়েজে ভেরিয়েবল বলে একটি জিনিস আছে যেটি কোন নির্দিষ্ট মান ধারণ করার জন্য ব্যবহার করা হয়। ভেরিয়েবলের একটি নাম দিতে হয়, তারপর ভেরিয়েবল = কোনো মান  লিখে দিলে ভেরিয়েবলের ভেতর সেটি ঢুকে যায়।

কন্ডিশনাল লজিক (Conditional Logic)
প্রোগ্রামাররা যেভাবে প্রোগ্রাম লিখে দেয় কম্পিউটার সেভাবে কাজ করে। এখন আমরা প্রোগ্রামিংয়ের সহজ অথচ খুব গুরুত্বপূর্ণ একটি বিষয় শিখব। সেটি হচ্ছে কন্ডিশনাল লজিক।

লুপ (Loop)
সব প্রোগ্রামিং ল্যাঙ্গুয়েজেই লুপ (loop) বলে একটি পদ্ধতি রয়েছে। এটি দিয়ে একই কাজ বারবার করা যায়। লুপের মধ্যে একটি শর্ত বসিয়ে দিতে হয়, যেটি পূরণ না হওয়া পর্যন্ত প্রোগ্রামটি লুপের ভেতরের কাজ বারবার করতে থাকবে।

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

অ্যারে (Array)
প্রায় সব প্রোগ্রামিং ল্যাংগুয়েজেই অ্যারে (Array) নামে একটি চমৎকার জিনিস আছে। এতে একই ধরনের অনেকগুলো ভেরিয়েবল একসঙ্গে রাখা যায়

ফাংশন (Function)
ফাংশন ব্যবহার করা হয় কোনো একটি নির্দিষ্ট কাজ করার জন্য। যেমন printf ফাংশনটি দিয়ে আমরা মনিটরে আউটপুট দিই। আবার scanf, getchar এসব ফাংশন দিয়ে আমরা কিবোর্ড থেকে ইনপুট নিই।

বাইনারি সার্চ (Binary Search)
এখন আমরা দেখব একটি অ্যারে থেকে কীভাবে বাইনারি সার্চ করে কোনো সংখ্যা খুঁজে বের করতে হয়। অ্যারেতে কিন্তু সংখ্যাগুলো ছোট থেকে বড় কিংবা বড় থেকে ছোট ক্রমানুসারে থাকতে হবে।

স্ট্রিং (String)
এক বা একাধিক character মিলে string তৈরি হয়। সোজা কথায় স্ট্রিং হচ্ছে ক্যারেক্টার টাইপের অ্যারে। তবে প্রোগ্রামিংয়ে এটির ব্যবহার এতই বেশি যে কোনো কোনো ল্যাঙ্গুয়েজে স্ট্রিংকে আলাদা একটি ডাটা টাইপ হিসেবে ধরা হয়।

মৌলিক সংখ্যা (Prime number)
মৌলিক সংখ্যা (Prime Number) গণিতবিদদের কাছে যেমন প্রিয়, তেমনই প্রোগ্রামারদেরও অনেক প্রিয় একটি বিষয়।

আবারও অ্যারে
নেস্টেড লুপের সাহায্যে আমরা ইনপুট নিতে পারি। প্রথম লুপটি ব্যবহার করা হয় রো-এর জন্য আর দ্বিতীয় লুপটি কলামের জন্য।

বাইনারি সংখ্যা পদ্ধতি
কম্পিউটার ব্যবহার করে দুইভিত্তিক বা বাইনারি (binary) সংখ্যা পদ্ধতি। দশভিত্তিক সংখ্যা পদ্ধতিতে আছে মোট দশটি অঙ্ক 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 আর বাইনারিতে দুটি, 0 আর 1।
 
কিছু প্রোগ্রামিং সমস্যা
কিছু সাধারণ প্রোগ্রামিং সমস্যা নিয়ে বিস্তর আলোচনা।
 
শেষের শুরু
একজন দক্ষ প্রোগ্রামার হতে গেলে যে জিনিসগুলো লাগবে তা জানতে হলে পড়ে ফেল লেখাটি।

অ্যাডভান্সড বিষয়

সি++ এর প্রাথমিক ধারণা

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

সি++ স্ট্যান্ডার্ড টেম্প্লেট লাইব্রেরী

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

সি++ এসটিএল ::ভেক্টর

অ্যারে আমাদের সবারই বিশেষভাবে পরিচিত, এবং সবার খুবই প্রিয় একটা ডাটা-স্ট্রাকচার হল অ্যারে। কোন কোডে অ্যারে ব্যবহার করতে পারলেই কেমন যেন শান্তি শান্তি লাগে… অ্যারের সবচেয়ে আকর্ষনীয় ফিচার মনে হয় তার ইন্ডেক্সিং (মানে র‍্যান্ডম অ্যাকসেস)।

সি++ এসটিএল :: স্ট্যাক

STL কন্টেইনারদের মধ্যে সম্ভবত সবচেয়ে সিম্পল ডাটা স্ট্রাকচার হল stack, এটা একটা লাস্ট ইন ফার্স্ট আউট (LIFO) ডাটা স্ট্রাকচার, মানে হল যে সবার শেষে আসবে, সে সবার আগে ভাগবে… সোজা কথায় এই কন্টেইনারের শুধুমাত্র একটা দিকেই ডাটা ইন্সার্ট বা এক্সট্র্যাক্ট করা হয়।

সি++ এসটিএল :: পেয়ার

কন্টেস্ট প্রোগ্রামিং-এ সাধারনতঃ খুব কমপ্লেক্স ডাটা টাইপ বানাতে হয় না। সেখানে বেশি প্রয়োজন খুব দ্রুত আর নির্ভুল কোডিং।

সি++ এসটিএল :: কিঊ

আগে আসলে আগে পাবেন, এই রকমের একটা ডাটা স্ট্রাকচার হল কিউ, যাকে আমরা বলি ফার্স্ট ইন ফার্স্ট আউট (FIFO)। এটা C++ STL এর সবচেয়ে বেশি ব্যবহৃত কন্টেইনার ক্লাস।

সি++ এসটিএল :: প্রায়োরিটি কিউ

সব ডাটা-স্ট্রাকচারই যে ধোয়া তুলসি পাতা, এইটা বলা যায় না, বিশেষতঃ যখন “জোর যার মুল্লুক তার” টাইপের এই ডাটা-স্ট্রাকচারটা প্রায়ই ব্যবহার করতে হয়, C++ STL এর priority_queue, এটা একটা বাইনারি হিপ ডাটা-স্ট্রাকচার (ডিফল্টঃ ম্যাক্স হিপ)।

সি / সি প্লাস প্লাস স্ট্রাকচার
C++ Struct একটি অত্যন্ত জরুরি ফিচার C/C++ programming language এর। এই আর্টিকেল এ আমরা জানবো C structure বা C++ struct এর ব্যবহার।
 
সর্টিং বা বাছাই করার পদ্ধতি
বাছাই করা, অর্থাৎ ক্রমানুসারে সাজানো তথ্য বিশ্লেষণের একটি মৌলিক সমস্যা। কম্পিউটার বিজ্ঞানে এই সমস্যাটির সমাধানের কৌশলগুলোকে বলে সর্টিং অ্যালগরিদম। আজ আমরা দেখবো এই সর্টিং এর কিছু সহজ কৌশল।

অ্যারে কম্প্রেশন

খুবই সহজ কিন্তু দরকারি একটা টেকনিক নিয়ে আলোচনা করবো আজকে। STL এর ম্যাপ ব্যবহার করে আমরা অ্যারে কম্প্রেশন করবো। মনে করো কোনো একটা প্রবলেমে তোমাকে বলা হলো একটি অ্যারেতে ১ লাখটা সংখ্যা দেয়া থাকবে যাদের মান হবে ০ থেকে সর্বোচ্চ ১০০০। এখন যেকোনো আমি একটি সংখ্যা বললে তোমাকে বলতে হবে অ্যারের কোন কোন পজিশনে সংখ্যাটি আছে।

অ্যালগোরিদম কমপ্লেক্সিটি(বিগ “O” নোটেশন)

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

অ্যালগরিদম

ব্যাকট্র্যাকিং অ্যালগোরিদম: পারমুটেশন জেনারেটর

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

মিনিমাম ভারটেক্স কভার প্রবলেম

মিনিমাম ভারটেক্স কভার একটি ক্লাসিক গ্রাফ প্রবলেম। ধরা যাক একটি শহরে কিছু রাস্তা আছে,এখন প্রতি রাস্তায় মোড়ে আমরা পাহারাদার বসাতে চাই। কোনো নোডে পাহারাদার বসালে সে নোডের সাথে যুক্ত রাস্তাগুলো একাই পাহারা দিতে [...]

ডিরেকশন অ্যারে

অনেক সময়ই এমন প্রবলেম থাকে যেখানে বলা হয় তুমি একটা ২-ডি অ্যারের কোনো এক পজিশনে আছো, সেখান থেকে তুমি উপরে-নিচে-বামে-ডানে যেতে পারবে। অথবা দাবার বোর্ডে একটা ঘোড়া আছে, তাকে ৮টা দিকে মুভ করানো যায়, এখন কোনো একটা পজিশনে শর্টেস্ট পাথে যেতে হবে। বিগিনার কোডাররা এ ধরণের প্রবলেমে ছোট্ট একটা ট্রিকস না জানার কারণে কোডের সাইজ [...]

ট্রি এর ডায়ামিটার নির্ণয়

ট্রি এর ডায়ামিটার হলো পরস্পর থেকে সবচেয়ে দূরে অবস্থিত দুটি নোডের দূরত্ব। নিচের ছবিতে ট্রি এর ডায়ামিটার ৩। ট্রি ডায়ামিটার বের করার একটি সহজ পদ্ধতি হলো দুইবার dfs,bfs বা dijkstra চালানো। ১: প্রথমে যে কোনো একটি নোড থেকে সবথেকে দূরের নোড বের করতে হবে(একাধিক নোড থাকলে যেকোনো একটি নিতে হবে) ।

ইউভিএ ১০৭০২(ট্রাভেলিং সেলসম্যান)

ট্রাভেলিং সেলসম্যান মূলত একটি NP-complete ক্লাসিকাল প্রবলেম। uva 10702 মূল প্রবলেমের পরিবর্তিত রূপ যা ডাইনামিক প্রোগ্রামিং এর মাধ্যমে সমাধান করা সম্ভব। একজন ফেরিওয়ালা এক শহর থেকে অন্য শহরে ঘুরে জিনিসপত্র বিক্রি করে। সে কোনো শহরে একাধিক বার যেতে পারে(ক্লাসিক tsp প্রবলেমে একটি নোড একবারের বেশি ভিজিট করা যায়না)।

ডাইনামিক প্রোগ্রামিং এ হাতেখড়ি-১(শুরুর কথা)

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

ডাইনামিক প্রোগ্রামিং এ হাতেখড়ি-২

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

ডাইনামিক প্রোগ্রামিং এ হাতেখড়ি-৩

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

ডাইনামিক প্রোগ্রামিং এ হাতেখড়ি-৪

০-১ ন্যাপস্যাক,কয়েন চেঞ্জ প্রবলেমে আশা করি তোমার এখন দক্ষতা এসে গিয়েছে। এই পর্বে আমরা দেখবো LIS, একই সাথে দেখবো কিভাবে ডিপিতে সলিউশন প্রিন্ট করতে হয় ,এটা নিয়ে তোমাদের অনেকেরই সমস্যা হয়েছে বলে জানিয়েছো। এছাড়া আগের পর্বে light oj 1231 প্রবলেমটি সলভ করতে বলেছিলাম,আমার সলিউশন পাবে লেখার একদম শেষে। এছাড়া দেখবো বুলিয়ান অ্যারে ব্যবহার করে ডিপি [...]

ডাইনামিক প্রোগ্রামিং এ হাতেখড়ি-৫

আশা করি তুমি এখন lis,knapsack,coin-change প্রবলেম সলভ করতে পারো খুব সহজেই, ডিপির সলিউশন প্রিন্ট করতেও তোমার সমস্যা হয়না। এখন আমরা একটু অন্যরকম ডিপি দেখবো যেটার নাম বিটমাস্ক ডিপি। নামটা শুনে ভয় লাগলেও জিনিসটা সহজ, অনেক ক্ষেত্রেই বিটমাস্ক ডিপি প্রবলেম পড়ার সাথে সাথে সলিউশন মাথায় চলে আসে। তবে এই পর্বটা পড়ার আগে তোমাকে বিট নিয়ে কাজ [...]

গ্রাফ থিওরিতে হাতেখড়ি – ১

মনে করো তুমি একটি পিরামিডের ভিতরে ঢুকেছো হাজার বছর আগের ধনরত্নের সন্ধানে। তোমার কাছে আছে একটি মাত্র টর্চ লাইট যার ব্যাটারি শেষ হয়ে যাবে ২ ঘন্টা পরেই, এর মধ্যেই তোমাকে সেই রত্ন নিয়ে বের হয়ে আসতে হবে। তোমার কাছে একটি ম্যাপ আছে যেখানে পিরামিডের ভিতরের টানেলগুলো আকা আছে, তুমি জানো কোন টানেল দিয়ে যেতে তোমার [...]

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

গ্রাফ স্টোর করার সবথেকে সহজ পদ্ধতি adjacency ম্যাট্রিক্স। নিচের ছবিটি দেখ: গ্রাফের পাশে একটি টেবিল দেখতে পাচ্ছ। এটাই adjacency ম্যাট্রিক্স. এই ম্যাট্রিক্সের প্রতিটি ঘর mat[i,j] নির্দেশ করে নোড i আর নোড j এর [...]

গ্রাফ থিওরিতে হাতেখড়ি – ৩ (ভ্যারিয়েবলে গ্রাফ স্টোর-২)

এই পর্বে গ্রাফ স্টোর করার ২য় পদ্ধতি adjacency লিস্ট নিয়ে লিখব। এ পদ্ধতিতে গ্রাফ স্টোর করে কম মেমরি ব্যবহার করে আরো efficient কোড লেখা যায়। এ ক্ষেত্রে আমরা ডায়নামিক্যালি মেমরি অ্যালোকেট করব,পিওর সি তে কাজটা করা ঝামেলা,তাই সি++ এর standard template library(STL) ব্যবহার করে কাজটি করব। আগের লেখার শেষের দিকে STL [...]

গ্রাফ থিওরিতে হাতেখড়ি-৪(ব্রেথড ফার্স্ট সার্চ(bfs))

আমরা যে অ্যালগোরিদমটা শিখব তার নাম breadth first search বা bfs। এটা ব্যবহার করে আমরা এখন unweighted গ্রাফে ২টি নোডের ভিতর শর্টেস্ট পাথ বের করব,unweighted বলতে বুঝাচ্ছি সবগুলো নোডের মধ্যে দুরত্ব সমান,আমরা ধরে নিব দুরত্ব [...]

গ্রাফ থিওরিতে হাতেখড়ি-৫(কোডিং বিএফএস)

এবার আমরা bfs এর কোড লিখতে শিখব। আমরা এখন জানি যে bfs এ আমাদের কাজ হলো গ্রাফটিকে একটি একটি লেভেলে ভাগ করা,যে যত নম্বর লেভেলে আছে [...]

গ্রাফ থিওরিতে হাতেখড়ি ৬: মিনিমাম স্প্যানিং ট্রি(prim’s mst)

মিনিমাম স্প্যানিং ট্রি গ্রাফ থিওরির খুব গুরুত্বপূর্ণ একটি অংশ। এই টিউটোরিয়ালে গ্রাফ থেকে মিনিমাম স্প্যানিং ট্রি নির্ণয়ের একটি অ্যালগোরিদম নিয়ে আলোচনা করবো। একটি গ্রাফ থেকে কয়েকটি নোড আর edge নিয়ে নতুন একটি গ্রাফ তৈরি করা হলে সেটাকে বলা হয় subgraph। স্প্যানিং ট্রি হলো এমন একটি সাবগ্রাফ যেটায়: * মূল গ্রাফের সবগুলো নোড [...]

গ্রাফ থিওরিতে হাতেখড়ি ৭:ক্রুসকাল অ্যালগোরিদম(mst)

mst বের করার আরেকটি অ্যালগোরিদম যা ক্রুসকালের অ্যালগোরিদম নামে পরিচিত। এটি mst নির্ণয়ের সবথেকে সহজ অ্যালগোরিদম। তবে তোমাকে অবশ্যই ডিসজয়েন্ট সেট ডাটা স্ট্রাকচার সম্পর্কে জানতে হবে,না জানলে এই পোস্টটি অবশ্যই [...]

গ্রাফ থিওরিতে হাতেখড়ি ৮:টপোলোজিকাল সর্ট

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

গ্রাফ থিওরিতে হাতেখড়ি ৯: ডেপথ ফার্স্ট সার্চ এবং আবারো টপোলোজিকাল সর্ট

bfs এ আমরা গ্রাফটাকে লেভেল বাই লেভেল সার্চ করেছিলাম[...]

গ্রাফ থিওরিতে হাতেখড়ি-১০ (ডায়াক্সট্রা ডায়াক্সট্রা!)

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

গ্রাফ থিওরি: স্টেবল ম্যারেজ প্রবলেম

আজকে আমরা একটা সহজ কিন্তু ইন্টারেস্টিং প্রবলেম দেখবো। স্টেবল ম্যারিজ(Stable Marriage) প্রবলেম এক ধরনের বাইপারটাইট ম্যাচিং প্রবলেম,তবে এটা শেখার জন্য অন্য কোনো অ্যালগোরিদম জানার প্রয়োজন নেই। মনে করি n টা ছেলে আর n টা মেয়ে আছে। এখন তাদের মধ্যে বিয়ে দিতে হবে এমন ভাবে [...]

টপোলজিকাল সর্ট - লিংক

রিকার্শন, সার্চিং এবং ডাইনামিক প্রোগ্রামিং - বেসিকস - লিংক

শর্টেস্ট পাথের অ্যালগরিদম - লিংক 

শর্টেস্ট পাথ - প্রবলেম নিয়ে বকর বকর - লিংক

পরিশিষ্ট

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

কন্টেস্ট্যান্টদের জন্য বেসিক সিপিপি  -  লিংক

স্ট্যান্ডার্ড টেম্প্লেট লাইব্রেরী - লিংক

ভিম নিয়ে বকরবকর - লিংক

টপকোডারে ইন্ট্রো - লিংক

টপকোডারে প্লাগ ইন ইন্সটল করা - লিংক

কন্টেস্ট টিপস - লিংক

বিগেনারদের জন্য - লিংক

প্রোগ্রামিং
প্রোগ্রামিং কখন শিখব, শুরুতে কোন ল্যাঙ্গুয়েজ শিখব, কম্পিউটার সায়েন্স না পড়েও কি প্রোগ্রামার হওয়া যাবে, ইত্যাদি নানা রকমের প্রশ্নের উত্তর।

প্রোগ্রামিং প্রতিযোগিতা
প্রোগ্রামিং প্রতিযোগিতার খুঁটিনাটি।

প্রোগ্রামিং ক্যারিয়ার
প্রোগ্রামিং জগতের ক্যারিয়ার কেমন হবে? ভবিষ্যৎ চাহিদা কি? জানতে হলে ঢুঁ মারুন।

বই ও ওয়েবসাইটের তালিকা
কিছু প্রোগ্রামিং বইইয়ের পিডিএফ ভার্সন আর ওয়েবসাইটের তালিকা আছে এই লিঙ্কটিতে।

লিস্ট

কম্পিউটেশনাল জিওমেট্রি প্রবলেমঃ শাহরিয়ার রউফ নাফি
SPOJ লিস্টঃ মীর ওয়াসি আহমেদ

বাংলাদেশি ব্লগ

মোঃ আরিফুজ্জামান আরিফ
সাব্বির ইউসুফ সানি
মশিউর রহমান
আনা ফারিহা
যোবায়ের হাসান
শাফায়েত আশরাফ
আহমদ ফাইয়াজ
মীর ওয়াসি আহমেদ
আহমেদ শামসুল আরেফীন

বিদেশি ব্লগ

পেয়তর মিত্রিচেভের ব্লগঃ পেয়তর মিত্রিচেভ বিশ্বের সবচেয়ে সফল কম্পিটিটিভ প্রোগ্রামারদের একজন। তার ব্লগের বিশেষত্ব হল বড় কনটেস্ট গুলোর (এসিএম আইসিপিসি ওয়ার্ল্ড ফাইনালস, টপকোডার ওপেন) কাভারেজ এবং প্রবলেমসেটের বিশ্লেষণ।
ভেক্সোরিয়ান এর ব্লগঃ ভিক্টর হুগো সলিজ কুনকার ওরফে ভেক্সোরিয়ান টপকোডারে তার বিস্তারিত এবং সহজবোধ্য প্রবলেমসেট অ্যানালাইসিসের জন্যে বিখ্যাত।
লেকার্সের ব্লগঃ (জাপানি ভাষায়) হিরোতো সেকিদো ওরফে লেকার্স দীর্ঘদিন ধরে ধারাবাহিকভাবে ইউভিএর কনটেস্টগুলোতে দুর্দান্ত পার্ফরমেন্স দেখিয়ে আসছেন।
যেজুন উয়ের ব্লগঃ (চীনা ভাষায়) যেজুন উ ২০১১ সালের এসিএম আইসিপিসি ওয়ার্ল্ড ফাইনালসের চ্যাম্পিয়ন দলের সদস্য ছিলেন। তার এই ব্লগটিতে ZOJ Monthly এর সেটগুলোর বিশ্লেষণ আছে।

ট্রেনিং সাইট

ইউসাকো

টপকোডার অ্যালগোরিদম টিউটোরিয়াল
ম্যাক্সিম ইভানভ (e-maxx) এর সাইট
পেগউইকি
এমআইটির অ্যালগোরিদম কোর্স
জেফ এরিকসনের অ্যালগোরিদম নোটস

কনটেস্টের সময়সূচী

অ্যালেক্সেই রোপানের কনটেস্ট লিস্ট

কনটেস্ট আর অনলাইন জাজ

টপকোডারঃ সারাবিশ্বের প্রোগ্রামারদের মাঝে অত্যন্ত জনপ্রিয় একটা প্রোগ্রামিং কন্টেস্ট। অ্যালগোরিদম ট্র্যাকে মাসে গড়ে ৩ টার মতো কনটেস্ট হয়। দেড় ঘন্টা সময়ে ৩টা প্রবলেম সলভ করতে বলা হয়।
কোডফোর্সেসঃ আরেকটি অসাধারণ সাইট। অনেকটা টপকোডারের  তবে নিয়মকানুনগুলো আইসিপিসি কনটেস্টের মতো।
আইপিএসসিঃ স্লোভাক বার্ষিক কনটেস্ট। ওপেন আর স্কুল-কলেজের ছাত্রছাত্রীদের জন্যে সেকেন্ডারি ডিভিশন। প্রবলেম আর্কাইভে আগের সব কনটেস্টের সলুশন আছে।
লাইট ওজেঃ বাংলাদেশি অনলাইন জাজ। নতুনদের জন্যে আদর্শ। বানিয়েছেন জানে আলম জান যিনি ২০০৯ সালের এসিএম ফাইনালিস্ট, বর্তমানে গুগলে কর্মরত। প্রবলেমগুলো ক্যাটাগরী অনুযায়ী ভাগ করা।
স্ফিয়ার অনলাইজ জাজ (স্পজ): পোলিশ অনলাইন জাজ। অনেক ভালো প্রবলেম আছে। তবে ইদানিং অনেককেই প্রবলেম যোগ করার সুযোগ করে দেওয়ার প্রবলেমের সংখ্যা মাত্রাতিরিক্ত হয়ে গেছে। প্র্যাকটিসের জন্যে উপযুক্ত প্রবলেম বাছাই করার জন্যে প্রতীক ট্যান্ডেল বা ভিএনওআই এর টুল ব্যবহার করা সুবিধাজনক।
সারাতভ ইউনিভার্সিটি অনলাইন জাজঃ এই রাশান জাজটিতে মাত্র ৫০০ এর মতো প্রবলেম আছে। কিন্তু প্রতিটা প্রবলেমই মানসম্মত। একেবারে নতুনদের জন্যে উপযোগী নয়।
ইউনিভার্সিটি অফ ভ্যালাদোলিদ অনলাইন জাজ ওরফে ইউভিএঃ ইউভিএ বোধহয় বাংলাদেশের সবচেয়ে জনপ্রিয় জাজ। অনেক পুরোনো জাজ এই ইউভিএ। এই সাইটে এক সময় প্রতি মাসেই নিয়ম করে কনটেস্ট হতো। ইউভিএর জনপ্রিয়তম কনটেস্ট হলো রিজিওনাল আর ওয়ার্ল্ড ফাইনালস ওয়ার্মআপ। এই সাইটে হাজার হাজার প্রবলেম আছে। প্রাকটিসের জন্যে ইউভিএটুলকিট বা ইগর এর টুল ব্যবহার করা যায়। মিগুয়েল রেভিয়ার  বই ‘প্রোগ্রামিং চ্যালেঞ্জেস’ আর ফেলিক্স ও স্টিভেন হালিমের বই ‘কম্পিটিটিভ প্রোগ্রামিং’ এই সাইটের প্রবলেমের উপর ভিত্তি করে লেখা।
আইসিপিসি লাইভ আর্কাইভঃ ইউভিএরই অংশ, তবে এখানে বিভিন্ন বছরের রিজিওনাল আর ওয়ার্ল্ড ফাইনালসের প্রবলেম আছে।
কোডশেফঃ ভারতীয় কোম্পানী Directi এর স্পন্সরশীপে আয়োজিত কনটেস্ট। প্রতি মাসে ১০ দিন ব্যাপী অত্যন্ত চ্যালেঞ্জিং কিছু প্রবলেম সলভ করতে দেওয়া হয়। আবার কুক-অফ নামের কম সময়ের আরেকটি কনটেস্ট আয়োজন করে তারা।
হুয়াজহং ইউনিভার্সিটি অফ সায়েন্স অ্যান্ড টেকনলজি ওরফে হাস্টঃ এই সাইটের সবচে আকর্ষণীয় দিক হচ্ছে ভার্চুয়াল জাজ। এর বিশেষত্ব হচ্ছে বিভিন্ন জনপ্রিয় অনলাইন জাজের প্রবলেম নিয়ে ভার্চুয়াল কনটেস্ট করা যায়।
যেড ট্রেনিং: এই জাজটিতে প্রধানতঃ ইনফরম্যাটিক্স অলিম্পিয়াড স্টাইলের প্রবলেম আছে। বেশ ভালো মানের জাজই বলতে হবে একে।
টাইমাস অনলাইন জাজঃ আরেকটি রাশান জাজ। মূলত রাশান কনটেস্টের প্রবলেম আছে।
পিকিং অনলাইন জাজঃ পিকিং ইউনিভার্সিটির জাজ। অনেক প্রবলেম। ইউসাকো মান্থলি কনটেস্টের প্রবলেম আছে।
ঝেজিয়াং অনলাইজ জাজঃ আরেকটি চীনা জাজ। ZOJ Monthly এর প্রবলেমগুলো বেশ চ্যালেঞ্জিং।

ইনফরম্যাটিক্স অলিম্পিয়াড

ক্রোয়েশিয়ান অলিম্পিয়াড
পোলিশ অলিম্পিয়াড