Quiz Space

Advanced Algorithms · Quiz 2 · 6 Aug 2023 · May 2023 term

Question 7: There are N stones, numbered 1, 2, \ldots, N. For each (1…

Question 7

+2 marksNumerical answer

There are NN stones, numbered 1,2,…,N1, 2, \ldots, N. For each (1⩽i⩽N)(1 \leqslant i \leqslant N), the height of stone ii is hih_i. Assume these heights are stored in an array HH. We are also given an additional parameter K⩽N−1K \leqslant N-1 which denotes the maximum jump length.

There is a frog who is initially on Stone 1. He will repeat the following action some number of times to reach Stone NN:

  • If the frog is currently on Stone ii, jump to one of the following: Stone i+1,i+2,…,i+Ki+1, i+2, \ldots, i+K.
  • Here, a cost of ∣hi−hj∣|h_i - h_j| is incurred, where jj is the stone to land on.

Our goal is to find the minimum possible total cost incurred before the frog reaches Stone NN.

Based on the above data, answer the given subquestions.

Show answer

Correct answer: 40

Question 7 of 15 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) Quiz 2 paper sat on 6 Aug 2023, in the May 2023 term (IIT M DEGREE AN3 EXAM QPE3 06 Aug 2023). It carries 2 marks.

More questions from this paper

  1. Q1For the following sets of timings of dance classes, figure out what is the largest number of classes that you can atten…
  2. Q2Consider 4 sets as follows: W = {w_1, w_2, w_3}, X = {x_1, x_2}, Y = {y_1, y_2, y_3} and Z = {z_1, z_2}. Given capacity…
  3. Q3Let G be a simple, undirected, unweighted graph. We use V(G) to denote the vertex set of G and E(G) to denote the edge …
  4. Q4Let G be a simple, undirected, unweighted graph. We use V(G) to denote the vertex set of G and E(G) to denote the edge …
  5. Q5There are N stones, numbered 1, 2, \ldots, N. For each (1 \leqslant i \leqslant N), the height of stone i is h_i. Assum…
  6. Q6There are N stones, numbered 1, 2, \ldots, N. For each (1 \leqslant i \leqslant N), the height of stone i is h_i. Assum…
  7. Q8There are N stones, numbered 1, 2, \ldots, N. For each (1 \leqslant i \leqslant N), the height of stone i is h_i. Assum…
  8. Q9Which of the following statements is true?\ Statement 1: For every graph G and every maximum flow on G, there always ex…
  9. Q10Figure question
  10. Q11Figure question
  11. Q12Consider the following definitions: A vertex cover is a subset S of V(G) such that for all (u,v) \in E(G), S \cap {u,v}…
  12. Q13Figure question
  13. Q14Figure question
  14. Q15Consider a different rounding strategy for the LP relaxation of the vertex cover problem. Instead of rounding up every …