1A) This graph adheres to the conditions specified: edges go from a vertex of lower index to a

vertex of higher index, and each node except vn (v4 in this case) has at least one edge leaving
it.

Example :
V : {v1, v2, v3, v4}
E = {(v1, v2) , (v1, v3) , (v1, v4)}

- Start at v1
- From v1, choose the vertex with the smallest index, which is v2 in this case
- From v2, go to v4 since it is the only neighbor with a smaller index
- End at v4

The longest path in this graph is from v1 to v3 to v4. However, in the greedy algorithm, the path
would have been from v1 to v2 to v4, which results in missing the longest path.

1B) Consider the longest path ending at each node.

Denote DP[i] as the length of the longest path ending at node i.
Algorithm:
- Initialize an array DP[] of size n where n is the number of vertices.
- Initialize DP[1] = 0 (since the longest path ending at v1 has length 0).
- Iterate through each node i from 2 to n.
- For each node i, initialize DP[i] = -INF (negative infinity) to denote that no
path ending at i has been found yet.
- For each incoming edge to node i from node j (where j < i), update DP[i]
as max(DP[i], DP[j] + 1).
- Finally, the maximum value in the DP[] array will represent the length of the
longest path from v1 to vn.
This algorithm makes sure that for each node i, DP[i] stores the length of the longest
path ending at i. It computes the longest path by iterating through the nodes in a specific order
and considering the incoming edges.

2A) Assume there exists a subset of jobs S that can be scheduled such that everyone meets
their deadlines, and these jobs are not sorted in increasing order of deadlines.
- If there are two jobs, A and B, in S such that A's deadline is earlier than B's deadline. If
job B is scheduled before job A, it implies that job B finishes before job A.
- However, since job A's deadline is earlier, it should have been scheduled before job B to
meet its deadline.
- If job A's deadline was already missed, it would contradict the assumption that S is a
subset where everyone meets their deadlines.
- Therefore, if a subset S exists where all jobs meet their deadlines, the jobs in S must be
scheduled in increasing order of their deadlines.
2B) Algorithm:
- Define DP[i][j] as the maximum number of jobs that can be scheduled from the first i jobs
and consider only the first j time units.
- Sort the jobs in increasing order of deadlines.
- Initialize a 2D array DP of size (n + 1) x (D + 1), where n is the number of jobs
and D is the maximum deadline.
- Set DP[0][j] = 0 for all j from 0 to D.
- Iterate through each job i from 1 to n:
- For each time unit j from t_i to D (where t_i is the duration of job i):
- Calculate DP[i][j] as max(DP[i - 1][j], DP[i - 1][j - t_i] + 1),
considering whether including job i would increase the number of
scheduled jobs.
- The maximum value in the last row of DP (DP[n][j]) will represent the maximum
number of jobs that can be scheduled within their deadlines.
This algorithm's run time is O(nD) time.

3A) Given that all the books have the same height , h , and the shelf height is greater than h,
algorithm:
- Start with empty shelf
- Iterate through books in order
- Place book in shelf until the thickness exceeds ‘L’
- If book doesn’t fit on shelf, go to the next shelf and place the book there
- Repeat until there are no more books left
The time complexity of this algorithm is O(n)

3B) The algorithm is not optimal when the shelf heights are adjusted to match the tallest book in
the shelf. If there are shorter books before or after a taller one, there is wasted space on the
shelf since the algorithm would make a new shelf due to the thickness limit.
3C) Let DP[i] represent the minimum sum of heights required to store the first i books.
Algorithm:
- Initialize an array DP of size n+1 and set DP[0] = 0.
- Iterate through each book i from 1 to n.
- For each book i, initialize DP[i] = INF (some large value).
- For j from 1 to i, calculate DP[i] as min(DP[i], DP[j-1] + max(height[j:i])), where
height[j:i] represents the maximum height from book j to book i.
- DP[n] will contain the minimum sum of heights required to store all books on shelves.
The time complexity of this algorithm is O(n^2).

