Combined Bank, Senior Officer (IT), 2025ok

Combined Bank

Post: Senior Officer (IT),
Exam Date: 17.10.2025

1. Determine whether the following pair of graphs are isomorphic, and justify your answer in one sentence.

(10 Marks)

Isomorphic Pairs:
• Graph 1 and Graph 2 are isomorphic because they have the same number of vertices, same number of edges, and identical degree sequence with preserved adjacency structure.
• Graph 3 and Graph 4 are also isomorphic since their vertex connections follow the same pattern, even though their drawings look different.

Graph-1:
Vertices = 6
(u1, u2, u3, u4, u5, u6)
Degree sequence = (3, 3, 3, 3, 3, 3)

Graph-2:
Vertices = 6
(v1, v2, v3, v4, v5, v6)
Degree sequence = (3, 3, 3, 3, 3, 3)

Conclusion for Graph-1 & Graph-2:
Both graphs have the same number of vertices (6) and the same degree sequence, so they are isomorphic.

Graph-3:
Vertices = 6
(u1, u2, u3, u4, u5, u6)
Degree sequence = (3, 3, 2, 2, 3, 3)

Graph-4:
Vertices = 6
(v1, v2, v3, v4, v5, v6)
Degree sequence = (2, 3, 3, 2, 2, 3)

Conclusion for Graph-3 & Graph-4:
have not the identical degree sequences, so they are not isomorphic.

Isomorphic পেয়ার:
• Graph 1 এবং Graph 2 পরস্পর isomorphic, কারণ এদের vertex সংখ্যা, edge সংখ্যা এবং degree sequence একই এবং adjacency ঠিকভাবে সংরক্ষিত।
• Graph 3 এবং Graph 4 ও isomorphic, কারণ দুটির connection pattern এক হলেও আঁকার ধরন আলাদা।

Graph-1:
Vertex সংখ্যা = ৬টি
(u1, u2, u3, u4, u5, u6)
Degree sequence = (3, 3, 3, 3, 3, 3)

Graph-2:
Vertex সংখ্যা = ৬টি
(v1, v2, v3, v4, v5, v6)
Degree sequence = (3, 3, 3, 3, 3, 3)

Graph-1 ও Graph-2 এর সিদ্ধান্ত:
উভয় graph-এ vertex সংখ্যা সমান (৬) এবং degree sequence একই, তাই এরা isomorphic।

Graph-3:
Vertex সংখ্যা = ৬টি
(u1, u2, u3, u4, u5, u6)
Degree sequence = (3, 3, 2, 2, 3, 3)

Graph-4:
Vertex সংখ্যা = ৬টি
(v1, v2, v3, v4, v5, v6)
Degree sequence =(2, 3, 3, 2, 2, 3)

Graph-3 ও Graph-4 এর vertex সংখ্যা সমান (৬) ,degree sequence একই নয়, তাই এরা isomorphic নয়।

2. Explain the Quick Sort algorithm with a suitable example. Under what conditions does Quick Sort exhibit its worst-case time complexity, and why does this situation occur?(10 Marks)

Quick Sort Algorithm Quick Sort is a divide-and-conquer sorting algorithm. It works by selecting a pivot element, partitioning the array into two parts (elements smaller than pivot and elements greater than pivot), and then recursively sorting the sub-arrays. It is fast and widely used in practice.

Steps of Quick Sort Choose a pivot → Partition the array → Recursively apply Quick Sort on left and right sub-arrays.

Worst-Case Time Complexity The worst-case time complexity of Quick Sort is O(n²).

When does Worst Case Occur? Worst case occurs when the pivot element is always the smallest or largest element in the array.
Examples: already sorted array, reverse sorted array (when first or last element is chosen as pivot).

Why does this happen? In this case, partitioning creates highly unbalanced sub-arrays (one with n−1 elements and the other with 0). This leads to maximum number of recursive calls, resulting in O(n²) time complexity.

Quick Sort Algorithm Quick Sort হলো একটি divide-and-conquer based sorting algorithm। এখানে একটি pivot element নেওয়া হয়, তারপর array কে pivot এর চেয়ে ছোট এবং বড় দুই ভাগে ভাগ করা হয় এবং এই sub-array গুলোকে recursively sort করা হয়। এটি দ্রুত এবং বাস্তবে খুব বেশি ব্যবহৃত হয়।

