Loading...
Different Ministry

Post: Assistant Programmer (CSE)
Exam Date: 19.07.2023, Exam Taker: BPSC
1(a) The complexity of merge sort is T(n) = 2T (n/2)+n. Explain how the above equation is derived? 5
Time Complexity of Merge Sort
The recurrence relation for merge sort is:
T(n) = 2T(n/2) + n
Explanation:
1. Divide Step: The array of size n is divided into two halves. Sorting each half takes T(n/2) time, so for two halves it is 2T(n/2).
2. Combine Step (Merging): Merging the two sorted halves takes linear time, proportional to n.
3. Full Recurrence: Combining the steps gives T(n) = k + 2T(n/2) + k₂n, where k and k₂ are constants. For large n, k can be ignored, giving T(n) = 2T(n/2) + k₂n. Simplifying constants gives the final form: T(n) = 2T(n/2) + kn.

Merge Sort-এর Time Complexity
Merge sort-এর recurrence relation হলো:
T(n) = 2T(n/2) + n
ব্যাখ্যা:
১. Divide Step: n সাইজের array দুই ভাগে ভাগ করা হয়। প্রতিটি ভাগ sort করতে T(n/2) সময় লাগে, দুই ভাগের জন্য এটি হয় 2T(n/2)।
২. Combine Step (Merging): দুই sorted অংশ merge করতে linear সময় লাগে, যা n-এর অনুপাতে।
৩. পূর্ণ Recurrence: এই ধাপগুলো মিলিয়ে equation হয় T(n) = k + 2T(n/2) + k₂n, যেখানে k ও k₂ constant। বড় n-এর জন্য k-কে উপেক্ষা করা যায়, ফলে T(n) = 2T(n/2) + k₂n হয়। Constants simplify করলে final form পাওয়া যায়: T(n) = 2T(n/2) + kn।
1. (b) What are the tasks of linker and loader? Describe briefly using examples. 5

Linker
A linker combines multiple object files into a single executable file.
It resolves references between files, like function calls or variable usage.
Example: If main.o calls functions in math.o, the linker connects them into one program.
Loader
A loader loads the executable file into memory and prepares it for execution.
It assigns memory addresses and sets up the program to run.
Example: Loading a compiled program like a calculator app into RAM for execution.

Linker
Linker বিভিন্ন object file একত্রিত করে একটি single executable file তৈরি করে।
এটি file-গুলোর মধ্যে function call বা variable reference resolve করে।
উদাহরণ: main.o যদি math.o-এর function কল করে, linker তাদের একসাথে একটি program-এ যুক্ত করে।
Loader
Loader executable file memory-তে load করে এবং run করার জন্য প্রস্তুত করে।
এটি memory address assign করে এবং program execute করার setup করে।
উদাহরণ: একটি compiled program যেমন calculator app RAM-এ load করা এবং চালানো।
2. (a) List down the layers of OSI model in top-down manner. 4

7

Application Layer

Human-computer interaction layer, where applications can access the network services.

6

Presentation Layer

Ensures that data is in a usable format and is where data encryption occurs.

5

Session Layer

Maintains connections and is responsible for controlling ports and sessions.

4

Transport Layer

Transmits data using transmission protocols including TCP and UDP.

3

Network Layer

Decides which physical path the data will take.

2

Data Link Layer

Defines the format of data on the network.

1

Physical Layer

Transmits raw bit stream over the physical medium.

2. (b) Find out the default mask, network address and broadcast address of the class full IPv4 address: 172.16.99.45. 6

Given Information

  • IP Address: 172.16.99.45
  • Class of IP Address: Class B (first octet 172 falls in range 128–191)

1. Default Subnet Mask for Class B

For Class B addresses, the default subnet mask is 255.255.0.0 (or /16 in CIDR notation). This means:

  • First 16 bits represent the network portion.
  • Last 16 bits represent the host portion.
Default Mask (Binary): 11111111.11111111.00000000.00000000 (255.255.0.0)

2. Calculating the Network Address

To find the network address, perform a bitwise AND operation between the IP address and the subnet mask.

IP Address (Binary):    10101100.00010000.01100011.00101101 (172.16.99.45)
Subnet Mask (Binary):   11111111.11111111.00000000.00000000 (255.255.0.0)
AND Operation Result:   10101100.00010000.00000000.00000000 (172.16.0.0)

Network Address: 172.16.0.0

3. Calculating the Broadcast Address

To find the broadcast address, set all host bits to 1 within the network portion of the IP address.

Broadcast Address (Binary): 10101100.00010000.11111111.11111111 (172.16.255.255)

Broadcast Address: 172.16.255.255

Final Answer

  • Default Subnet Mask: 255.255.0.0 (or /16 in CIDR notation)
  • Network Address: 172.16.0.0
  • Broadcast Address: 172.16.255.255
3. (a) How do you define packet fragmentation? Explain briefly the transparent and non-transparent fragmentation with necessary diagram. 6

