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

লেসন

1. 01Asymptotic Analysis — O, Θ, Ω: growth-এর ভাষাAsymptotic analysis অ্যালগরিদম-তুলনাকে মিলিসেকেন্ড থেকে মুক্ত করে — O, Θ, Ω-র growth-ভাষায় দুইটা correct solution-এর মধ্যে কোনটা scale করবে তার machine-independent উত্তর ওঠে।কঠিন৫০ মিনিটEXPERIMENTBUILD
2. 02Amortized Analysis — মাঝে মাঝে দামি, গড়ে সস্তাAmortized analysis দামি অপারেশনের খরচ সস্তাদের ওপর ছড়িয়ে দেয় — dynamic array-র n append-এর মোট খরচ 3n প্রমাণ করে দেখায় যে প্রতি-append গড়ে constant, যদিও একক append মাঝে মাঝে linear।অ্যাডভান্সড৪৫ মিনিটEXPERIMENTBUILD
3. 03Array ও Dynamic Array — memory layout থেকে performance পর্যন্তArray-র সব শক্তি তার memory layout-এ — contiguous slots-এর address arithmetic O(1) indexing দেয়, spatial locality cache থেকে ফ্রি speedup দেয়, আর একই কারণ ঘুরিয়ে middle insertion-কে O(n) বাধ্য করে।মাঝারি৪০ মিনিটEXPERIMENTBUILD
4. 04Linked List — pointer chasing-এর আসল দামLinked list theory-তে pointer-এর জাদু মনে হয়, কিন্তু প্রতিটা hop একটা dependent memory load — cache miss-এর দাম মেপে দেখা যায় list প্রায় সব traversal-এ array-কে হারে, আর জেতে শুধু যেখানে O(1) splicing আর stable iterator আসলেই দরকার।মাঝারি৪০ মিনিটEXPERIMENTBUILD
5. 05Stack, Queue, Deque — discipline থেকে শক্তিStack, Queue আর Deque নতুন storage না — এরা access-discipline: কোন প্রান্তে ঢোকা-বেরোনা ঠিক করলেই recursion, scheduling, BFS/DFS আর undo-র পুরো machinery abstract level-এ ওঠে।মাঝারি৩৫ মিনিটEXPERIMENTBUILD
6. 06Hash Table — O(1)-এর জাদু আর তার দামHash table array-র O(1) indexing-কে key-তে সাধারণীকরণ করে — কিন্তু pigeonhole বলে collision থামানো যায় না, তাই আসল engineering হলো collision-কে সস্তা করা: chaining, probing, load factor, resize, আর adversarial keys-এর বিরুদ্ধে randomization।অ্যাডভান্সড১ ঘণ্টাEXPERIMENTBUILD
7. 07Binary Tree — hierarchy-র সবচেয়ে সরল রূপBinary tree হলো hierarchy-র সবচেয়ে সরল রূপ — প্রতিটা node-এর হাতে মাত্র দুইটা pointer, আর traversal মানে সেই tree-এর প্রতিটা node-কে ঠিক একবার করে ঘুরে দেখা, চারটা ভিন্ন নিয়মে।মাঝারি৪৫ মিনিটEXPERIMENTBUILD
8. 08BST, AVL, Red-Black — unbalanced হলে কী হয়BST-র log₂ n গ্যারান্টি শুধু balance থাকলেই সত্য — sorted input তা ভেঙে linked list বানায়, আর rotation নামের O(1) pointer-অস্ত্র AVL ও red-black tree-কে সেই পতন ঠেকাতে দেয়।অ্যাডভান্সড১ ঘণ্টা ৫ মিনিটEXPERIMENTBUILD
9. 09B-Tree ও B+ Tree — disk-এর জন্য জন্ম নেওয়া treeDisk byte না, পুরো page পড়ে — তাই B-tree node page-সমান চওড়া করে fanout হাজারে তোলে আর height ৩-৪-তে নামায়; B+ variant leaf-link দিয়ে range scan sequential read বানায়।অ্যাডভান্সড৫৫ মিনিটEXPERIMENTBUILD
10. 10Heap ও Priority Queue — array-তে বসানো treeComplete binary tree flat array-তে বসে যায় — একটাও pointer নেই; heap-ই একমাত্র tree যার প্রতি ধাপ cache-friendly, আর priority queue-র ইঞ্জিন সেই heap।কঠিন৫০ মিনিটEXPERIMENTBUILD
11. 11Trie ও Radix Tree — prefix দিয়ে খোঁজাTrie-তে key বসে edge-এ edge-এ — character ধরে নামতে হয়, খোঁজা O(word length), dictionary দশগুণ বড় হলেও; radix compression এক-child শৃঙ্খল গুটিয়ে memory-bill অর্ধেকে নামায়।কঠিন৪৫ মিনিটEXPERIMENTBUILD
12. 12Union-Find — disjoint set-এর inverse Ackermann magicUnion-Find দুই op জানে — same group? merge করো — rank + path compression মিলে খরচ নামায় inverse Ackermann α(n)-এ, বাস্তবের যেকোনো n-এ ৪-এরও কম।অ্যাডভান্সড৫০ মিনিটEXPERIMENTBUILD
13. 13Graph Representation, BFS ও DFS — সব graph algorithm-এর ভিতএকই graph রাখার দুই উপায়ের খরচ আলাদা, ঘোরার দুই মৌলিক কৌশল — BFS queue দিয়ে layer ধরে shortest path, DFS stack দিয়ে cycle ও component — দুটোই O(V+E), কিন্তু representation choice constant আর feasibility দুটোই ঠিক করে।কঠিন১ ঘণ্টাEXPERIMENTBUILD
14. 14Shortest Path — Dijkstra, Bellman-Ford, Floyd-Warshall, A*চারজন shortest-path বিশেষজ্ঞের ভিন্ন অস্ত্র — Dijkstra-র greedy certainty, Bellman-Ford-এর negative-cycle রডার, Floyd-Warshall-এর all-pairs DP, A*-এর goal-directed অনুমান — আর কোন situation-এ কার অস্ত্র, সেটাই আসল সিদ্ধান্ত।অ্যাডভান্সড১ ঘণ্টা ১০ মিনিটEXPERIMENTBUILD
15. 15MST — Kruskal আর Prim: greedy-এর প্রমাণিত জয়Minimum spanning tree হলো সেই বিরল জায়গা যেখানে greedy শুধু কাজ করে না — cut property দিয়ে প্রমাণিতভাবে সেরা; Kruskal edge সাজিয়ে union-find দিয়ে ছাঁটে, Prim heap দিয়ে একটা গাছ বাড়ায়, আর দুজনের যোগফল সবসময় সমান।কঠিন৫০ মিনিটEXPERIMENTBUILD
16. 16Topological Sort ও SCC — dependency-র গণিতDependency-র গোলমাল দুনিয়াকে সোজা লাইনে সাজানোর দুই রাস্তা — Kahn-এর in-degree queue আর DFS finish-time reversal; আর যেখানে গোলকধাঁধা mutually reachable block-এ ভাগ হয়, সেখানে SCC — Kosaraju ও Tarjan-এর হাতে।অ্যাডভান্সড৫৫ মিনিটEXPERIMENTBUILD
17. 17Sorting — quick, merge, heap, radix, timsortSorting-ই সেই জায়গা যেখানে theory আর silicon সবচেয়ে স্পষ্টভাবে মুখোমুখি — Ω(n log n) lower bound, quicksort-এর cache-friendly inner loop, radix-এর বৈধ ফাঁকি, আর timsort-এর adaptive চালাকি; benchmark টেবিল সব উন্মোচন করে।অ্যাডভান্সড১ ঘণ্টা ১০ মিনিটEXPERIMENTBUILD
18. 18Binary Search — ২০ লাইনের কোড, ৯৯% মানুষ ভুল লেখেBinary search ছোট দেখায় কিন্তু boundary-ই খুনি — loop invariant-এর discipline, overflow-র ইতিহাস, lower/upper bound family, rotated array, আর answer-search pattern; fuzzing প্রমাণ করে correctness কেনা যায় শৃঙ্খলা দিয়ে।কঠিন৪৫ মিনিটEXPERIMENTBUILD
19. 19Recursion ও Divide and Conquer — ছোট নিজেকে ডাকাRecursion আসলে induction-এরই কোড-রূপ — কিন্তু প্রতিটা call একটা stack frame-এর দাম দেয়, আর divide-and-conquer-এর recurrence মেপে দেয় সেই দাম কত।কঠিন৫০ মিনিটEXPERIMENTBUILD
20. 20Dynamic Programming — একবার হিসাব, বারবার ব্যবহারDP-র পুরো খেলা দুইটা শর্ত আর একটা শৃঙ্খলায়: একই subproblem বারবার এলে একবারই হিসাব করে জমা রাখো — state-এর অর্থ লিখে, recurrence সাজিয়ে, space চেপে।রিসার্চ-লেভেল১ ঘণ্টা ১০ মিনিটEXPERIMENTBUILD
21. 21Greedy — local সিদ্ধান্তে global জয়, কখন সম্ভবGreedy প্রতিটা ধাপে locally best নেয় — global optimum তখনই নিশ্চিত যখন exchange argument-এ প্রমাণ আছে; Huffman সেই প্রমাণের সবচেয়ে সুন্দর জয়।অ্যাডভান্সড৫৫ মিনিটEXPERIMENTBUILD
22. 22String Algorithms — KMP, Rabin-Karp, suffix structuresString matching-এর পুরো ladder — naive-র backtrack-দুর্ভোগ থেকে KMP-র LPS memory, Rabin-Karp-র hash shortcut, suffix array-র genomics-scale index পর্যন্ত।রিসার্চ-লেভেল১ ঘণ্টা ৫ মিনিটEXPERIMENTBUILD
23. 23Randomized Algorithms — dice নিয়ে correctnessRandomness শুধু speed নয় — adversary-কে অস্ত্রহীন করে: Las Vegas সঠিক উত্তর random সময়ে, Monte Carlo bounded সময়ে probable উত্তর; দুটোই মাপা যায়।অ্যাডভান্সড৫০ মিনিটEXPERIMENTBUILD
24. 24Cache-aware ও Cache-oblivious — Big-O যখন মিথ্যা বলেBig-O একই থেকে গতি ৪-১০× বদলায় — cache line, prefetcher, locality আর layout-এর হিসাব না জানলে RAM model আপনাকে ধোঁকা দেবে।রিসার্চ-লেভেল১ ঘণ্টাEXPERIMENTBUILD

যা যা থাকছে

• Asymptotic analysis — O, Θ, Ω, o, ω
• Amortized analysis
• Arrays, dynamic arrays, memory layout
• Linked lists ও pointer chasing-এর cost
• Stacks, queues, deques
• Hash tables — hashing, collisions, open addressing, chaining
• Trees, binary trees, traversals
• BST, AVL, red-black trees
• B-trees ও B+ trees
• Heaps ও priority queues
• Tries ও radix trees
• Union-Find ও path compression
• Graphs — representation, BFS, DFS
• Shortest path — Dijkstra, Bellman-Ford, Floyd-Warshall, A*
• MST — Kruskal, Prim
• Topological sort, SCC
• Sorting — quick, merge, heap, radix, timsort
• Searching ও binary search variants
• Recursion ও divide and conquer
• Dynamic programming
• Greedy algorithms ও exchange argument
• String algorithms — KMP, Rabin-Karp, suffix structures
• Randomized algorithms
• Cache-aware ও cache-oblivious algorithms

প্রজেক্ট