Design and Analysis of Algorithm

BPSC Syllabus (Algorithm)

Algorithm and complexity: Asymptotic notations, Basic algorithm techniques and analysis, Divide and conquer, Dynamic programming, greedy method, branch and bound, string matching, computational geometric problems, graph algorithms, spanning. trees, shortest paths, max-flow problem, searching algorithms. Techniques for analysis of algorithms, approximation algorithms, parallel algorithms..

You must subscribe & Login to view more.

Don’t have an account? Register

Or your subscription is under review by admin. Please message on WhatsApp / Telegram.

Loading...
Explain the logic of "Bubble Sort". Why is it considered inefficient for large datasets compared to Merge Sort? CB, AP, 26

Logic of Bubble Sort
Bubble Sort is a simple comparison-based sorting algorithm. It works by repeatedly comparing adjacent elements and swapping them if they are in the wrong order. After each pass, the largest unsorted element “bubbles up” to its correct position at the end of the array.

Steps
1) Compare the first two elements.
2) Swap them if the first is greater than the second.
3) Move to the next pair and repeat until the end of the array.
4) Repeat the entire process for the remaining unsorted portion until the array is sorted.

Time Complexity
Worst and average case: O(n²)

Why Bubble Sort is Inefficient for Large Datasets
Bubble Sort makes a large number of comparisons and swaps even when the array is nearly sorted. As the input size grows, the number of operations increases quadratically, making it very slow for large datasets.

Why Merge Sort is Better
Merge Sort uses the divide and conquer approach. It divides the array into smaller parts, sorts them, and then merges them efficiently. Its time complexity is O(n log n), which is much faster than Bubble Sort for large datasets.

Bubble Sort এর Logic
Bubble Sort হলো একটি সহজ sorting algorithm যেখানে বারবার পাশাপাশি থাকা element গুলো compare করা হয় এবং ভুল order এ থাকলে swap করা হয়। প্রতিটি pass শেষে সবচেয়ে বড় element টি তার সঠিক জায়গায় চলে যায়, ঠিক যেন bubble উপরে উঠে আসে।

Steps
1) প্রথম দুইটি element compare করা হয়।
2) ভুল order হলে swap করা হয়।
3) পরবর্তী pair এ গিয়ে একই কাজ করা হয়।
4) পুরো array sorted না হওয়া পর্যন্ত process টি repeat করা হয়।

Time Complexity
Worst এবং average case: O(n²)

বড় Dataset এ কেন Bubble Sort অকার্যকর
Bubble Sort অনেক বেশি comparison ও swap করে, এমনকি array প্রায় sorted হলেও। Dataset বড় হলে operation সংখ্যা খুব দ্রুত বেড়ে যায়, তাই এটি ধীরগতির হয়ে যায়।

Merge Sort কেন ভালো
Merge Sort divide and conquer পদ্ধতি ব্যবহার করে। এটি array কে ছোট অংশে ভাগ করে sort করে তারপর merge করে। এর time complexity O(n log n), যা বড় dataset এর জন্য Bubble Sort এর চেয়ে অনেক বেশি কার্যকর।

Describe step-by-step how Binary Search locates a target value in a sorted array. Why does it fail if the array is unsorted? CB, AP, 26

How Binary Search Works (Step-by-Step)
Binary Search is a searching technique used to find a target value in a sorted array by repeatedly dividing the search range into half.

Steps
1) Set two pointers: low = first index, high = last index.
2) Find the middle index: mid = (low + high) / 2.
3) Compare the target with array[mid]:
• If target == array[mid] → target found.
• If target < array[mid] → search left half (high = mid − 1).
• If target > array[mid] → search right half (low = mid + 1).
4) Repeat steps 2–3 until the target is found or low > high (target not present).

Example
Array: [10, 20, 30, 40, 50], Target = 40
low=0, high=4 → mid=2 → array[2]=30 (40>30) → search right
low=3, high=4 → mid=3 → array[3]=40 → found

Why it fails if the array is unsorted
Binary Search depends on the sorted order to decide whether to go left or right. If the array is unsorted, the comparisons (target < or > mid value) do not correctly indicate which half contains the target, so the algorithm may skip the target and give wrong results.

Binary Search কীভাবে কাজ করে (Step-by-Step)
Binary Search হলো একটি searching technique যা sorted array তে target value খুঁজতে search range কে বারবার half করে।

Steps
1) দুইটি pointer সেট করি: low = প্রথম index, high = শেষ index।
2) middle index বের করি: mid = (low + high) / 2।
3) target এর সাথে array[mid] compare করি:
• যদি target == array[mid] → target পাওয়া গেছে।
• যদি target < array[mid] → left half এ যাব (high = mid − 1)।
• যদি target > array[mid] → right half এ যাব (low = mid + 1)।
4) target না পাওয়া পর্যন্ত অথবা low > high হওয়া পর্যন্ত step গুলো repeat করি।

Example
Array: [10, 20, 30, 40, 50], Target = 40
low=0, high=4 → mid=2 → array[2]=30 (40>30) → right half এ search
low=3, high=4 → mid=3 → array[3]=40 → found

Array unsorted হলে কেন fail করে
Binary Search এর মূল শর্ত হলো array টি sorted হতে হবে, কারণ mid এর value দেখে সিদ্ধান্ত নেওয়া হয় target left এ নাকি right এ। Array unsorted হলে এই সিদ্ধান্ত ভুল হয়, ফলে target থাকা সত্ত্বেও algorithm সেটিকে skip করে ভুল result দিতে পারে।

