Advanced Algorithms · End Term · Jan 2026 · FN

We are given a non-empty list of

ordered triplets where each triplet holds three integers and represents a cuboid-shaped disk. These integers denote each disk's width, depth, and height, respectively. Your goal is to stack up the disks and to maximize the total height of the stack. A disk must have a strictly smaller width, depth, and height than any other disk below it. Our goal is to design an algorithm that returns the total height of the optimal stack, starting with the top disk and ending with the bottom disk. Note that you can't rotate disks. You can assume that there will only be one stack with the greatest total height. We also use

-based indexing in the subquestions given.

Can the disk with dimensions [2,1,2] be placed above [3,2,3]?

We are given a non-empty list of

ordered triplets where each triplet holds three integers and represents a cuboid-shaped disk. These integers denote each disk's width, depth, and height, respectively. Your goal is to stack up the disks and to maximize the total height of the stack. A disk must have a strictly smaller width, depth, and height than any other disk below it. Our goal is to design an algorithm that returns the total height of the optimal stack, starting with the top disk and ending with the bottom disk. Note that you can't rotate disks. You can assume that there will only be one stack with the greatest total height. We also use

-based indexing in the subquestions given.

Can the disk with dimensions [2,2,2] be placed above [3,2,3]?

We are given a non-empty list of

ordered triplets where each triplet holds three integers and represents a cuboid-shaped disk. These integers denote each disk's width, depth, and height, respectively. Your goal is to stack up the disks and to maximize the total height of the stack. A disk must have a strictly smaller width, depth, and height than any other disk below it. Our goal is to design an algorithm that returns the total height of the optimal stack, starting with the top disk and ending with the bottom disk. Note that you can't rotate disks. You can assume that there will only be one stack with the greatest total height. We also use

-based indexing in the subquestions given.

Suppose the input consists of the following triplets: [[3, 5, 7], [3, 2, 2], [3, 1, 1], [5, 5, 9]]. What's the answer?

We are given a non-empty list of

ordered triplets where each triplet holds three integers and represents a cuboid-shaped disk. These integers denote each disk's width, depth, and height, respectively. Your goal is to stack up the disks and to maximize the total height of the stack. A disk must have a strictly smaller width, depth, and height than any other disk below it. Our goal is to design an algorithm that returns the total height of the optimal stack, starting with the top disk and ending with the bottom disk. Note that you can't rotate disks. You can assume that there will only be one stack with the greatest total height. We also use

-based indexing in the subquestions given.

Our approach will be to building a DP table of the same length as the array of disks. Let

denote the

disk in the input array. The value of DP

will be the height of the tallest tower that can be created with

the bottom. We initialize the value of DP

to the height of

. Consider the following approach. We process the DP array in increasing order of indices (i.e,

to

). We look at all disks

where

and

can be placed on top of

. If

can be placed on top of

, then DP

is updated to be the maximum of DP

and DP

, where

is the height of the disk

. What can you say about this approach?

We are given a non-empty list of

ordered triplets where each triplet holds three integers and represents a cuboid-shaped disk. These integers denote each disk's width, depth, and height, respectively. Your goal is to stack up the disks and to maximize the total height of the stack. A disk must have a strictly smaller width, depth, and height than any other disk below it. Our goal is to design an algorithm that returns the total height of the optimal stack, starting with the top disk and ending with the bottom disk. Note that you can't rotate disks. You can assume that there will only be one stack with the greatest total height. We also use

-based indexing in the subquestions given.

With the same notation as in the previous question, consider the following alternate approach. We process the DP array in increasing order of indices (i.e,

to

). We look at all disks

such that

can be placed on top of

. If

can be placed on top of

, then DP

is updated to be the maximum of DP

and DP

, where

is the height of the disk

. Note that the DP array is initialized as before, that is, DP

is initialized to the height of

. What can you say about this approach?

We are given a non-empty list of

ordered triplets where each triplet holds three integers and represents a cuboid-shaped disk. These integers denote each disk's width, depth, and height, respectively. Your goal is to stack up the disks and to maximize the total height of the stack. A disk must have a strictly smaller width, depth, and height than any other disk below it. Our goal is to design an algorithm that returns the total height of the optimal stack, starting with the top disk and ending with the bottom disk. Note that you can't rotate disks. You can assume that there will only be one stack with the greatest total height. We also use

