৪৯তম বিসিএস ⎯ কম্পিউটার সায়েন্স (CSE) [৯৭১] · তারিখ অনির্ধারিত · ৪৮ প্রশ্ন
Answer: C
Asymptotic notations are mathematical tools used to describe the running time or space requirement of an algorithm as the input size (n) grows very large (n → ∞).
They focus only on growth rate, i.e., how fast the runtime increases as input size increases.
Asymptotic analysis studies growth as input size approaches infinity.
Answer: B
Asymptotic analysis does not calculate exact runtime, only growth trends.
Other options are valid uses.
Answer: D
Big-O provides an asymptotic upper bound (worst-case growth).
Eg: f(n) = 3n2 + 5n + 2 → O(n2).
Answer: A
O(1) = constant → independent of input size.
Example: accessing an array element.
Answer: C
Growth hierarchy: 1 < log n < n < n log n < n² < n³ < 2ⁿ < n!
O(1) → Flat line
log n → Slow rise
n → Straight line
n log n → Slightly faster than linear
n² → Steep curve
2ⁿ → Explodes rapidly
n! → Even faster than exponential
Answer: B
Explanation: n2 grows faster than √n and log variations.
Answer: D
Explanation: Big-Θ provides tight bounds (both upper and lower simultaneously).
(Big-O): Upper bound (worst case).
Ω (Big-Omega): Lower bound (best case).
Θ (Big-Theta): Tight bound.
o (Little-o): Strictly smaller growth.
ω (Little-omega): Strictly larger growth.
Answer: B
Merge Sort divides the array into halves, sorts recursively, and merges results → classic divide and conquer
Answer: D
A Divide & Conquer (D&C) algorithm does three things:
Divide: Split the problem of size n into smaller subproblems (often 2 halves).
Conquer: Solve each subproblem recursively.
Combine: Merge the sub-results into the full answer.
Merge sort, Binary search and Quick sort algorithm are based on Divide & Conquer
Bubble sort is iterative (comparison-based), not divide-and-conquer.
Answer: A
Explanation: Divide and Conquer → Divide → Solve (recursively) → Combine.
Answer: C
Explanation: If pivot is smallest/largest → highly unbalanced recursion → O(n²).
Best Case / Average Case: Pivot divides the array almost equally each time.
Example: size n = 16, pivot splits into 8 + 7.
Recurrence: T(n) = 2T(n/2) + Θ(n)
⇒ Θ(n log n)
Depth of recursion = log n, each level costs Θ(n).
Total = Θ(n log n).
Worst Case (Pivot = smallest/largest element)
Suppose pivot is always the smallest element:
Left side = 0 elements, Right side = n−1 elements.
Example: Sorting [1, 2, 3, 4, 5] with pivot = smallest.
Recurrence becomes: T(n) = T(n−1) + Θ(n)
Partitioning costs Θ(n). Then we recurse on n−1 elements.
T(n) = T(n−1) + n
= T(n−2) + (n−1) + n
= …
= Θ(1 + 2 + 3 + … + n)
= Θ(n²)
Answer: C
Merge sort always divides and merges in O(n log n), regardless of input.
Quick Sort : average Θ(n log n) but worst-case Θ(n²) (pivot-dependent).
Selection Sort: always Θ(n²) — no divide step.
Insertion Sort : worst Θ(n²), best O(n) (nearly sorted arrays).
So Merge Sort is the only one of the four that always runs in Θ(n log n).
Answer: D Quick Sort is faster in practice for large database
Average time complexity: Θ(n log n), same as Merge Sort and Heap Sort.
Cache-friendly: Works mostly in-place (good memory locality).
Low constant factors: Less overhead compared to Merge Sort’s extra arrays and Heap Sort’s swaps.
On the other hand
Merge Sort: Guarantees O(n log n), but needs extra space (O(n)) and has more overhead.
Heap Sort: O(n log n) worst-case, but more comparisons and less cache-efficient → slower in practice.
Bubble Sort: Always O(n²), far too slow for large datasets.
Answer: B
Dynamic Programming (DP) is effective when the problem has overlapping subproblems (same subproblem appears multiple times) and optimal substructure (solution can be composed from sub-solutions).
Answer: D
Fibonacci Numbers is an example of a Dynamic Programming. Fibonacci computation has overlapping subproblems. Memorization or tabulation avoids redundant computations.
Where, Binary search, Quick sort, Merge sort are the example Divide and Conquer approach.
Answer: D
Explanation: All these problems have optimal substructure and overlapping subproblems, suitable for DP.
Answer: B
DP is about solving overlapping subproblems once, storing results (memoization or tabulation), and reusing them to avoid recomputation. This reduces exponential problems (like Fibonacci recursion) to polynomial.
Answer: C
Greedy-choice is used in greedy algorithms, not DP.
Answer: B) 0/1 Knapsack Problem
Explanation: 0/1 Knapsack (decision) is NP-Complete (in NP), not NP-Hard whereas remaining three are NP- hard .
Answer: C
Explanation: Space complexity = memory needed for input, variables, recursion, etc.
Answer: B) Hard to solve, easy to verify
P: Easy to solve, easy to verify.
NP-Complete: The hardest problems in NP but easy to verify (both NP + NP-Hard).
NP-Hard: Harder than NP, not always verifiable in polynomial time.
Answer - B) The approach followed in Floyd Warshall’s algorithm is dynamic programming.
Answer: B
Explanation: Greedy algorithms repeatedly make a local optimal choice (a greedy choice) and never reconsider it. They work when local choices lead to a global optimum (via greedy-choice property + optimal substructure).
Option
A is divide & conquer;
C is brute-force;
D is backtracking.
Answer: C
Explanation: Both Kruskal (pick smallest-weight edges that don’t form a cycle) and Prim (grow a tree by adding smallest-weight edge crossing the cut) are greedy. Correctness proofs use cut and cycle properties (exchange arguments). Typical complexities: Kruskal O(E log E), Prim with heap O(E log V).
Answer - A) Time and space complexity are the main measures of the efficiency of an algorithm.
Answer: C
Explanation: 0/1 Knapsack requires Dynamic Programming because greedy may fail; fractional Knapsack is solvable greedily.
Answer: B
Explanation: Huffman coding combine two nodes with smallest frequency iteratively → ensures minimal total cost.
example:
| Symbol | Frequency |
| ------ | --------- |
| A | 5 |
| B | 9 |
| C | 12 |
| D | 13 |
| E | 16 |
| F | 45 |
Pick 5 (A) and 9 (B) → combine to 14
Pick 12 (C) and 13 (D) → combine to 25
Pick 14 and 16 (E) → combine to 30
Pick 25 and 30 → combine to 55
Pick 45 (F) and 55 → root = 100
Resulting Huffman tree minimizes total weighted path length.
Answer: B
Explanation: Branch and Bound (B&B) is designed for combinatorial optimization problems, like Travelling Salesman, Knapsack, etc.
Answer: D
Explanation: B&B is flexible. DFS uses less memory, BFS explores level by level, and best-first explores nodes with the best bound first (often faster).
Answer: A
Explanation: B&B reduces search but may still explore many nodes if the bound is weak (not tight) or the branching factor is large. Proper bound calculation is crucial for efficiency.
Answer: B
Explanation: Jarvis March constructs convex hull by wrapping points → O(nh), h = number of hull points
Answer: C
Explanation: Sweep line technique is widely used in line intersection, closest pair, and other geometric problems.
Answer: B
Explanation: A graph ?= (?, ?) consists of vertices (nodes) and edges connecting pairs of vertices. Trees are a special type of graph.
Answer: A
Explanation: In a connected undirected graph, there is a path between every pair of vertices.
Answer: A
BFS explores all vertices at the current level before moving to the next level.
Answer: B
Explanation: BFS is level-order, DFS goes deep along a path first.
Answer: B
Explanation: DFS maintains recursion stack; a back edge indicates a cycle.
Answer: C
Explanation: A spanning tree connects all vertices without cycles → exactly V-1 edges.
Answer: B
• Kruskal = greedy algorithm → pick lightest edge → avoid cycles → build MST (Minimum Spanning Tree)
Answer: B
Explanation: Prim with adjacency matrix → O(V^2), efficient for dense graphs. Kruskal better for sparse graphs
Answer: C
Explanation: Number of spanning trees depends on graph connectivity and edges; multiple MSTs possible if weights allow.
Answer: C
Explanation: MST
Connects all vertices with V-1 edges (spanning),
Has minimum possible total edge weight
Forms a tree (no cycles)
Answer: A
Explanation: Bellman-Ford handles negative weights, but not negative cycles for shortest path
Answer: B
Max-Flow computes the largest possible flow from a source vertex to a sink vertex, respecting edge capacities.
Answer: D
Applications of Max-Flow problem include network design, traffic flow, bandwidth, matching problems, and resource allocation (scheduling)
Output: C ) n(n-1)/2
Explanation: First for loop will run for (n) times and another for loop will be run for (n-1) times as the inner loop will only run till the range i which is 1 less than n,
so overall time will be n(n-1)/2.
Answer: B
Pseudocode is a simplified representation of a program's logic, written in plain English to make it easy to understand. Pseudocode helps design logic without worrying about syntax.
Answer: A
Complexity is measured as a function of input size (n).