Quiz Space

Advanced Algorithms · End Term · 1 Sept 2024 · May 2024 term · Set QDB3

Question 7: We are given a non-empty list of N ordered triplets where…

Question 7

+2 marksOne correct option

We are given a non-empty list of N 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 1-based indexing in the subquestions.
Based on the above data, answer the given subquestions.

  1. A
  2. B
  3. C
  4. D
Show answer

Correct answer

  • B
See the whole paperTake it as a mock test

Question 7 of 54 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) End Term paper sat on 1 Sept 2024, in the May 2024 term (IIT M DEGREE AN EXAM QDB3 01 Sep 2024). It carries 2 marks.

More questions from this paper

  1. Q1Can the disk with dimensions [2,1,2] be placed above [3,2,3]?
  2. Q2Can the disk with dimensions [2,2,2] be placed above [3,2,3]?
  3. Q3Suppose the input consists of the following triplets: [[3, 8, 8], [2, 1, 9], [4, 1, 1], [2, 3, 6]]. What’s the answer?
  4. Q4Our approach will be to building a DP table of the same length as the array of disks. Let d_i denote the i^{th} disk in…
  5. Q5With the same notation as in the previous question, consider the following alternate approach.We process the DP array i…
  6. Q6With the same notation as in the previous questions, consider the following alternate approach. We first organize the d…
  7. Q8We are given a set of N dice, each with S sides, and a target integer T, which represents a target sum to obtain when r…
  8. Q9We are given a set of N dice, each with S sides, and a target integer T, which represents a target sum to obtain when r…
  9. Q10We are given a set of N dice, each with S sides, and a target integer T, which represents a target sum to obtain when r…
  10. Q11We are given a set of N dice, each with S sides, and a target integer T, which represents a target sum to obtain when r…
  11. Q12We are given a set of N dice, each with S sides, and a target integer T, which represents a target sum to obtain when r…
  12. Q13We are given a set of N dice, each with S sides, and a target integer T, which represents a target sum to obtain when r…
  13. Q14We are given a set of N dice, each with S sides, and a target integer T, which represents a target sum to obtain when r…
  14. Q15We are given a set of N dice, each with S sides, and a target integer T, which represents a target sum to obtain when r…
  15. Q16We are given a set of N dice, each with S sides, and a target integer T, which represents a target sum to obtain when r…
  16. Q17We are given a set of N dice, each with S sides, and a target integer T, which represents a target sum to obtain when r…
  17. Q18We are given a set of N dice, each with S sides, and a target integer T, which represents a target sum to obtain when r…
  18. Q19In this question, we use [3] to denote {1, 2, 3}. Let G be a simple undirected finite graph. A function f : V(G) \to [3…
  19. Q20In this question, we use [3] to denote {1, 2, 3}. Let G be a simple undirected finite graph. A function f : V(G) \to [3…
  20. Q21In this question, we use [3] to denote {1, 2, 3}. Let G be a simple undirected finite graph. A function f : V(G) \to [3…
  21. Q22In this question, we use [3] to denote {1, 2, 3}. Let G be a simple undirected finite graph. A function f : V(G) \to [3…
  22. Q23In this question, we use [3] to denote {1, 2, 3}. Let G be a simple undirected finite graph. A function f : V(G) \to [3…
  23. Q24If the ILP is feasible, its optimal solution must be greater than or equal to 54.3
  24. Q25If the ILP is feasible, its optimal solution must be less than or equal to 54.3.
  25. Q26Suppose we are given an ILP which seeks to minimize an objective functions subject to constraints. We solve the LP rela…
  26. Q27It is possible that the ILP’s optimal solution (if it exists) will also be 54.3.
  27. Q28The ILP is guaranteed to be feasible.
  28. Q29Consider the task of counting how many sequences of length n exist consisting only of numbers 0, 1, and 2 such that eac…
  29. Q30Consider the task of counting how many sequences of length n exist consisting only of numbers 0, 1, and 2 such that eac…
  30. Q31Consider the task of counting how many sequences of length n exist consisting only of numbers 0, 1, and 2 such that eac…
  31. Q32Consider the task of counting how many sequences of length n exist consisting only of numbers 0, 1, and 2 such that eac…
  32. Q33Consider the task of counting how many sequences of length n exist consisting only of numbers 0, 1, and 2 such that eac…
  33. Q34Based on the above data, answer the given subquestions.
  34. Q35The final answer is
  35. Q36Based on the above data, answer the given subquestions.
  36. Q37Based on the above data, answer the given subquestions.
  37. Q38Based on the above data, answer the given subquestions.
  38. Q39A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…
  39. Q40A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…
  40. Q41A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…
  41. Q42A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…
  42. Q43A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…
  43. Q44A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…
  44. Q45A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…
  45. Q46A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…
  46. Q47A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…
  47. Q48A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…
  48. Q49In this problem you are given as input a graph T = (V, E) that is a tree (that is, T is undirected, connected, and acyc…
  49. Q50Figure question
  50. Q51Recall the max-flow problem: for a directed graph G(V, E) with non-negative capacities c_e for every e \in E and two sp…
  51. Q52Figure question
  52. Q53Figure question
  53. Q54We are given as input a set of n requests (e.g.. for the use of an classroom), with a known start time s_i; and finish …