cs4021_2026T1_Q1_NA.pdf
Advanced Algorithms · Quiz 1 · Jan 2026
← Course papers · Start practice / exam
Questions and published explanations below are available without starting a test. Some questions may not have a published solution yet.
Question 2 MCQ · 3.0 marks
We are given as input a set of n requests (e.g., for the use of a classroom), with a known **start**
**time** [[IMAGE:d8f48cd587745de3_3_2]] and **finish time** [[IMAGE:d8f48cd587745de3_3_3]] for each request [[IMAGE:d8f48cd587745de3_3_4]] .
Assume that all start and finish times are **distinct**.
Two requests are said to conflict if their intervals overlap, i.e., if [[IMAGE:d8f48cd587745de3_3_5]] and [[IMAGE:d8f48cd587745de3_3_6]] .
Our goal is to select a **maximum-cardinality subset** of the given requests that contains **no**
**conflicts**.
**Example:**
Given three requests consuming the intervals [[IMAGE:d8f48cd587745de3_3_7]] , [[IMAGE:d8f48cd587745de3_3_8]] , and [[IMAGE:d8f48cd587745de3_3_9]] , the optimal solution selects
the **first and third** requests.
We aim to design a greedy algorithm of the following form:
At each iteration, we select a new request [[IMAGE:d8f48cd587745de3_3_10]] , include it in the solution-so-far, and delete from future
consideration all requests that conflict with [[IMAGE:d8f48cd587745de3_3_11]] .
Which of the following greedy rules is guaranteed to always compute an optimal solution?
At each iteration, pick the remaining request with the **fewest number of**
**conflicts** with other remaining requests (breaking ties arbitrarily).
At each iteration, pick the remaining request with the **earliest start time**.
At each iteration, pick the remaining request with the **earliest finish time**.
At each iteration, pick the remaining request which requires the **least time**
(i.e., has the smallest value of [[IMAGE:d8f48cd587745de3_4_12]] ) (breaking ties arbitrarily).
A published solution is not available for this question yet.
Question 3 MCQ · 3.0 marks
Consider the following statements about **maximum flow** in a graph:
**Statement 1:**
For every graph [[IMAGE:d8f48cd587745de3_4_13]] and every maximum flow on [[IMAGE:d8f48cd587745de3_4_14]] , there always exists an edge such that
increasing the capacity on that edge will increase the maximum flow possible in the graph.
**Statement 2:**
Suppose the maximum [[IMAGE:d8f48cd587745de3_4_15]] -flow of some graph has value [[IMAGE:d8f48cd587745de3_4_16]] . Now we increase the capacity of
every edge by 1. Then the maximum [[IMAGE:d8f48cd587745de3_4_17]] -flow in this modified graph will have value at most
[[IMAGE:d8f48cd587745de3_4_18]] .
Which of the following is true?
Only Statement 1 is true
Only Statement 2 is true
Both Statement 1 and Statement 2 are true
Neither Statement 1 nor Statement 2 is true
A published solution is not available for this question yet.
Question 4 MCQ · 3.0 marks
Given a flow network [[IMAGE:d8f48cd587745de3_4_19]] and a flow [[IMAGE:d8f48cd587745de3_4_20]] , how will you determine if [[IMAGE:d8f48cd587745de3_4_21]] is a maximum flow?
If there is any edge that is not saturated to full capacity, then we can conclude
that [[IMAGE:d8f48cd587745de3_4_22]] is not a maximum flow.
If the residual graph does not have any augmenting paths, then [[IMAGE:d8f48cd587745de3_4_23]] is a
maximum flow.
If the value of the flow [[IMAGE:d8f48cd587745de3_5_24]] is not the sum of the capacities of the edges coming
out of the source [[IMAGE:d8f48cd587745de3_5_25]] , then [[IMAGE:d8f48cd587745de3_5_26]] is not a maximum flow.
If the value of the flow [[IMAGE:d8f48cd587745de3_5_27]] is not the sum of the capacities of the edges coming
into the sink [[IMAGE:d8f48cd587745de3_5_28]] , then [[IMAGE:d8f48cd587745de3_5_29]] is not a maximum flow.
A published solution is not available for this question yet.
Question 5 MCQ · 3.0 marks
A popular conference is being held, and there are several types of seats: VIP, Regular, and
Economy. Each type of seat has a limited number of available spots. Each attendee has a
preference for the type of seat they want, and the total number of attendees is greater than the
number of available seats. The goal is to allocate the seats to attendees such that each attendee is
assigned to their preferred seat type, and no seat type exceeds its capacity.
How can the given problem of allocating seats to attendees based on their preferences and seat
type capacities be effectively solved?
Using a greedy algorithm to assign seats based on attendee preferences.
Modeling the problem as a maximum flow network with capacities
representing seat limits and flows representing the number of attendees assigned to each seat
type.
Implementing a first-come, first-serve approach without considering the
preferences or seat type capacities.
Assigning all attendees to the VIP seats first and distributing the remaining
attendees among Regular and Economy seats.
A published solution is not available for this question yet.
Question 6 MCQ · 3.0 marks
Let A be a decision problem. Suppose:
• A is in NP
• A is NP-hard
Which of the following must be true?
A is in P
A is NP-complete
A is not solvable in polynomial time
P = NP
A published solution is not available for this question yet.
Question 7 MCQ · 3.0 marks
Consider a universe [[IMAGE:d8f48cd587745de3_6_30]] { [[IMAGE:d8f48cd587745de3_6_31]] } of [[IMAGE:d8f48cd587745de3_6_32]] couples. A subset [[IMAGE:d8f48cd587745de3_6_33]] is good if it has at most
three couples in it. Consider the family of all good sets. What can you say about this family?
Based on the above data, answer the given subquestions.
The family satisfies the hereditary property, that is, if [[IMAGE:d8f48cd587745de3_6_34]] is a good set and [[IMAGE:d8f48cd587745de3_6_35]] , then [[IMAGE:d8f48cd587745de3_6_36]] is also a
good set.
True
False
A published solution is not available for this question yet.
Question 8 MCQ · 3.0 marks
Consider a universe [[IMAGE:d8f48cd587745de3_6_30]] { [[IMAGE:d8f48cd587745de3_6_31]] } of [[IMAGE:d8f48cd587745de3_6_32]] couples. A subset [[IMAGE:d8f48cd587745de3_6_33]] is good if it has at most
three couples in it. Consider the family of all good sets. What can you say about this family?
Based on the above data, answer the given subquestions.
Consider two good sets [[IMAGE:d8f48cd587745de3_6_37]] and [[IMAGE:d8f48cd587745de3_6_38]] where [[IMAGE:d8f48cd587745de3_6_39]] and [[IMAGE:d8f48cd587745de3_6_40]] . Then there exists an element
[[IMAGE:d8f48cd587745de3_6_41]] such that [[IMAGE:d8f48cd587745de3_6_42]] { [[IMAGE:d8f48cd587745de3_6_43]] } is a good set.
True
False
A published solution is not available for this question yet.
Question 9 MSQ · 3.0 marks
The **Longest Increasing Subsequence** problem is defined as follows.
Given a list
[[IMAGE:d8f48cd587745de3_7_44]] of size [[IMAGE:d8f48cd587745de3_7_45]] non-negative integers, determine the Longest Increasing Subsequence(LIS), i.e., the
longest possible subsequence in which the elements of the subsequence are sorted in increasing
order.
Based on the above data, answer the given subquestions.
Consider the following greedy approach to find the **Longest Increasing Subsequence (LIS)**:
Select the first element of the list. Then repeatedly select the next element that is **strictly larger**
**than the last selected element**.
On which of the following inputs does this greedy algorithm give an **incorrect** answer?
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
[20, 18, 16, 14, 12, 10, 8, 6, 4, 2]
[15, 1, 2, 3, 4, 5, 6, 7, 8, 16]
[2, 9, 3, 6, 5, 1, 7, 8, 4, 10]
A published solution is not available for this question yet.
Question 10 MCQ · 3.0 marks
The **Longest Increasing Subsequence** problem is defined as follows.
Given a list
[[IMAGE:d8f48cd587745de3_7_44]] of size [[IMAGE:d8f48cd587745de3_7_45]] non-negative integers, determine the Longest Increasing Subsequence(LIS), i.e., the
longest possible subsequence in which the elements of the subsequence are sorted in increasing
order.
Based on the above data, answer the given subquestions.
Consider the following algorithm to compute the **length of the Longest Increasing**
**Subsequence (LIS)** of a sequence [[IMAGE:d8f48cd587745de3_7_46]] .
**Algorithm: LIS-Length**
[[IMAGE:d8f48cd587745de3_7_47]]
Which of the following expressions should replace the blank( ___ ) so that the algorithm correctly
computes the LIS length?
[[IMAGE:d8f48cd587745de3_8_48]]
[[IMAGE:d8f48cd587745de3_8_49]]
[[IMAGE:d8f48cd587745de3_8_50]]
[[IMAGE:d8f48cd587745de3_8_51]]
A published solution is not available for this question yet.
Question 11 MSQ · 3.0 marks
Which of the following set systems [[IMAGE:d8f48cd587745de3_8_52]] is/are matroids?
Let [[IMAGE:d8f48cd587745de3_8_53]] = {1, 2, 3}.
Let [[IMAGE:d8f48cd587745de3_8_54]] = { [[IMAGE:d8f48cd587745de3_8_55]] , {1}, {2}, {3}, {1,2}, {1,3}}.
Let [[IMAGE:d8f48cd587745de3_8_56]] = {1, 2, 3}.
Let [[IMAGE:d8f48cd587745de3_8_57]] = { [[IMAGE:d8f48cd587745de3_8_58]] , {1}, {2}, {3}, {1,2}, {2,3}, {1,2,3}}.
Let [[IMAGE:d8f48cd587745de3_8_59]] = {1,2,3,4}.
Let [[IMAGE:d8f48cd587745de3_8_60]] = { [[IMAGE:d8f48cd587745de3_8_61]] }.
Let [[IMAGE:d8f48cd587745de3_8_62]] = {1,2,3}.
Let [[IMAGE:d8f48cd587745de3_8_63]] = { [[IMAGE:d8f48cd587745de3_8_64]] , {1}, {2}, {1,2}, {1,3}}.
A published solution is not available for this question yet.
Question 12 MSQ · 3.0 marks
Consider the following problem, called **BoxDepth**:
Given a set of [[IMAGE:d8f48cd587745de3_9_65]] axis-aligned rectangles in the plane, determine the size of the largest subset of
rectangles that contain a common point.
Which of the following statement(s) is/are **TRUE**?
There is a polynomial-time reduction from BoxDepth to MaxClique.
There is a polynomial-time algorithm for BoxDepth.
Only one of the statements (There is a polynomial-time reduction from
BoxDepth to MaxClique) and (There is a polynomial-time algorithm for BoxDepth) can be true
assuming [[IMAGE:d8f48cd587745de3_9_66]] .
BoxDepth can be solved in polynomial time by sweeping a vertical line and
maintaining the maximum number of overlapping rectangles at any point.
A published solution is not available for this question yet.
Question 13 MCQ · 4.0 marks
[[IMAGE:d8f48cd587745de3_9_67]] is an unsorted array composed of positive and negative numbers. We wish to compute the
maximum subarray sum within the array.
**Example:**
[[IMAGE:d8f48cd587745de3_9_68]]
Here, the sum of the elements in the subarray from index 4 to 6 in array [[IMAGE:d8f48cd587745de3_9_69]] is 11, which is the
maximum among all possible subarrays of array [[IMAGE:d8f48cd587745de3_9_70]] . Hence, the output should be 11.
Consider the following algorithm:
**Algorithm: Max-Subarray-Sum**
[[IMAGE:d8f48cd587745de3_10_71]]
Which of the following expressions should replace the blank( ___ ) so that the algorithm correctly
computes the maximum sum subarray?
[[IMAGE:d8f48cd587745de3_10_72]]
[[IMAGE:d8f48cd587745de3_10_73]]
[[IMAGE:d8f48cd587745de3_10_74]]
[[IMAGE:d8f48cd587745de3_10_75]]
A published solution is not available for this question yet.
Question 14 NAT · 3.0 marks
A university wants to cover all **departments {1,2,3,4,5,6,7,8,9}** using the minimum number of
workshops. Each workshop can train certain departments.
Workshops and coverage:
• W1: {1, 2, 3, 4}
• W2: {3, 5, 6}
• W3: {2, 7, 8}
• W4: {4, 6, 9}
• W5: {1, 5, 8}
What is the **minimum number of workshops** required to cover all departments?
A published solution is not available for this question yet.
Question 15 NAT · 3.0 marks
Consider the following tree:
[[IMAGE:d8f48cd587745de3_11_76]]
What is the size of the **maximum independent set** of this tree?
A published solution is not available for this question yet.
Question 16 NAT · 3.0 marks
Let G be a bipartite graph with:
• Total number of vertices = 20
• Size of maximum matching = 8
What is the size of the maximum independent set in G?
A published solution is not available for this question yet.
Question 17 NAT · 4.0 marks
Consider the network given below with source [[IMAGE:d8f48cd587745de3_12_77]] and sink [[IMAGE:d8f48cd587745de3_12_78]] , with the numbers on the edges
denoting maximum capacity across a particular edge.
[[IMAGE:d8f48cd587745de3_12_79]]
The value of the maximum flow in the given network is______ .
A published solution is not available for this question yet.