Write Merge short function. CB 3 Bank, AE(it), 21

Merge Sort Algorithm

Merge Sort is a divide and conquer algorithm. It recursively splits an array into two halves, sorts each half, and then merges the sorted halves back together.

Merge Sort Function

void MergeSort(int A[], int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;  // Find the middle index
        MergeSort(A, p, q);    // Recursively sort the left half
        MergeSort(A, q + 1, r); // Recursively sort the right half
        merge(A, p, q, r);      // Merge the sorted halves
    }
}

Merge Function

void merge(int A[], int p, int q, int r) {
    int n1 = q - p + 1;
    int n2 = r - q;
    int L[n1], R[n2];

    // Copy data into temporary arrays
    for (int i = 0; i < n1; i++) L[i] = A[p + i];
    for (int j = 0; j < n2; j++) R[j] = A[q + 1 + j];

    int i = 0, j = 0, k = p;
    // Merge the two subarrays
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) A[k++] = L[i++];
        else A[k++] = R[j++];
    }

    // Copy remaining elements of L[]
    while (i < n1) A[k++] = L[i++];
    // Copy remaining elements of R[]
    while (j < n2) A[k++] = R[j++];
}
Shortest Path Algorithm.Janata Bank, ASA, 21
Dijkstra(G, s)
for each vertex v in G
    dist[v] = infinity
    visited[v] = false

dist[s] = 0

for i = 1 to number of vertices
    u = vertex with minimum dist[u] among unvisited vertices
    visited[u] = true

    for each neighbor v of u
        if visited[v] == false and dist[u] + w(u,v) < dist[v]
            dist[v] = dist[u] + w(u,v)

return dist
Finding Shortest Spanning tree using Kruskal's Algorithm from the following graph
Sonali Bank, O(it), 21

You are given a sorted array of integers. Write an algorithm using Binary Search to search for a given key element in the array. If the element is found, return its index; otherwise, return -1.ICB Assest Management, AP, 24

Binary Search Algorithm

Binary Search is used to find a key element in a sorted array by repeatedly dividing the search interval into two halves.

Pseudocode:

BINARY_SEARCH(A, n, key)
1. low ← 0
2. high ← n - 1
3. while low ≤ high do
4.     mid ← (low + high) / 2
5.     if A[mid] = key then
6.         return mid
7.     else if A[mid] < key then
8.         low ← mid + 1
9.     else
10.        high ← mid - 1
11. return -1

Explanation:

  • If the key equals the middle element, return its index.
  • If the key is greater, search the right half.
  • If the key is smaller, search the left half.
  • If not found, return -1.

Time Complexity: O(log n)
Space Complexity: O(1)

Binary Search অ্যালগরিদম

Binary Search একটি sorted array-এ কোনো key খুঁজতে ব্যবহৃত হয়। এটি বারবার array-কে দুই ভাগে বিভক্ত করে অনুসন্ধান করে।

Pseudocode:

BINARY_SEARCH(A, n, key)
1. low ← 0
2. high ← n - 1
3. while low ≤ high do
4.     mid ← (low + high) / 2
5.     if A[mid] = key then
6.         return mid
7.     else if A[mid] < key then
8.         low ← mid + 1
9.     else
10.        high ← mid - 1
11. return -1

ব্যাখ্যা:

  • key যদি মধ্যম উপাদানের সমান হয়, index ফেরত দেয়।
  • key বড় হলে ডান অংশে খোঁজে।
  • key ছোট হলে বাম অংশে খোঁজে।
  • না পেলে -1 ফেরত দেয়।

Time Complexity: O(log n)
Space Complexity: O(1)

What is the worst-case time and space complexity of quicksort algorithm. Explain how this worst case behavior can occur?CBt, o(it), 24

Worst-Case Time and Space Complexity of Quicksort

  • Time Complexity (Worst Case): O(n2)
  • Space Complexity (Worst Case): O(n) due to recursive calls

How Worst-Case Behavior Occurs
Quicksort works by selecting a pivot element and partitioning the array into two subarrays. In the worst case:

  • The pivot is always the smallest or largest element.
  • This happens when the array is already sorted (ascending or descending) and the first or last element is chosen as pivot.
  • As a result, one subarray has n−1 elements and the other has 0 elements, leading to maximum recursive calls and O(n2) comparisons.

Proper pivot selection (like median-of-three) can help avoid this worst-case behavior.

Quicksort-এর Worst-Case Time এবং Space Complexity

  • Time Complexity (Worst Case): O(n2)
  • Space Complexity (Worst Case): O(n), কারণ recursive calls এর জন্য stack memory লাগে

Worst-Case কিভাবে ঘটে
Quicksort একটি pivot নির্বাচন করে array-কে দুটি subarray-তে ভাগ করে। Worst case ঘটে যখন:

  • Pivot সবসময় সবচেয়ে ছোট বা সবচেয়ে বড় element হয়।
  • উদাহরণস্বরূপ, array আগে থেকেই sorted থাকে (ascending বা descending) এবং প্রথম বা শেষ element pivot হিসেবে নেওয়া হয়।
  • ফলে, একটি subarray-তে থাকে n−1 element এবং অন্যটির size 0, যার কারণে recursive calls সর্বাধিক হয় এবং O(n2) comparisons লাগে।

Pivot-কে median-of-three বা random selection করলে এই worst-case এড়ানো যায়।

Coming Soon
WhatsApp Telegram Messenger