Quick Sort এর ধাপসমূহ Pivot নির্বাচন → Array partition → Left ও right sub-array এ recursive sorting।
Worst-Case Time Complexity Quick Sort এর worst-case time complexity হলো O(n²)।

Worst Case কখন ঘটে? Worst case ঘটে যখন pivot সবসময় array এর সবচেয়ে ছোট বা সবচেয়ে বড় element হয়।
উদাহরণ: already sorted বা reverse sorted array (যখন first বা last element pivot নেওয়া হয়)।

কেন এমন হয়? এই অবস্থায় partition ঠিকভাবে balanced হয় না। একদিকে n−1 element আর অন্যদিকে 0 element থাকে। ফলে recursive call এর সংখ্যা বেড়ে যায় এবং time complexity O(n²) হয়ে যায়।

3. Consider a logical address space of 512 pages, each of 2-KB page size, mapped onto a physical memory containing 128 frames.
a. How many bits are required in the logical address?
b. How many bits are required in the physical address? (10 Marks)

Given
Logical address space = 512 pages
Page size = 2 KB = 2048 bytes
Physical memory = 128 frames

a) Bits required in the Logical Address
Number of pages = 512 = 2⁹ → Page number bits = 9 bits
Page size = 2048 bytes = 2¹¹ → Offset bits = 11 bits
So, Logical address bits = Page number bits + Offset bits = 9 + 11 = 20 bits

b) Bits required in the Physical Address
Number of frames = 128 = 2⁷ → Frame number bits = 7 bits
Offset remains same = 11 bits
So, Physical address bits = Frame number bits + Offset bits = 7 + 11 = 18 bits

প্রদত্ত তথ্য
Logical address space = 512 pages
Page size = 2 KB = 2048 bytes
Physical memory = 128 frames

a) Logical Address এর জন্য কত bit লাগবে
Page সংখ্যা = 512 = 2⁹ → Page number এর জন্য লাগবে 9 bit
Page size = 2048 bytes = 2¹¹ → Offset এর জন্য লাগবে 11 bit
সুতরাং Logical address bits = 9 + 11 = 20 bit

b) Physical Address এর জন্য কত bit লাগবে
Frame সংখ্যা = 128 = 2⁷ → Frame number এর জন্য লাগবে 7 bit
Offset একই থাকবে = 11 bit
সুতরাং Physical address bits = 7 + 11 = 18 bit

4. Why does the Domain Name System (DNS) primarily use UDP as its transport layer protocol instead of TCP? Describe the sequence of events that take place during the DNS name resolution process when a user enters www.companybd.com into a web browser and presses Enter.(10 Marks)

Why DNS primarily uses UDP instead of TCP
DNS mainly uses UDP because it is fast and lightweight. UDP does not require connection establishment, which reduces delay and overhead. Most DNS queries and responses are small in size and can easily fit within a single UDP packet. Using UDP allows DNS to provide quick responses, which is important for fast web browsing. TCP is only used in special cases, such as zone transfers or when the response size is too large.

DNS Name Resolution Process for www.companybd.com
1) The user enters www.companybd.com in the web browser and presses Enter.
2) The browser first checks its local DNS cache to see if the IP address is already available.
3) If not found, the request is sent to the local DNS resolver (usually provided by the ISP).
4) The resolver contacts the Root DNS Server, which directs it to the .com Top-Level Domain (TLD) server.
5) The TLD server provides the address of the authoritative DNS server for companybd.com.
6) The authoritative DNS server returns the IP address of www.companybd.com.
7) The resolver sends the IP address back to the browser and stores it in cache for future use.
8) Using the obtained IP address, the browser connects to the web server and loads the website.

DNS কেন প্রধানত TCP এর পরিবর্তে UDP ব্যবহার করে
DNS মূলত UDP ব্যবহার করে কারণ এটি দ্রুত এবং কম overhead তৈরি করে। UDP তে connection establish করার দরকার হয় না, ফলে delay কম হয়। বেশিরভাগ DNS query এবং response ছোট আকারের হয়, যা একটি UDP packet এই পাঠানো যায়। দ্রুত response পাওয়ার জন্য UDP ব্যবহার করা হয়। বিশেষ ক্ষেত্রে যেমন zone transfer বা বড় response হলে TCP ব্যবহার করা হয়।