-based indexing in the subquestions given.

With the same notation as in the previous questions, consider the following alternate approach. We first organize the disks in non-decreasing order of heights, that is,

is a disk that has the smallest height, while

is a disk that has the largest height. We process the DP array in increasing order of indices (i.e,

to

). We look at all disks

where

such that

can be placed on top of

. If

can be placed on top of

, then DP

is updated to be the maximum of DP

and DP

, where

is the height of the disk

. What can you say about this approach?

We are given a non-empty list of

ordered triplets where each triplet holds three integers and represents a cuboid-shaped disk. These integers denote each disk's width, depth, and height, respectively. Your goal is to stack up the disks and to maximize the total height of the stack. A disk must have a strictly smaller width, depth, and height than any other disk below it. Our goal is to design an algorithm that returns the total height of the optimal stack, starting with the top disk and ending with the bottom disk. Note that you can't rotate disks. You can assume that there will only be one stack with the greatest total height. We also use

-based indexing in the subquestions given.

What is the complexity of this algorithm?

Answer the given subquestions about matroids.

The rank function of a matroid

, denoted by either

or

, is defined by:

Does the rank function satisfy the following property for any pair of subsets

?

Answer the given subquestions about matroids.

Let

be a matroid and let

where

. This is the set system obtained by "removing" an element

from

. Is

also a matroid?

Answer the given subquestions about matroids.

Choose the correct option(s):

Consider a universe

of

couples. A subset

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 heriditary property, that is, if

is a good set and

, then

is also a good set.

Consider a universe

of

couples. A subset

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

and

where

and

. Then there exists an element

such that

is a good set.

Consider a universe

of

couples. A subset

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.

Recall that the exchange property is the following. If

and

are good sets and

then there exists an element

such that

is a good set. The family of all good sets satisfies the exchange property. Note that we make no assumption about

unlike the previous question.

In this question, we will examine the relationship of treewidth with other graph parameters.

Let

be an undirected connected graph and

be a depth-first search (DFS) tree of

rooted at a vertex

. Depth of

is the length of a longest path from root to a leaf. Let

be the depth of

. Which of the following statements are true?

In this question, we will examine the relationship of treewidth with other graph parameters.

What is the treewidth of

, a simple cycle on

vertices?

Recall the max-flow problem: for a directed graph

with non-negative capacities

for every

and two special vertices

(source, with no incoming edges) and

(sink, with no outgoing edges), a flow in

is an assignment

such that

for every edge and for every vertex

. The task is to find a maximum flow (f) i.e., a flow (f) such that

is maximized. Given an instance

, we attempt here to design a LP whose optimal value is equal to the maximum flow in the graph

. There is a variable

for all

. Note that for any pair of vertices that is not an edge, we do not introduce any variable corresponding to it.

Is the LP above a valid formulation for computing the maximum flow in

?

Given a flow network

and a flow

, how will you determine if

is maximum flow?

Consider the LP for vertex cover for the graph

shown in the figure below.

Based on the above data, answer the given subquestions.

The value of the optimal solution for the Vertex Cover LP corresponding to

is less than 2.

Consider the LP for vertex cover for the graph

shown in the figure below.

Based on the above data, answer the given subquestions.

The value of the optimal solution for the Vertex Cover LP corresponding to

is 2.

Consider the LP for vertex cover for the graph

shown in the figure below.

Based on the above data, answer the given subquestions.

The size of the smallest vertex cover of

is 2.

Consider the LP for vertex cover for the graph

shown in the figure below.

Based on the above data, answer the given subquestions.

The all-

solution is optimal for the Vertex Cover LP corresponding to

.

Consider the LP for vertex cover for the graph

shown in the figure below.

Based on the above data, answer the given subquestions.

After deleting the vertex

from

, the value of the optimal LP solution decreases by 1.

Let

be a graph with positive edge weights. Then its aspect ratio is the quantity

. Given a graph

, a reweighted graph on the same vertex and edge set

is **shortest-paths preserving** if, for every shortest path

in

