Dhaka Electric Supply Company PLC
Post: Sub- Assistant Engineer(Computer)
Exam: 15/05/2026
1: NAT, DSSS, RIP, EIGRP, DHCP, IoT এর পূর্ণরূপ লিখ।
  • NAT – Network Address Translation
  • DSSS – Direct Sequence Spread Spectrum
  • RIP – Routing Information Protocol
  • EIGRP – Enhanced Interior Gateway Routing Protocol
  • DHCP – Dynamic Host Configuration Protocol
  • IoT – Internet of Things
3: Bubble Sort কী? এর Best, Average এবং Worst Case Time Complexity লিখ।

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. The algorithm gets its name because smaller elements “bubble” to the top (beginning) of the list with each iteration, just like air bubbles rise to the surface of water.

How Bubble Sort Works

  1. Start from the first element and compare it with the next element.
  2. If the current element is greater than the next element, swap them.
  3. Move to the next pair of adjacent elements and repeat the comparison and swap.
  4. Continue this process until the end of the list.
  5. After the first pass, the largest element will be at the last position.
  6. Repeat the process for the remaining elements (excluding the already sorted elements at the end).
  7. Continue until no more swaps are needed, indicating the list is sorted.

Time Complexity of Bubble Sort

CaseTime ComplexityExplanation
Best CaseO(n)When the array is already sorted. Only one pass is needed to confirm no swaps are required.
Average CaseO(n²)When the array elements are in random order. The algorithm needs to make multiple passes and comparisons.
Worst CaseO(n²)When the array is sorted in reverse order. Maximum number of comparisons and swaps are needed.

Space Complexity: O(1) — Bubble Sort is an in-place sorting algorithm that requires only a constant amount of extra space for swapping.

Bubble Sort হলো একটি simple sorting algorithm যা list-এর মধ্যে বারবার step করে, পাশাপাশি elements compare করে, এবং তারা wrong order-এ থাকলে তাদের swap করে। List-এর মধ্যে pass করা repeat করা হয় যতক্ষণ না list sorted হয়। Algorithm-টি তার নাম পেয়েছে কারণ ছোট elements প্রতিটি iteration-এ list-এর top (শুরুতে) “bubble” হয়, ঠিক যেভাবে বাতাসের bubbles পানির surface-এ উঠে আসে।

Bubble Sort কীভাবে কাজ করে

  1. প্রথম element থেকে শুরু করে পরের element-এর সাথে compare করুন।
  2. যদি current element পরের element থেকে বড় হয়, তাহলে swap করুন।
  3. পরবর্তী adjacent elements-এর pair-এ যান এবং comparison এবং swap repeat করুন।
  4. এই process list-এর শেষ পর্যন্ত continue করুন।
  5. প্রথম pass-এর পর, সবচেয়ে বড় element শেষ position-এ চলে যাবে।
  6. বাকি elements-এর জন্য process repeat করুন (শেষে already sorted elements বাদ দিয়ে)।
  7. যতক্ষণ না আর swap-এর প্রয়োজন নেই ততক্ষণ continue করুন, যা indicate করে list sorted হয়েছে।

Bubble Sort-এর Time Complexity

CaseTime Complexityব্যাখ্যা
Best CaseO(n)যখন array already sorted থাকে। শুধু একটি pass প্রয়োজন swap প্রয়োজন কিনা confirm করতে।
Average CaseO(n²)যখন array elements random order-এ থাকে। Algorithm-কে multiple passes এবং comparisons করতে হয়।
Worst CaseO(n²)যখন array reverse order-এ sorted থাকে। সর্বাধিক comparisons এবং swaps প্রয়োজন।

Space Complexity: O(1) — Bubble Sort একটি in-place sorting algorithm যা swap-এর জন্য শুধু constant amount extra space প্রয়োজন।

4: (iii) DeMorgan's Duality Formula লিখ এবং উদাহরণ দাও।

DeMorgan’s Theorem is a fundamental rule in Boolean Algebra that describes how to convert an AND operation into an OR operation (and vice versa) by using complements. It is very useful for simplifying Boolean expressions and designing digital circuits.
DeMorgan’s Two Laws
Law 1: The complement of a sum (OR) is equal to the product (AND) of the complements.

Formula: (A + B)’ = A’ · B’

Explanation: The NOT of (A OR B) is equal to (NOT A) AND (NOT B).

Law 2: The complement of a product (AND) is equal to the sum (OR) of the complements.

Formula: (A · B)’ = A’ + B’

Explanation: The NOT of (A AND B) is equal to (NOT A) OR (NOT B).

Truth Table Verification for Law 1: (A + B)’ = A’ · B’

ABA + B(A + B)’A’B’A’ · B’
0001111
0110100
1010010
1110000

Truth Table Verification for Law 2: (A · B)’ = A’ + B’

ABA · B(A · B)’A’B’A’ + B’
0001111
0101101
1001011
1110000

Example 1: Simplify (A + B)’ using DeMorgan’s Law

Given: Y = (A + B)’

Using DeMorgan’s First Law:
Y = A’ · B’

Explanation: The NOT of (A OR B) becomes (NOT A) AND (NOT B).

DeMorgan’s Theorem হলো Boolean Algebra-এর একটি মৌলিক নিয়ম যা complements ব্যবহার করে একটি AND operation-কে OR operation-এ (এবং বিপরীতভাবে) রূপান্তর করার পদ্ধতি describe করে। এটি Boolean expressions simplify করতে এবং digital circuits design করতে খুবই useful।

DeMorgan’s দুটি Law

Law 1: একটি sum (OR)-এর complement সমান complements-এর product (AND)।

Formula: (A + B)’ = A’ · B’

ব্যাখ্যা: (A OR B)-এর NOT সমান (NOT A) AND (NOT B)।

Law 2: একটি product (AND)-এর complement সমান complements-এর sum (OR)।

Formula: (A · B)’ = A’ + B’

ব্যাখ্যা: (A AND B)-এর NOT সমান (NOT A) OR (NOT B)।

Law 1-এর জন্য Truth Table Verification: (A + B)’ = A’ · B’

ABA + B(A + B)’A’B’A’ · B’
0001111
0110100
1010010
1110000

Law 2-এর জন্য Truth Table Verification: (A · B)’ = A’ + B’

ABA · B(A · B)’A’B’A’ + B’
0001111
0101101
1001011
1110000

উদাহরণ 1: DeMorgan’s Law ব্যবহার করে (A + B)’ simplify
প্রদত্ত: Y = (A + B)’
DeMorgan’s First Law ব্যবহার করে:
Y = A’ · B’
ব্যাখ্যা: (A OR B)-এর NOT হয়ে যায় (NOT A) AND (NOT B)।

5: DESCO System এ Customer Information, Prepaid Meter Information, Payment Information ও Complaint Records আছে। এদের জন্য একটি Database Schema অঙ্কন কর।

6: সার্কিট সম্পর্কিত একটি সমস্যা সমাধান কর।
7: Rooppur Nuclear Power Plant কোন ধরনের জ্বালানি ব্যবহার করে?
8: Coal Power Plant এর ২টি পরিবেশগত প্রভাব লিখ।
9: Solar Power Plant এর ২টি সুবিধা লিখ।
10: নিচের বাক্যটির Voice Change করঃ

Leave a Comment

WhatsApp Telegram Messenger