Different Ministry
Post: Assistant Programmer (CSE)
Exam Date: 19.07.2023, Exam Taker: BPSC
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-এর 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।
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 বিভিন্ন 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 করা এবং চালানো।
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. |
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
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 উন্নত করে।
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:

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 হলো দুটি সমজাতীয় network কে একটি ভিন্ন ধরনের network-এর মাধ্যমে সংযুক্ত করার পদ্ধতি।
এটি মূল packet-কে অন্য একটি packet-এর মধ্যে wrap করে, যাতে incompatible network-এর মাধ্যমে data নিরাপদে পাঠানো যায়।
চিত্র:

প্রক্রিয়া:
১. 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-তে পৌঁছে দেয়।