4) Algorithm:
- Initialize a 2D array, DP, of size (n+1) x (T+1) where n is the number of cities, T is the
maximum number of days, and DP[i][j] represents the maximum profit achievable by
visiting city i in j days.
- Set DP[1][0] = 0
- For each city i from 1 to n:
- For each day t from 1 to T:
- Calculate DP[i][t] by considering two cases:
- If t is greater than the number of days needed to travel from city i
to city 1 and back:
- DP[i][t] equals the maximum of either:
- DP[i][t-1], which means Adam stays in the current
city.
- DP[1][t - cost_to_travel] + x_i - 100 * t * t, where
cost_to_travel is the number of days required to
travel from city i to city 1 and x_i is the earning at
city i.
- If t is less than or equal to the days needed to travel from city i to
city 1 and back:
- DP[i][t] equals the maximum of either:
- DP[i][t-1], which means Adam stays in the current
city.
- -100 * t * t, indicating that it's not feasible to travel
to city 1 and back within t days, so the earning is
zero.
- Find the maximum value in the last column DP[1][T] as this represents the maximum
profit achievable by visiting city 1 in T days.
The time complexity of this algorithm is O(n * T).
5) Algorithm:
- Create a 2D prefix sum array prefix of the same dimensions as array M.
- Initialize prefix[i][j] = M[i][j].
- Calculate prefix sums row-wise and column-wise to represent the cumulative sums up to
each cell.
- For each row i from 1 to n:
- For each column j from 1 to n:
- prefix[i][j] += prefix[i][j - 1]
- For each column j from 1 to n:
- For each row i from 1 to n:
- prefix[i][j] += prefix[i - 1][j] d
- Initialize a variable max_sum to store the maximum sum found and set it to a very small
value initially.
- Use four nested loops to iterate through all possible subarrays:
- For each starting row start_row from 1 to n:
- For each ending row end_row from start_row to n:
- For each starting column start_col from 1 to n:
- For each ending column end_col from start_col to n:
- Calculate the sum of the subarray using the prefix
sum array:
- current_sum = prefix[end_row][end_col] -
prefix[start_row - 1][end_col] -
prefix[end_row][start_col - 1] +
prefix[start_row - 1][start_col - 1].
- Update max_sum to the maximum value between
max_sum and current_sum.
- After completing all iterations, max_sum will contain the largest sum of elements in any
rectangular subarray of the form M[i...i', j...j'].
The time complexity for this algorithm is O(n^3).

6) Algorithm:
- Create a 2D array DP of size n x n, where DP[i][j] will store the maximum total value that
the first player can collect from cards i to j.
- Initialize the base cases:
- For each index i, set DP[i][i] = vi, as the first player can only pick one card, and
that's the maximum value of that single card.
- Populate the DP array using dynamic programming:
- Iterate through the sequence length from 2 to n
- For each subproblem size len:
- Iterate through each starting index i from 1 to n - len + 1:
- Calculate the ending index j = i + len - 1.
- Consider two scenarios:
- If it's the first player's turn: The first player has two choices:
picking i or picking j.
 - If the first player picks i, the second player will then choose
optimally from the subarray i+1 to j.
- If the first player picks j, the second player will then choose
optimally from the subarray i to j-1.
- The first player's total value is vi + min(DP[i+1][j-1],
DP[i+2][j]). I
- f it's the second player's turn:
- The second player will choose optimally based on what the
first player left them. Hence, the first player's score is the
minimum of what's remaining.
- Store the maximum total value for the first player at indices i and j in the
DP array: DP[i][j] = max(value_if_pick_i, value_if_pick_j).
- After populating the DP array, the first player can determine the optimal move at each
step by looking up the precomputed information in O(1) time. For each turn, the first
player checks DP[i][j] for the current range of cards i to j and decides which card to pick
accordingly.