Topic 13 · Revision
Last-Minute Cheat Sheet
পরীক্ষার আগের শেষ ৩০ মিনিটের জন্য। ১২টা টপিকের সব নিয়ম, সূত্র, complexity আর
ফাঁদ — এক পাতায়। নতুন কিছু শেখার জায়গা নয়, মনে করার জায়গা।
পরীক্ষার আগে অবশ্যই
সময় ≈ ২০ মিনিট
Print করে নিতে পারো
১. Graph — Basics
Adjacency Matrix
M[i][j] = 1 যদি i → j edge থাকে- Undirected → দুই ঘরেই 1, matrix symmetric
- Weighted → 1 এর বদলে weight; edge না থাকলে
∞ (0 নয়)
- Space
O(V²) · edge check O(1)
Adjacency List
- প্রতি vertex এর পাশে প্রতিবেশীদের নাম
- Undirected এ প্রতিটা edge দুইবার লেখা হয়
- Space
O(V + E)
- Sparse graph এ ভালো; BFS/DFS
O(V+E)
Handshaking Lemma: Σ degree = 2 × E — গাছ বা graph আঁকার পর এটা দিয়ে যাচাই করো।
সর্বোচ্চ edge (simple undirected): V(V−1)/2
In-degree = ভেতরে ঢোকা edge · Out-degree = বাইরে যাওয়া edge (Kahn's এ লাগে)
২. BFS ও DFS
তিনটা নিয়ম যা ভুললেই উত্তর ভুল:
১। প্রতিবেশীদের alphabetical/সংখ্যার ক্রমে নাও (প্রশ্নে অন্য কিছু না বললে)
২। Queue/Stack এ ঢোকানোর সময়েই visited চিহ্ন দাও, বের করার সময় নয় — নইলে একই node দুইবার ঢুকবে
৩। DFS এ backtrack এর ধাপগুলোও টেবিলে দেখাও — এখানেই নম্বর
৩. Topological Sort
শর্ত: শুধু DAG (Directed Acyclic Graph) এ সম্ভব। Cycle থাকলে
topological sort হয় না — এই লাইনটা লিখতে ভুলো না।
একাধিক উত্তর বৈধ — তোমারটা নিয়ম মানলেই সঠিক।
পদ্ধতি ১ — DFS + Stack
- যেকোনো unvisited node থেকে DFS চালাও
- কোনো node এর সব প্রতিবেশী শেষ হলে (finish হলে) তাকে stack এ push করো
- সব শেষে stack উল্টে পড়ো — এটাই উত্তর
মনে রাখো: push হয় ফেরার সময়, যাওয়ার সময় নয়।
পদ্ধতি ২ — Kahn's (In-degree)
- সবার in-degree হিসাব করো
- in-degree 0 ওয়ালাদের queue তে দাও
- একটা বের করো → উত্তরে লেখো → তার প্রতিবেশীদের in-degree ১ করে কমাও
- নতুন করে 0 হলে queue তে দাও; queue খালি হলে শেষ
Cycle ধরা: সব node বের না হলে cycle আছে।
৪. Dijkstra
Relaxation সূত্র (মুখস্থ):
if ( d[u] + c(u,v) < d[v] ) then d[v] = d[u] + c(u,v)
Undirected graph দেওয়া থাকলে আগে directed এ রূপান্তর করো — প্রতিটা edge কে
দুই দিকে ভেঙে নাও। (স্যার এটা আলাদা করে বলে দিয়েছেন।)
ধাপ: শুরুতে source এর দূরত্ব 0, বাকি সব ∞ → প্রতিবার
সবচেয়ে ছোট দূরত্বের unvisited vertex select করো → তার প্রতিবেশীদের relax করো →
select করা vertex আর কখনো বদলাবে না।
Selected Vertex টেবিল আকারে লিখলে সবচেয়ে পরিষ্কার হয়।
দুর্বলতা: Negative weight এ Dijkstra কাজ করে না। (Bellman-Ford সিলেবাসে নেই।)
Complexity: O(V²) array দিয়ে · O((V+E) log V) min-heap দিয়ে
৫. Binary Tree Traversal
Preorder : Root → Left → Right
Inorder : Left → Root → Right
Postorder : Left → Right → Root
Level order: উপর থেকে নিচে, বাম → ডান (Queue)
মনে রাখার কৌশল
- Pre = root আগে · In = root মাঝে · Post = root পরে
- Left সবসময় Right এর আগে — তিনটাতেই
- Preorder এর প্রথম = root · Postorder এর শেষ = root
Terminology: Height = সবচেয়ে লম্বা পথের edge সংখ্যা · Depth = root থেকে ওই node পর্যন্ত edge ·
Level = root এর level 0 · Leaf = child নেই এমন node
Node সংখ্যা: h height এর গাছে সর্বোচ্চ 2^(h+1) − 1 টা node ·
level L এ সর্বোচ্চ 2^L টা
৬. Traversal থেকে Tree
সাধারণ Tree এর নিয়ম: Pre/Post থেকে root নাও → Inorder এ root খুঁজে দুই ভাগ করো →
গুনে Pre/Post ও একই অনুপাতে ভাগ করো → recursion।
BST এর নিয়ম: root নাও → বাকিদের মান তুলনা করে ছোট/বড় দুই ভাগে ভাগ করো
(গুনতে হয় না) → recursion। শর্টকাট: preorder এর ক্রমে insert করলেই গাছ পাওয়া যায়
(postorder হলে reverse করে insert)।
কেন BST তে একটাই যথেষ্ট: BST এর inorder সবসময় sorted — নিজেরাই বানিয়ে নেওয়া যায়।
৭. BST — Insert / Delete
Property: বাম subtree এর সব < node < ডান subtree এর সব
(শুধু child নয়, পুরো subtree)।
যাচাই: Inorder বের করো — sorted হলে বৈধ BST।
Insert: root থেকে নামো (ছোট→বাম, বড়→ডান), খালি জায়গা পেলে বসাও।
নতুন node সবসময় leaf।
Inorder Successor: একবার ডানে যাও, তারপর যতদূর সম্ভব বামে নামো।
Inorder Predecessor: একবার বামে যাও, তারপর যতদূর সম্ভব ডানে নামো।
দুইটার যেকোনো একটা ব্যবহার করা যায় — কোনটা করছ খাতায় লিখে দাও।
Successor এর কখনো বাম child থাকে না — তাই তাকে delete করা সবসময় Case 1 বা 2।
৮. Heap — সব নিয়ম
Index (1-based):
Left child = 2i Right child = 2i + 1 Parent = i / 2 (floor)
0-based হলে: left = 2i+1, right = 2i+2, parent = (i−1)/2
Max Heap: parent ≥ child ·
Min Heap: parent ≤ child
Heap সবসময়
complete binary tree; height =
⌊log₂ n⌋
তিনটা সবচেয়ে বড় ফাঁদ:
১। Delete এ শেষ element কে উপরে আনতে হয়, বড় child কে নয়
২। Heapify down এ বড় child এর সাথে swap (min heap এ ছোট child) — একটা swap করে থেমো না, যতদূর দরকার নামো
৩। Delete এর পর heap size কমাতে ভুলো না — নইলে মুছে ফেলা element আবার heap এ ঢুকে যাবে
Max Heap দিয়ে sort = ascending · Min Heap দিয়ে sort = descending
৯. Complexity টেবিল
১০. সূত্র সংগ্রহ
Handshaking Lemma : Σ degree = 2 × E
সর্বোচ্চ edge (undirected) : V (V − 1) / 2
Heap index (1-based) : left = 2i , right = 2i + 1 , parent = i / 2
Heap height : ⌊ log₂ n ⌋
Tree এ সর্বোচ্চ node : 2^(h+1) − 1 (h = height, edge গুনে)
Level L এ সর্বোচ্চ node : 2^L
n node এর BST সংখ্যা : Catalan(n) = (2n)! / ( n! (n+1)! )
Dijkstra relaxation : if ( d[u] + c(u,v) < d[v] ) d[v] = d[u] + c(u,v)
Build heap শুরু index : n / 2 (এর পরেরগুলো সব leaf)
১১. টপ ২০ ফাঁদ
- Undirected matrix এ এক দিকে 1 বসানো — দুই দিকেই লাগবে
- Weighted matrix এ edge না থাকলে 0 বসানো —
∞ হবে
- BFS/DFS এ প্রতিবেশীর ক্রম এলোমেলো করা
- Queue/Stack এ ঢোকানোর সময় visited চিহ্ন না দেওয়া
- DFS এ backtrack এর ধাপ না দেখানো
- BFS কে shortest path ভাবা weighted graph এও — ওখানে Dijkstra লাগবে
- Cycle থাকা graph এ topological sort করার চেষ্টা
- Topological sort এ DFS চলার সময় push করা — finish হলে push
- Dijkstra তে undirected graph কে directed না করা
- Dijkstra তে একবার select করা vertex আবার বদলানো
- Postorder এর প্রথম element কে root ধরা — root শেষে
- Pre + Post দিয়ে unique tree বানিয়ে ফেলা — হয় না (full binary tree ছাড়া)
- Construction এ subtree এর element গুনতে ভুল করা
- BST তে শুধু সরাসরি parent এর সাথে তুলনা করা — পুরো পথ হাঁটতে হবে
- BST delete এ successor এর বদলে যেকোনো child উপরে তোলা
- Successor উপরে তুলে নিচের পুরোনো copy না মোছা
- Heap delete এ শেষ element এর বদলে বড় child কে root এ বসানো
- Heapify down এ একটা swap করেই থেমে যাওয়া
- Heap delete এর পর size কমাতে ভুলে যাওয়া
- Build heap এর complexity O(n log n) লেখা — উত্তর O(n)
১২. পরীক্ষার হলে কৌশল
১ — সহজগুলো আগে
পুরো প্রশ্ন একবার পড়ে যেগুলো নিশ্চিত জানো সেগুলো আগে শেষ করো। Heap আর BST insert
সাধারণত সবচেয়ে দ্রুত হয়ে যায়।
২ — ধাপ দেখাও, শুধু উত্তর নয়
Trace table, Queue/Stack এর অবস্থা, প্রতিটা swap এর পরের array — নম্বর এখানেই।
উত্তর ভুল হলেও ধাপ ঠিক থাকলে আংশিক নম্বর পাবে।
৩ — অনুমান লিখে দাও
"1-based indexing ব্যবহার করা হলো", "inorder successor ব্যবহার করা হলো",
"height edge গুনে", "প্রতিবেশী alphabetical ক্রমে" — এই এক লাইনগুলো ভুল বোঝাবুঝি ঠেকায়।
৪ — বিনামূল্যের যাচাই ব্যবহার করো
BST → inorder sorted কিনা · Graph → Σ degree = 2E কিনা · Heap → প্রতিটা parent ≥ child কিনা ·
Tree construction → আঁকা গাছ থেকে inorder মেলে কিনা। প্রতিটাই ৩০ সেকেন্ডের কাজ।
৫ — পরিষ্কার আঁকো
গাছ/graph বড় করে আঁকো, node এ index লিখে দাও। ছোট করে আঁকলে নিজেরই ভুল হয়।
৬ — Code লাগবে না
স্যার নিশ্চিত করেছেন — পরীক্ষায় code আসবে না। হাতে সমাধান আর ধাপ দেখানোই যথেষ্ট।
Bellman-Ford ও সিলেবাসে নেই।
সব প্রস্তুতি শেষ — এখন শুধু ধাপ দেখিয়ে লেখো ✓
সন্দেহ হলে সংশ্লিষ্ট টপিকের পাতায় ফিরে যাও — উপরের নেভিগেশন থেকে