www.companybd.com এর ক্ষেত্রে DNS Name Resolution Process
1) User browser এ www.companybd.com লিখে Enter চাপ দেয়।
2) প্রথমে browser নিজের DNS cache এ IP address খোঁজে।
3) না পেলে request local DNS resolver (সাধারণত ISP) এর কাছে পাঠানো হয়।
4) Resolver Root DNS Server এর সাথে যোগাযোগ করে, যা তাকে .com Top-Level Domain (TLD) server এর ঠিকানা দেয়।
5) TLD server companybd.com এর authoritative DNS server এর ঠিকানা দেয়।
6) Authoritative DNS server www.companybd.com এর IP address পাঠিয়ে দেয়।
7) Resolver সেই IP address browser এ পাঠায় এবং ভবিষ্যতের জন্য cache এ সংরক্ষণ করে।
8) প্রাপ্ত IP address ব্যবহার করে browser web server এর সাথে সংযোগ করে এবং website load করে।

5. Explain the concept of thrashing in an operating system, describing how it occurs in a demand-paged virtual memory system and how it impacts CPU utilization and overall system performance. (10 Marks)

Thrashing in Operating System
Thrashing is a condition in an operating system where the system spends most of its time swapping pages in and out of memory instead of executing actual processes. It mainly occurs in a demand-paged virtual memory system when there are not enough frames to support the working sets of active processes.

How Thrashing Occurs in Demand Paging
In demand paging, pages are loaded into memory only when they are needed. If too many processes are running and physical memory is insufficient, frequent page faults occur. The OS continuously replaces pages, but the required pages are again needed immediately, causing excessive paging activity. This situation leads to thrashing.

Impact on CPU Utilization
During thrashing, CPU utilization becomes very low because the CPU waits for disk I/O operations caused by page faults. Even though many processes are active, the CPU remains mostly idle.

Impact on System Performance
Overall system performance degrades severely. Response time increases, throughput decreases, and the system becomes slow and inefficient. To handle thrashing, the OS may reduce the degree of multiprogramming or use working set and page fault frequency control techniques.

Operating System এ Thrashing
Thrashing হলো একটি অবস্থা যেখানে operating system অধিকাংশ সময় memory থেকে page আনা-নেওয়ায় ব্যয় করে, process execute করার পরিবর্তে। এটি মূলত demand-paged virtual memory system এ ঘটে, যখন active process গুলোর জন্য যথেষ্ট frame থাকে না।

Demand Paging এ Thrashing কীভাবে ঘটে
Demand paging এ page তখনই memory তে আনা হয় যখন সেটি দরকার হয়। যদি একসাথে অনেক process চালানো হয় এবং physical memory কম থাকে, তাহলে বারবার page fault ঘটে। OS এক page remove করে আরেকটা আনে, কিন্তু আগের page আবার দরকার পড়ে। এতে অতিরিক্ত paging শুরু হয়, যা thrashing সৃষ্টি করে।

CPU Utilization এর উপর প্রভাব
Thrashing এর সময় CPU utilization খুব কমে যায়, কারণ CPU বারবার disk I/O এর জন্য অপেক্ষা করে। অনেক process থাকা সত্ত্বেও CPU প্রায় idle থাকে।

System Performance এর উপর প্রভাব
System performance অনেক খারাপ হয়ে যায়। Response time বেড়ে যায়, throughput কমে যায় এবং system ধীরগতির হয়ে পড়ে। Thrashing কমাতে OS degree of multiprogramming কমাতে পারে অথবা working set ও page fault frequency technique ব্যবহার করতে পারে।

6. Write a structured program (in C or Python) that takes an integer input n and prints the sum of all even numbers from 1 to n.

#include <stdio.h>
/* Function to calculate sum of even numbers from 1 to n */
int sumOfEven(int n) {
    int sum = 0;
    for (int i = 2; i <= n; i += 2) {
        sum += i;
    }
    return sum;
}
int main() {
    int n, result;
    printf("Enter an integer: ");
    scanf("%d", &n);
    result = sumOfEven(n);
    printf("Sum of even numbers from 1 to %d = %d\n", n, result);
    return 0;
}

    
Sample I/O:
  Enter an integer: 50
Sum of even numbers from 1 to 50 = 650


=== Code Execution Successful ===

🔗 Run Online: Sum of even number.

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.

Leave a Comment Cancel Reply

You must be logged in to post a comment.

Field Based Job Solution Topic Based QnS IT Job News / Circular

Combined Bank Post: Senior Officer (IT), Exam Date: 17.10.2025

Leave a Comment Cancel Reply

Combined Bank

Post: Senior Officer (IT),
Exam Date: 17.10.2025