, the sequence of nodes and edges along

is also a shortest path in

. Based on the above data, answer the given subquestions.

Consider the following graphs

and

. Note that

has aspect ratio

and

has aspect ratio

. Is

shortest-paths preserving with respect to

?

Let

be a graph with positive edge weights. Then its aspect ratio is the quantity

. Given a graph

, a reweighted graph on the same vertex and edge set

is **shortest-paths preserving** if, for every shortest path

in

, the sequence of nodes and edges along

is also a shortest path in

. Based on the above data, answer the given subquestions.

Suppose you reweight the graph

shown below on the left to the graph (H) on the right. Suppose

is shortest-paths preserving. Then what can you say about

?

Let

be a graph with positive edge weights. Then its aspect ratio is the quantity

. Given a graph

, a reweighted graph on the same vertex and edge set

is **shortest-paths preserving** if, for every shortest path

in

, the sequence of nodes and edges along

is also a shortest path in

. Based on the above data, answer the given subquestions.

Consider any reweighted graph

of

that is shortest-paths preserving, where

is the graph from part (b). Then the aspect ratio of

:

Let

be a graph with positive edge weights. Then its aspect ratio is the quantity

. Given a graph

, a reweighted graph on the same vertex and edge set

is **shortest-paths preserving** if, for every shortest path

in

, the sequence of nodes and edges along

is also a shortest path in

. Based on the above data, answer the given subquestions.

Consider the following claim: for any DAG

, it is possible to always find a re-weighting that is shortest-paths preserving such that the aspect ratio with the new weight function is at most

, where

is the number of vertices in

. Is this claim true?

Let

be a graph with positive edge weights. Then its aspect ratio is the quantity

. Given a graph

, a reweighted graph on the same vertex and edge set

is **shortest-paths preserving** if, for every shortest path

in

, the sequence of nodes and edges along

is also a shortest path in

. Based on the above data, answer the given subquestions.

Consider the following claim: for any DAG

, it is possible to always find a re-weighting that is shortest-paths preserving such that the aspect ratio with the new weight function is at most

, where

is the number of vertices in

. Is this claim true?

Suppose we are given an ILP which seeks to minimize an objective function subject to constraints. We solve the LP relaxation and find an optimal solution with the objective evaluating to

.What can you say about the original ILP? Based on the above data, answer the given subquestions.

If the ILP is feasible, its optimal solution must be greater than or equal to

.

Suppose we are given an ILP which seeks to minimize an objective function subject to constraints. We solve the LP relaxation and find an optimal solution with the objective evaluating to

.What can you say about the original ILP? Based on the above data, answer the given subquestions.

If the ILP is feasible, its optimal solution must be less than or equal to

.

Suppose we are given an ILP which seeks to minimize an objective function subject to constraints. We solve the LP relaxation and find an optimal solution with the objective evaluating to

.What can you say about the original ILP? Based on the above data, answer the given subquestions.

It is possible that the ILP's optimal solution (if it exists) will be

.

Suppose we are given an ILP which seeks to minimize an objective function subject to constraints. We solve the LP relaxation and find an optimal solution with the objective evaluating to

.What can you say about the original ILP? Based on the above data, answer the given subquestions.

It is possible that the ILP's optimal solution (if it exists) will also be

.

Suppose we are given an ILP which seeks to minimize an objective function subject to constraints. We solve the LP relaxation and find an optimal solution with the objective evaluating to

.What can you say about the original ILP? Based on the above data, answer the given subquestions.

The ILP is guaranteed to be feasible.

Consider the given statements and answer if they are true or false.

The worst-case running time and expected running time are equal to within constant factors for any randomized algorithm.

Consider the given statements and answer if they are true or false.

An adversary can provide randomized quicksort with an input array of length

that forces the algorithm to run in

time on that input. (If you are not familiar with the

asymptotic notation, it roughly translates as "at least". For example, we can say that it is possible to come up with an input that forces insertion sort to run for

steps.)

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex. The CLUSTER VERTEX DELETION problem is the following: Given an input graph

and a parameter

, does there exist a set

of at most

vertices of

such that the subgraph induced on

is a cluster graph. In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph

, parameter

and a set

of vertices of

