Different Ministry
Post: Assistant Maintenance Engineer
Subject: CSE, Exam Taker: BPSC
1(a)What is heap? Explain how heap property is maintained in binary tree. 3+5 = 8
1(b)How can a graph be represented? Explain Prim's algorithm with an example. 4+4 = 8
Graph Representation
A graph can be represented mainly in two ways:
1) Adjacency Matrix:
It is a 2D array of size V × V (where V = number of vertices). If there is an edge between vertex i and j, the value is 1 (or weight for weighted graph); otherwise 0.
Example:
For a graph with vertices A, B, C and edges A–B, B–C:
A B C A [ 0 1 0 ] B [ 1 0 1 ] C [ 0 1 0 ]
2) Adjacency List:
Each vertex stores a list of its adjacent vertices. It requires less memory and is suitable for sparse graphs.
Example:
A → B B → A, C C → B
Prim’s Algorithm Prim’s Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a weighted, connected, undirected graph. The MST connects all vertices with minimum total edge weight and without forming cycles.
Steps of Prim’s Algorithm:
1) Start from any vertex.
2) Select the minimum weight edge that connects a visited vertex to an unvisited vertex.
3) Add the selected edge to the MST.
4) Repeat until all vertices are included.
Example: 
Graph প্রধানত দুইভাবে উপস্থাপন করা যায়:
১) Adjacency Matrix:এটি একটি 2D array (V × V), যেখানে V হলো vertex সংখ্যা। যদি i ও j vertex-এর মধ্যে edge থাকে তবে মান 1 (বা weighted graph হলে weight), না থাকলে 0।
উদাহরণ:Vertex A, B, C এবং edge A–B, B–C হলে:
A B C A [ 0 1 0 ] B [ 1 0 1 ] C [ 0 1 0 ]
২) Adjacency List:
প্রতিটি vertex-এর সাথে সংযুক্ত vertex-এর তালিকা সংরক্ষণ করা হয়। এটি কম memory ব্যবহার করে এবং sparse graph-এর জন্য উপযোগী।
উদাহরণ:
A → B B → A, C C → B
Prim’s Algorithm Prim’s Algorithm হলো একটি greedy algorithm যা weighted, connected, undirected graph-এর Minimum Spanning Tree (MST) নির্ণয় করতে ব্যবহৃত হয়। MST সব vertex-কে minimum মোট weight দিয়ে সংযুক্ত করে এবং কোনো cycle তৈরি করে না।
Prim’s Algorithm-এর ধাপসমূহ:
1) যেকোনো একটি vertex থেকে শুরু করতে হবে।
2) এমন minimum weight edge নির্বাচন করতে হবে যা visited vertex থেকে unvisited vertex-এ যায়।
3) সেই edge MST-তে যুক্ত করতে হবে।
4) সব vertex অন্তর্ভুক্ত না হওয়া পর্যন্ত প্রক্রিয়া চালাতে হবে।
উদাহরণ:
2(a) Write an algorithm for finding the k-th smallest element in an array of n elements. Analyze the complexity of your algorithm. 4+4 = 8
Method: Using QuickSelect (Efficient Approach)
The QuickSelect algorithm is based on the partition process of QuickSort. It finds the k-th smallest element without fully sorting the array.
Pseudocode:
QUICKSELECT(A, low, high, k) 1. if low = high 2. return A[low] 3. pivotIndex ← PARTITION(A, low, high) 4. if pivotIndex = k 5. return A[pivotIndex] 6. else if k < pivotIndex 7. return QUICKSELECT(A, low, pivotIndex - 1, k) 8. else 9. return QUICKSELECT(A, pivotIndex + 1, high, k) PARTITION(A, low, high) 1. pivot ← A[high] 2. i ← low - 1 3. for j ← low to high - 1 4. if A[j] ≤ pivot 5. i ← i + 1 6. swap A[i] and A[j] 7. swap A[i + 1] and A[high] 8. return i + 1
Note: To find the k-th smallest element, call QUICKSELECT(A, 0, n-1, k-1) (assuming 0-based index).
Complexity Analysis:
- Best Case: O(n)
- Average Case: O(n)
- Worst Case: O(n²) (when pivot selection is poor)
- Space Complexity: O(1) (in-place, ignoring recursion stack)
Thus, QuickSelect is efficient for finding the k-th smallest element compared to fully sorting the array (which takes O(n log n)).
