WorksheetsUnit 4 Class Test
Total questions: 100
Worksheet time: 50mins
Name
Class
Date
1.
In a flow network, if path capacities are [10, 5, 7], what is the bottleneck capacity of this path?
a)
5
b)
7
c)
10
d)
22
2.
A network has max flow of 20. If an edge of capacity 5 is removed from the minimum cut, new max flow = ?
a)
15
b)
20
c)
25
d)
10
3.
If total capacity from source = 30 and total from sink = 25, what is possible max flow?
a)
25
b)
30
c)
20
d)
15
4.
In Ford–Fulkerson, if augmenting paths have capacities [4, 3, 2], total max flow = ?
a)
9
b)
8
c)
7
d)
6
5.
Using Ford–Fulkerson, if flow increases 2 units per iteration for 4 iterations, total flow = ?
a)
4
b)
6
c)
8
d)
10
6.
A bipartite graph with 5 left and 4 right vertices has maximum matching ≤ ?
a)
9
b)
4
c)
5
d)
6
7.
If max flow = 16 and capacity of one edge is reduced by 4, new max flow ≤ ?
a)
16
b)
12
c)
8
d)
20
8.
In push–relabel algorithm, if 3 pushes each of 2 units occur, total flow pushed = ?
a)
4
b)
6
c)
8
d)
10
9.
If distance between points (1,2) and (4,6) = ?
a)
4
b)
5
c)
6
d)
√20
10.
Given 4 points forming a square of side 5, perimeter of convex hull = ?
a)
10
b)
15
c)
20
d)
25
11.
For n=6 points, Graham’s Scan complexity = ?
a)
O(n²)
b)
O(n log n)
c)
O(n³)
d)
O(log n)
12.
In a graph, if max flow = 12 and min cut capacity = 12, what theorem is satisfied?
a)
Dijkstra’s
b)
Max-flow Min-cut
c)
Bellman-Ford
d)
Kruskal’s
13.
Two line segments (1,1)-(3,3) and (1,3)-(3,1) intersect at ?
a)
(1,1)
b)
(2,2)
c)
(3,3)
d)
No intersection
14.
Closest pair among points (1,1), (2,2), (5,5) has distance = ?
a)
√2
b)
√3
c)
3
d)
2
15.
If the Ford–Fulkerson algorithm runs with path capacities decreasing by half each time, starting at 8, total flow after 3 iterations = ?
a)
8
b)
12
c)
14
d)
15
16.
If a flow network has 4 vertices and 5 edges, possible complexity of Ford–Fulkerson using BFS = ?
a)
O(VE²)
b)
O(VE)
c)
O(E²)
d)
O(V²)
17.
A bipartite graph has 4 students and 4 projects. If 3 pairs can be matched, max matching = ?
a)
1
b)
2
c)
3
d)
4
18.
Using push–relabel, a node’s height increases from 0→3 in 3 relabels. Average height change per relabel = ?
a)
1
b)
2
c)
3
d)
0.5
19.
If two edges of a cut have capacities 4 and 7, total cut capacity = ?
a)
11
b)
8
c)
10
d)
7
20.
If closest pair algorithm runs in O(n log n) for n=8, and doubling n roughly doubles log n, runtime increases by factor ≈ ?
a)
2
b)
4
c)
3
d)
1.5
21.
In a flow network, augmenting paths: [3, 2, 5, 4], total flow = ?
a)
12
b)
13
c)
14
d)
15
22.
For convex hull of 8 random points, expected hull vertices ≈ ?
a)
3
b)
4
c)
5
d)
8
23.
In Ford–Fulkerson, if 4 augmenting paths found with capacities [5,4,3,2], final flow = ?
a)
10
b)
12
c)
14
d)
15
24.
Two segments (0,0)-(4,4) and (0,4)-(4,0) intersect. How many intersection points exist?
a)
0
b)
1
c)
2
d)
4
25.
Closest pair for points (0,0), (1,0), (2,0), (4,0) has distance = ?
a)
1
b)
2
c)
3
d)
4
26.
In Ford–Fulkerson, if no augmenting path exists in residual graph, the current flow is
a)
Not maximum
b)
Minimum
c)
Maximum
d)
Undefined
27.
In a flow network, the maximum flow value is equal to
a)
Minimum cut capacity
b)
Maximum path capacity
c)
Sum of all capacities
d)
Product of edge capacities
28.
When Ford–Fulkerson uses integer capacities, it terminates because
a)
Flow increases in fractions
b)
Flow increases by at least 1 each iteration
c)
Flow never increases
d)
Flow decreases
29.
The push–relabel algorithm differs from Ford–Fulkerson in that it
a)
Works without augmenting paths
b)
Uses BFS for flow
c)
Uses DFS for flow
d)
Requires sorting edges
30.
In the relabel-to-front algorithm, the vertex relabeled most frequently is usually
a)
Source
b)
Sink
c)
Highest height vertex
d)
Lowest height vertex
31.
A bipartite graph has 6 left and 6 right vertices. The maximum number of possible matchings = ?
a)
6
b)
12
c)
36
d)
720
32.
In a flow network with edges of capacity [8, 5, 3], the bottleneck capacity = ?
a)
8
b)
5
c)
3
d)
16
33.
For a bipartite matching problem, using flow network representation allows us to
a)
Compute shortest path
b)
Reduce to a max-flow problem
c)
Reduce to min-cost flow
d)
Use Dijkstra’s algorithm
34.
If Ford–Fulkerson runs on irrational capacities, what may happen?
a)
Terminates quickly
b)
May not terminate
c)
Runs in O(VE)
d)
Always gives minimum cut
35.
In push–relabel, a node is eligible for push operation when
a)
Height(u) = Height(v)
b)
Height(u) = Height(v) + 1
c)
Height(u) < Height(v)
d)
Flow(u,v) = 0
36.
Convex hull of points forming a convex polygon with 5 vertices has hull vertices = ?
a)
3
b)
4
c)
5
d)
6
37.
In line segment intersection, if determinant of orientation test is zero, segments are
a)
Parallel or collinear
b)
Intersecting
c)
Skewed
d)
Perpendicular
38.
The time complexity of Graham’s scan algorithm for convex hull is
a)
O(n²)
b)
O(n log n)
c)
O(n³)
d)
O(n)
39.
Closest pair of points using divide and conquer has time complexity
a)
O(n²)
b)
O(n log n)
c)
O(log n)
d)
O(1)
40.
In a network, total inflow = total outflow except at
a)
Source and sink
b)
Sink only
c)
Internal nodes
d)
Every node
41.
Which method ensures polynomial time for max flow computation?
a)
Ford–Fulkerson
b)
Push–Relabel
c)
Randomized augmenting paths
d)
Depth-first search
42.
The number of relabel operations in Push–Relabel algorithm is bounded by
a)
O(VE)
b)
O(V²)
c)
O(V³)
d)
O(E²)
43.
If flow = 10 and min cut = 10, what can be concluded?
a)
Flow < Cut
b)
Flow > Cut
c)
Flow = Cut
d)
No relation
44.
In convex hull, which step ensures removal of interior points?
a)
Sorting by x-coordinate
b)
Orientation test
c)
Finding min y-point
d)
Computing distance
45.
Two line segments intersect if and only if
a)
Endpoints are equal
b)
Orientation tests differ for both pairs
c)
Slopes are equal
d)
Distances are equal
46.
Relabel-to-front algorithm maintains a list of vertices and moves relabeled vertices
a)
To front of list
b)
To end of list
c)
Randomly
d)
Deletes them
47.
In bipartite matching using flow, each edge has capacity = ?
a)
0
b)
1
c)
2
d)
∞
48.
The Euclidean distance between (3,4) and (6,8) = ?
a)
3
b)
4
c)
5
d)
6
49.
When Ford–Fulkerson runs with BFS for shortest augmenting path, it becomes
a)
Push–Relabel
b)
Edmonds–Karp
c)
Relabel-to-Front
d)
Dijkstra’s
50.
Polynomial algorithms are preferred because they
a)
Run in constant time
b)
Run efficiently for large inputs
c)
Are nondeterministic
d)
Use exponential space
51.
A company uses a flow network to model data transfer between servers. If the total incoming capacity is 100 MB/s and outgoing capacity is 90 MB/s, what is the maximum flow possible?
a)
100 MB/s
b)
90 MB/s
c)
190 MB/s
d)
10 MB/s
52.
In a transportation network, Ford–Fulkerson is applied and all augmenting paths are used. If no path is found further, this indicates
a)
A new minimum cut is formed
b)
Flow has reached its maximum
c)
Algorithm failed
d)
Bottleneck edges are removed
53.
A logistics firm models truck routes as a bipartite graph (drivers vs. routes). Each driver can drive one route only. Which algorithm helps in assigning maximum drivers?
a)
Kruskal
b)
Push–Relabel
c)
Max Bipartite Matching
d)
Dijkstra
54.
In a water distribution system modeled as a flow network, one pipe (edge) capacity is reduced from 10L/s to 4L/s. How will this affect max flow?
a)
Increases
b)
Decreases
c)
Remains same
d)
Doubles
55.
A company uses Ford–Fulkerson for resource allocation. After 4 iterations, flow increases by 2, 4, 3, and 1 units. What is total flow achieved?
a)
10
b)
8
c)
12
d)
9
56.
A streaming platform uses Push–Relabel to balance video traffic. A node has excess flow but cannot push forward. What operation is performed?
a)
Relabel
b)
Delete node
c)
Add sink
d)
Reset height
57.
A bipartite graph connects 5 tutors and 5 students. Each tutor can teach only one student. If 4 tutors are assigned, how many matchings remain?
a)
1
b)
5
c)
4
58.
In a computer vision application, convex hull is used to bound detected objects. If 8 points are detected forming a convex polygon, how many hull vertices exist?
a)
4
b)
6
c)
8
d)
5
59.
In a traffic routing problem, Ford–Fulkerson is applied but it loops indefinitely. This can happen when
a)
Capacities are fractional
b)
All edges are equal
c)
Graph is disconnected
d)
Source and sink coincide
60.
A networking firm compares Edmonds–Karp and Push–Relabel for packet routing. Which is faster in dense graphs?
a)
Edmonds–Karp
b)
Ford–Fulkerson
c)
Push–Relabel
d)
Relabel-to-Front
61.
In a robot navigation problem, two paths intersect. Using line segment intersection, what condition confirms intersection?
a)
Parallel lines
b)
Opposite orientation signs
c)
Same slope
d)
Equal distances
62.
A set of GPS coordinates is used to find the smallest convex boundary around locations. Which algorithm applies?
a)
Dijkstra
b)
Kruskal
c)
Graham’s Scan
d)
Bellman-Ford
63.
In a radar detection system, closest pair of objects is found to be 2 km apart using divide and conquer. Reducing it to 1 km means
a)
Better clustering
b)
Faster detection
c)
Reduced noise
d)
Increased distance
64.
During push–relabel, a node with higher height pushes to a neighbor. If all neighbors have equal height, algorithm must
a)
Relabel node
b)
Stop process
c)
Reduce capacity
d)
Merge nodes
65.
In a supply chain modeled as flow network, maximum flow equals total supply. This means
a)
Flow is less than cut
b)
Flow equals cut
c)
Cut is zero
d)
Bottleneck not found
66.
A firm uses relabel-to-front to manage resource distribution. When a node is relabeled, it is moved
a)
To front of list
b)
To end of list
c)
Deleted
d)
Ignored
67.
A delivery company tracks city connections using a graph. The Ford–Fulkerson algorithm repeatedly increases flow until
a)
Source disconnects
b)
Sink disconnects
c)
No augmenting path exists
d)
Capacities double
68.
In a GIS mapping task, determining if two roads intersect is solved using
a)
Convex hull
b)
Push–Relabel
c)
Line segment intersection
d)
Max flow
69.
A flow network has total capacity of 20, but flow achieved is 15. What can improve flow?
a)
Increase edge capacity
b)
Add edges to sink
c)
Reduce edges
d)
Both A and B
70.
In a geometric clustering system, convex hull helps to
a)
Connect random points
b)
Form smallest enclosing polygon
c)
Remove intersecting lines
d)
Minimize edge weights
71.
In a bipartite graph modeling internships and students, if 8 of 10 students are placed, this implies
a)
Max matching found
b)
Graph disconnected
c)
Capacity exceeded
d)
Flow not saturated
72.
A navigation algorithm compares distance between 100 GPS points. To reduce computations, the best algorithm is
a)
Brute force
b)
Divide and conquer
c)
DFS
d)
Greedy
73.
If Ford–Fulkerson gives max flow = 12 and min cut = 12, then
a)
Flow < Cut
b)
Flow > Cut
c)
Flow = Cut
d)
Flow undefined
74.
In a graphics rendering system, convex hull is applied to detect outer boundaries of polygons. This step primarily
a)
Finds internal points
b)
Simplifies object shapes
c)
Reduces memory
d)
Eliminates all data
75.
A company wants to test efficiency of Push–Relabel and Relabel-to-Front algorithms. Both yield same flow, but one is faster due to
a)
Fewer relabel operations
b)
More augmenting paths
c)
Parallel flow usage
d)
Higher memory
76.
Assertion (A): In a flow network, maximum flow is equal to minimum cut. Reason (R): The Max-Flow Min-Cut theorem ensures this equality.
a)
A and R are true, and R is the correct explanation
b)
A true, R false
c)
A false, R true
d)
Both false
77.
A: Ford–Fulkerson algorithm terminates for integer capacities. R: Each augmentation increases flow by at least 1 unit.
a)
A and R true, R correct explanation
b)
A true, R false
c)
A false, R true
d)
Both false
78.
A: Push–Relabel algorithm works even without finding augmenting paths. R: It maintains height labels to guide local pushes.
a)
A and R true, R correct explanation
b)
A true, R false
c)
A false, R true
d)
Both false
79.
A: In bipartite graphs, maximum matching can be reduced to a max flow problem. R: Each vertex pair is connected with edges of capacity 1.
a)
A and R true, R correct explanation
b)
A true, R false
c)
A false, R true
d)
Both false
80.
A: The relabel-to-front algorithm reorders vertices frequently. R: This reduces the number of relabel operations overall.
a)
A and R true, R correct explanation
b)
A true, R false
c)
A false, R true
d)
Both false
81.
A: The Ford–Fulkerson method may not terminate with irrational capacities. R: Augmenting path increments can approach infinity without completion.
a)
A and R true, R correct explanation
b)
A true, R false
c)
A false, R true
d)
Both false
82.
A: In convex hull algorithms, all points inside the hull are irrelevant for the boundary. R: Convex hull only includes outermost points forming minimal convex polygon.
a)
A and R true, R correct explanation
b)
A true, R false
c)
A false, R true
d)
Both false
83.
A: In line segment intersection, collinear points can intersect. R: The orientation test gives zero for collinear points.
a)
A and R true, R correct explanation
b)
A true, R false
c)
A false, R true
d)
Both false
84.
A: In the closest pair problem, brute-force takes O(n²). R: Each pair must be compared once to find the smallest distance.
a)
A and R true, R correct explanation
b)
A true, R false
c)
A false, R true
d)
Both false
85.
A: Push–Relabel algorithm maintains a height function. R: It ensures flow always moves from higher to lower height nodes.
a)
A and R true, R correct explanation
b)
A true, R false
c)
A false, R true
d)
Both false
86.
A: The Ford–Fulkerson algorithm can be optimized using BFS. R: BFS ensures shortest augmenting path selection.
a)
A and R true, R correct explanation
b)
A true, R false
c)
A false, R true
d)
Both false
87.
A: Convex hull of 4 points in a square includes all 4 points. R: No point lies inside since all are extreme points.
a)
A and R true, R correct explanation
b)
A true, R false
c)
A false, R true
d)
Both false
88.
A: Line segments intersect when orientations of endpoints differ. R: This is checked using the cross-product sign method.
a)
A and R true, R correct explanation
b)
A true, R false
c)
A false, R true
d)
Both false
89.
A: Push–Relabel algorithm can have higher memory use. R: It maintains excess and height values for each vertex.
a)
A and R true, R correct explanation
b)
A true, R false
c)
A false, R true
d)
Both false
90.
A: In a bipartite graph, matching all vertices implies perfect matching. R: A perfect matching connects every vertex from both sets uniquely.
a)
A and R true, R correct explanation
b)
A true, R false
c)
A false, R true
d)
Both false
91.
A: In Ford–Fulkerson, if no augmenting path exists, algorithm stops. R: No further improvement in flow is possible beyond the cut.
a)
A and R true, R correct explanation
b)
A true, R false
c)
A false, R true
d)
Both false
92.
A: Convex hull algorithms can detect boundary of objects in images. R: Outermost pixel coordinates can be treated as points.
a)
A and R true, R correct explanation
b)
A true, R false
c)
A false, R true
d)
Both false
93.
A: Closest pair of points algorithm helps reduce search time in large datasets. R: Divide and conquer strategy reduces comparisons to O(n log n).
a)
A and R true, R correct explanation
b)
A true, R false
c)
A false, R true
d)
Both false
94.
A: Relabel-to-front algorithm reorders vertex list dynamically. R: It improves average performance over push–relabel by prioritizing active nodes.
a)
A and R true, R correct explanation
b)
A true, R false
c)
A false, R true
d)
Both false
95.
A: Ford–Fulkerson finds maximum flow but not minimum cost. R: It focuses on capacity utilization, not cost optimization.
a)
A and R true, R correct explanation
b)
A true, R false
c)
A false, R true
d)
Both false
96.
A: The orientation test can detect both parallel and intersecting lines. R: Parallel lines yield zero cross-product result.
a)
A and R true, R correct explanation
b)
A true, R false
c)
A false, R true
d)
Both false
97.
A: In a flow network, increasing one edge capacity always increases max flow. R: Flow depends only on total capacity of all edges.
a)
A true, R false
b)
A and R true, R correct explanation
c)
A false, R true
d)
Both false
98.
A: Convex hull of collinear points includes only endpoints. R: Internal collinear points do not affect convex boundary.
a)
A and R true, R correct explanation
b)
A true, R false
c)
A false, R true
d)
Both false
99.
A: In push–relabel, preflow may temporarily violate flow conservation. R: Excess flow is later pushed to achieve valid flow.
a)
A and R true, R correct explanation
b)
A true, R false
c)
A false, R true
d)
Both false
100.
A: Polynomial algorithms are more efficient than NP algorithms. R: NP algorithms may require exponential time for worst-case inputs.
a)
A and R true, R correct explanation
b)
A true, R false
c)
A false, R true
d)
Both false
100 %