of size

such that the subgraph induced on

is a cluster graph. We need to find if there exists a subset

of size at most

which is disjoint from

such that the subgraph induced on

is a cluster graph. Determine, for each statement given in the subquestion, if it is true or false.

A graph

is a cluster graph if and only if it does not have an induced path on

vertices.

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex. The CLUSTER VERTEX DELETION problem is the following: Given an input graph

and a parameter

, does there exist a set

of at most

vertices of

such that the subgraph induced on

is a cluster graph. In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph

, parameter

and a set

of vertices of

of size

such that the subgraph induced on

is a cluster graph. We need to find if there exists a subset

of size at most

which is disjoint from

such that the subgraph induced on

is a cluster graph. Determine, for each statement given in the subquestion, if it is true or false.

In the DISJOINT CLUSTER VERTEX DELETION problem, if the subgraph induced on

is not a cluster graph, we can immediately return YES.

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex. The CLUSTER VERTEX DELETION problem is the following: Given an input graph

and a parameter

, does there exist a set

of at most

vertices of

such that the subgraph induced on

is a cluster graph. In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph

, parameter

and a set

of vertices of

of size

such that the subgraph induced on

is a cluster graph. We need to find if there exists a subset

of size at most

which is disjoint from

such that the subgraph induced on

is a cluster graph. Determine, for each statement given in the subquestion, if it is true or false.

In the DISJOINT CLUSTER VERTEX DELETION problem, if the subgraph induced on the vertices of

is not a cluster graph, we can immediately return NO.

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex. The CLUSTER VERTEX DELETION problem is the following: Given an input graph

and a parameter

, does there exist a set

of at most

vertices of

such that the subgraph induced on

is a cluster graph. In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph

, parameter

and a set

of vertices of

of size

such that the subgraph induced on

is a cluster graph. We need to find if there exists a subset

of size at most

which is disjoint from

such that the subgraph induced on

is a cluster graph. Determine, for each statement given in the subquestion, if it is true or false.

If the subgraph induced on the vertices of

is a cluster graph and a vertex in

is adjacent to at least two vertices in

which are in different cliques, then we can delete it and leave the parameter unchanged.

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex. The CLUSTER VERTEX DELETION problem is the following: Given an input graph

and a parameter

, does there exist a set

of at most

vertices of

such that the subgraph induced on

is a cluster graph. In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph

, parameter

and a set

of vertices of

of size

such that the subgraph induced on

is a cluster graph. We need to find if there exists a subset

of size at most

which is disjoint from

such that the subgraph induced on

is a cluster graph. Determine, for each statement given in the subquestion, if it is true or false.

If the subgraph induced on the vertices of

is a cluster graph and a vertex in

is adjacent to at least two vertices in

which are in different cliques, then we can delete it and decrease the parameter by

.

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex. The CLUSTER VERTEX DELETION problem is the following: Given an input graph

and a parameter

, does there exist a set

of at most

vertices of

such that the subgraph induced on

is a cluster graph. In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph

, parameter

and a set

of vertices of

of size

such that the subgraph induced on

is a cluster graph. We need to find if there exists a subset

of size at most

which is disjoint from

such that the subgraph induced on

is a cluster graph. Determine, for each statement given in the subquestion, if it is true or false.

If the subgraph induced on the vertices of

is a cluster graph and a vertex in

is adjacent to some but not all vertices in a clique of

, then we can delete it and leave the parameter unchanged.

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex. The CLUSTER VERTEX DELETION problem is the following: Given an input graph

and a parameter

, does there exist a set

of at most

vertices of

such that the subgraph induced on

is a cluster graph. In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph

, parameter

and a set

of vertices of

of size

such that the subgraph induced on

is a cluster graph. We need to find if there exists a subset

of size at most

which is disjoint from

such that the subgraph induced on

is a cluster graph. Determine, for each statement given in the subquestion, if it is true or false.

If the subgraph induced on the vertices of

is a cluster graph and a vertex in

is adjacent to some but not all vertices in a clique of

, then we can delete it and decrease the parameter by

.

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex. The CLUSTER VERTEX DELETION problem is the following: Given an input graph

and a parameter