Packet Fragmentation
Packet fragmentation is the process of breaking an IP packet into smaller fragments when its size exceeds the Maximum Transmission Unit (MTU) of the network. Each fragment has an IP header to allow correct reassembly at the destination.

Transparent Fragmentation
In Transparent Fragmentation, a large packet arriving at a gateway (e.g., G1) is split into smaller fragments to match the network MTU. Fragments are sent to the exit gateway (e.g., G2), which reassembles them into the original packet. The next networks are unaware of the fragmentation. This method is often used in ATM networks.

Non-Transparent Fragmentation
In Non-Transparent Fragmentation, each fragment is treated as an independent packet and is sent to the destination host. The exit gateway does not reassemble the fragments. The destination host reassembles the fragments, allowing multiple exit gateways and improving network performance.

Packet Fragmentation
Packet fragmentation হলো এমন একটি প্রক্রিয়া যেখানে একটি IP packet-এর size network-এর Maximum Transmission Unit (MTU)-এর চেয়ে বড় হলে সেটিকে ছোট ছোট fragment-এ ভাগ করা হয়। প্রতিটি fragment-এ একটি IP header থাকে যাতে destination-এ সঠিকভাবে reassemble করা যায়।

Transparent Fragmentation
Transparent Fragmentation-এ একটি বড় packet যখন gateway-এ (যেমন G1) আসে, এটি network MTU অনুযায়ী ছোট fragment-এ ভাগ করা হয়। Fragment-গুলো exit gateway (যেমন G2) এর কাছে পাঠানো হয়, যা এগুলোকে মূল packet-এ reassemble করে। পরবর্তী network-গুলো fragmentation-এর তথ্য জানে না। এটি প্রায়শই ATM network-এ ব্যবহৃত হয়।

Non-Transparent Fragmentation
Non-Transparent Fragmentation-এ প্রতিটি fragment আলাদা packet হিসেবে ধরা হয় এবং destination host-এ পাঠানো হয়। Exit gateway fragment-গুলো reassemble করে না। Destination host-ই fragment-গুলোকে মূল packet-এ reassemble করে। এটি multiple exit gateway ব্যবহার সম্ভব করে এবং network performance উন্নত করে।

3. (b) Describe briefly the TCP/IP tunneling using appropriate diagram. 4

Tunneling
Tunneling is a method to connect two similar networks over a different type of network.
It wraps the original packet inside another packet, allowing data to pass through incompatible networks safely.
Diagram:
tunneling
Process:
1. Packet Construction: Host A creates an IP packet for Host B.
2. Encapsulation in Ethernet Frame: Host A places the IP packet inside an Ethernet frame addressed to router M1.
3. Transition via WAN: M1 extracts the IP packet, encapsulates it in a WAN packet, and sends it to M2.
4. Final Delivery: M2 decapsulates the IP packet, re-encapsulates it in an Ethernet frame, and delivers it to Host B.

Tunneling
Tunneling হলো দুটি সমজাতীয় network কে একটি ভিন্ন ধরনের network-এর মাধ্যমে সংযুক্ত করার পদ্ধতি।
এটি মূল packet-কে অন্য একটি packet-এর মধ্যে wrap করে, যাতে incompatible network-এর মাধ্যমে data নিরাপদে পাঠানো যায়।
চিত্র:
tunneling
প্রক্রিয়া:
১. Packet Construction: Host A Host B-এর জন্য একটি IP packet তৈরি করে।
২. Ethernet Frame-এ Encapsulation: Host A IP packet-টিকে Ethernet frame-এর মধ্যে রাখে এবং router M1-এর address দেয়।
৩. WAN-এ Transition: M1 IP packet বের করে, WAN packet-এর মধ্যে encapsulate করে M2-তে পাঠায়।
৪. চূড়ান্ত ডেলিভারি: M2 IP packet decapsulate করে, Ethernet frame-এ re-encapsulate করে Host B-তে পৌঁছে দেয়।

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

Latest Post
Field Based Job Question & Solution
Bank IT Job Solution

MCQ + Written from Bangladesh Bank, Sonali, Combined Bank IT recruitment.

BPSC IT Job Solution

BPSC Computer/IT cadre & non-cadre post Question papers with full solutions.

Gas Field IT Job Solution

Gas field like TGTDCL, BGDCL, JGTDSL, KGDCL, SGCL, RPGCL, GTCL etc. question solution

Power Sector IT Job Solution

Power sector such as NESCO, DESCO, DPDC, WZPDCL, BPDB, PGCB, BREB etc

Other IT Job Solution

Other Govt. Semi govt. organization like BCC, BTCL, CAAB, NSI etc.

NTRCA IT Job Solution (upcoming)

NTRCA ICT-related posts such as Assistant Teacher, Demonstrator, Lecturer.

IT MCQ Job Solution

Collected MCQ Job solution of BANK, BPSC, POWER SECTOR, GAS Field and Others.

Topic Based Q&S
WhatsApp Telegram Messenger