Petrobangla Assistant Manager (IT) Exam: 16.09.2022 (BUET)প্রশ্ন ও সমাধান

Black Box Testing is a software testing technique that verifies a system's functionality purely from its inputs and expected outputs, without any knowledge of its internal code, logic or structure — it is based entirely on requirements/specifications, so it is also called Behavioural Testing (as opposed to White Box Testing, which examines internal code paths).

graph LR
  I[Input] --> B["Black Box: System Under Test, internal logic hidden"] --> O[Output]

Equivalence Class Partitioning — for a program computing the square root of an integer in the range 0–5000, the input domain splits into three classes:

Class	Range	Nature
EC1	n < 0	Invalid
EC2	0 ≤ n ≤ 5000	Valid
EC3	n > 5000	Invalid

One representative test case per class is sufficient: {-10, 2500, 6000}.

Boundary Value Analysis (BVA) — since defects cluster at boundaries, test at min−1, min, min+1, max−1, max, max+1:

Test Case	Input	Expected
BVA1	−1	Error/Invalid
BVA2	0	0
BVA3	1	1
BVA4	4999	√4999 (valid)
BVA5	5000	√5000 (valid, upper boundary)
BVA6	5001	Error/Invalid

Exam takeaway: Equivalence partitioning reduces the number of test cases needed by grouping inputs that should behave alike, while boundary value analysis specifically targets the edges of each class, where off-by-one errors most often occur.

Single-source shortest path with negative weights — Bellman-Ford Algorithm

Unlike Dijkstra's algorithm, Bellman-Ford correctly handles negative edge weights and can also detect negative-weight cycles reachable from the source.

Algorithm:

1. Initialize dist[src] = 0, dist[v] = infinity for all other vertices.
2. Repeat V−1 times: for every edge (u, v, w), relax it — if dist[u] + w < dist[v], set dist[v] = dist[u] + w.
3. Do one extra (Vth) pass: if any edge can still be relaxed, the graph contains a negative-weight cycle reachable from the source.

Why V−1 iterations suffice (in the absence of a negative cycle): any simple shortest path visits each vertex at most once, so it has at most V−1 edges; after i iterations, all shortest paths using at most i edges are already correct, so V−1 iterations guarantee correctness for every simple path.

Example (detecting a negative cycle):

Input: 4 vertices, 4 edges
0 -> 1 : 1
1 -> 2 : -1
2 -> 3 : -1
3 -> 0 : -1

graph LR
  n0((0)) -- 1 --> n1((1))
  n1((1)) -- -1 --> n2((2))
  n2((2)) -- -1 --> n3((3))
  n3((3)) -- -1 --> n0((0))

Sum of weights around the cycle 0→1→2→3→0 = 1 − 1 − 1 − 1 = −2 < 0, so it is a negative-weight cycle. Running the Vth relaxation pass finds that dist can still decrease (for example, dist[1] keeps dropping every time we go around the cycle), which is exactly how the algorithm detects it. Output: "Yes, the graph contains a negative cycle."

Complexity: O(V × E) time, O(V) space.

Exam takeaway: Run V−1 relaxations for correct shortest paths; if a Vth pass still relaxes an edge, a negative cycle exists and no finite shortest path is defined for the vertices reachable from it.