Quiz Space

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

Question 13: With the same notation as in the previous questions, con…

Question 13

+2 marksOne correct option

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, d1d_1 is a disk that has the smallest height, while dNd_N is a disk that has the largest height.

We process the DP array in increasing order of indices (i.e, i=1i = 1 to i=Ni = N). We look at all disks djd_j where j<ij < i such that djd_j can be placed on top of did_i.

If djd_j can be placed on top of did_i, then DP[i]\text{DP}[i] is updated to be the maximum of DP[i]\text{DP}[i] and DP[j]+H\text{DP}[j] + H, where HH is the height of the disk did_i.

What can you say about this approach?

  1. A

    This approach is correct.

  2. B

    This approach is incorrect, because we might miss some disks that can be placed on top of di, as the given array may not be sorted by height.

  3. C

    This approach is incorrect because the values we are looking up may not be computed correctly when we need them.

Show answer

Correct answer

  • A

    This approach is correct.

See the whole paperTake it as a mock test

Question 13 of 53 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. Q1Figure question
  2. Q2Figure question
  3. Q3In this problem you are given as input a graph T = (V, E) that is a tree (that is, T is undirected, connected, and acyc…
  4. Q4Which of the following statements is true?\ Statement 1: For every graph G and every maximum flow on G, there always ex…
  5. Q5Recall 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…
  6. Q6Figure question
  7. Q7A subset S of vertices in an undirected graph G is half-independent if each vertex in S is adjacent to at most one othe…
  8. Q8Can the disk with dimensions [2,1,2] be placed above [3,2,3]?
  9. Q9Can the disk with dimensions [2,2,2] be placed above [3,2,3]?
  10. Q10Suppose the input consists of the following triplets: [[3, 5, 7], [3, 2, 2], [3, 1, 1], [5, 5, 9]]. What’s the answer?
  11. Q11Our 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…
  12. Q12With the same notation as in the previous question, consider the following alternate approach. We process the DP array …
  13. Q14What is the complexity of this algorithm?
  14. Q15If we have 1 die with 6 sides, how many ways can we achieve a target sum of 4?
  15. Q16If we have 3 dice with 17 sides each, how many ways can we achieve a target sum of 7?
  16. Q17Suppose the input consists of 3 dice, each with 4 sides, and the target sum is 9. What’s the answer?
  17. Q18In which of the following scenarios will the answer be zero?
  18. Q19If we have one die with six sides, what are the achievable targets?
  19. Q20Let DP[N,T ] denote the number of ways to achieve a target sum of T > 0 using N > 0 dice. Which of the following recurs…
  20. Q21What is the value of DP[0, 0]?
  21. Q22What is the value of DP[0, T ] for any T > 0?
  22. Q23What is the value of DP[N , 0] for any N > 0?
  23. Q24What is the value of DP[N , T ] if T \< N ?
  24. Q25What is the complexity of this algorithm ?
  25. Q26Based on the above data, answer the given subquestions.
  26. Q27Based on the above data, answer the given subquestions.
  27. Q28Based on the above data, answer the given subquestions.
  28. Q29In this given subquestion, we will examine the relationship of treewidth with other graph parameters. Let G be an undir…
  29. Q30In this given subquestion, we will examine the relationship of treewidth with other graph parameters. Let G be an undir…
  30. Q31In this given subquestion, we will examine the relationship of treewidth with other graph parameters.
  31. Q32If the ILP is feasible, its optimal solution must be greater than or equal to 54.3
  32. Q33If the ILP is feasible, its optimal solution must be less than or equal to 54.3.
  33. Q34It is possible that the ILP’s optimal solution (if it exists) will be 50 ×10²³³¹.
  34. Q35It is possible that the ILP’s optimal solution (if it exists) will also be 54.3.
  35. Q36The ILP is guaranteed to be feasible.
  36. Q37What is the size of each Ai?
  37. Q38Based on the above data, answer the given subquestions.
  38. Q39Based on the above data, answer the given subquestions.
  39. Q40For n = 4, calculate the number of sequences of length 3 consisting only of numbers 0, 1, and 2 such that each number o…
  40. Q41For n = 6, calculate the number of sequences of length 5 consisting only of numbers 0, 1, and 2 such that each number o…
  41. Q42How many numbers in the interval [1; r] are divisible by pi ? The answer to this question is:
  42. Q43The final answer is:
  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. Q49A 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…
  49. Q50A 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…
  50. Q51A 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…
  51. Q52A 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…
  52. Q53A 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…