, does there exist a set

of at most

vertices of

such that the subgraph induced on

is a cluster graph. In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph

, parameter

and a set

of vertices of

of size

such that the subgraph induced on

is a cluster graph. We need to find if there exists a subset

of size at most

which is disjoint from

such that the subgraph induced on

is a cluster graph. Determine, for each statement given in the subquestion, if it is true or false.

After modifying the input instance, we can solve DISJOINT CLUSTER VERTEX DELETION by solving a matching problem on a bipartite graph.

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex. The CLUSTER VERTEX DELETION problem is the following: Given an input graph

and a parameter

, does there exist a set

of at most

vertices of

such that the subgraph induced on

is a cluster graph. In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph

, parameter

and a set

of vertices of

of size

such that the subgraph induced on

is a cluster graph. We need to find if there exists a subset

of size at most

which is disjoint from

such that the subgraph induced on

is a cluster graph. Determine, for each statement given in the subquestion, if it is true or false.

DISJOINT CLUSTER VERTEX DELETION is NP-Hard.

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex. The CLUSTER VERTEX DELETION problem is the following: Given an input graph

and a parameter

, does there exist a set

of at most

vertices of

such that the subgraph induced on

is a cluster graph. In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph

, parameter

and a set

of vertices of

of size

such that the subgraph induced on

is a cluster graph. We need to find if there exists a subset

of size at most

which is disjoint from

such that the subgraph induced on

is a cluster graph. Determine, for each statement given in the subquestion, if it is true or false.

There exists a

algorithm for CLUSTER VERTEX DELETION.

**Marbles** is a solitaire game played on an undirected graph

, where each vertex has zero or more marbles. A single move in this game consists of removing two marbles from a vertex

and adding one marble to an arbitrary neighbor of

. Note that the vertex

must have at least two marbles on it before the move. The **Marbles Elimination** problem asks: given a graph

and a marble count

for each vertex

, is there a sequence of valid moves that removes all but one marble? **Example.** Consider a triangle graph with vertices

and edges

. If we start with marbles

,

,

(total

): 1. Move from

to

: now

,

,

. 2. Move from

to

: now

,

,

. 3. Move from

to

: now

,

,

. We end with exactly

marble. Based on the above data, answer the given subquestions.

Consider a path graph

with vertices

(edges

). Starting configuration:

(total

marbles). Can the game be won (reduced to exactly

marble)?

**Marbles** is a solitaire game played on an undirected graph

, where each vertex has zero or more marbles. A single move in this game consists of removing two marbles from a vertex

and adding one marble to an arbitrary neighbor of

. Note that the vertex

must have at least two marbles on it before the move. The **Marbles Elimination** problem asks: given a graph

and a marble count

for each vertex

, is there a sequence of valid moves that removes all but one marble? **Example.** Consider a triangle graph with vertices

and edges

. If we start with marbles

,

,

(total

): 1. Move from

to

: now

,

,

. 2. Move from

to

: now

,

,

. 3. Move from

to

: now

,

,

. We end with exactly

marble. Based on the above data, answer the given subquestions.

Consider a cycle graph

with vertices

(edges

). Starting configuration:

(total

marbles). Can the game be won (reduced to exactly

marble)?

**Marbles** is a solitaire game played on an undirected graph

, where each vertex has zero or more marbles. A single move in this game consists of removing two marbles from a vertex

and adding one marble to an arbitrary neighbor of

. Note that the vertex

must have at least two marbles on it before the move. The **Marbles Elimination** problem asks: given a graph

and a marble count

for each vertex

, is there a sequence of valid moves that removes all but one marble? **Example.** Consider a triangle graph with vertices

and edges

. If we start with marbles

,

,

(total

): 1. Move from

to

: now

,

,

. 2. Move from

to

: now

,

,

. 3. Move from

to

: now

,

,

. We end with exactly

marble. Based on the above data, answer the given subquestions.

Consider the general **Marbles Elimination** decision problem with the following setup: • Input: A graph

with

vertices, where one designated vertex

has

marbles and all other vertices have

marble each. • Output: TRUE if we can reduce to exactly

marble, FALSE otherwise. What is the complexity of this problem?