Quiz Space

Advanced Algorithms · End Term · 3 Sept 2023 · May 2023 term · Set QPE1-S2

Question 17: The memory of Bob's computer contains two interesting th…

Question 17

+2 marksNumerical answer

The memory of Bob's computer contains two interesting things: an array of integers and a virus. Each midnight the virus becomes active. It takes each array in memory and replaces it with a bunch of new arrays: one for each contiguous subarray of the original array.

For example, if today the memory contains a single array (1,2,1,3), tomorrow it will contain the following arrays: (1), (2), (1), (3), (1,2), (2, 1), (1, 3), (1,2,1), (2, 1,3), (1,2, 1, 3).

As another example, if today the memory contains a single array {(7,7)},tomorrow it will contain the following arrays: {(7), (7), (7,7)}, and the day after tomorrow it will contain the following arrays: {(7), (7), (7), (7), (7,7)}, and so on.

You are given Bob's original array A and the number of days D. Let f(A,D)f(A, D) be the sum of all elements of all arrays that will be in the memory of Bob's computer after D days. Our goal is to calculate f(A,D)f(A, D). You may assume that the memory of Bob's computer is sufficiently large to accommodate all the arrays.

Based on the above data, answer the given subquestions.

Show answer

Correct answer: 33

See the whole paperTake it as a mock test

Question 17 of 34 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) End Term paper sat on 3 Sept 2023, in the May 2023 term (IIT M DEGREE ET1 EXAM QPE1 S2 03 Sep). It carries 2 marks.

More questions from this paper

  1. Q1Recall the Dance Class problem: Problem Definition Dance Classes Input: A collection of n intervals given by their left…
  2. Q2Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible…
  3. Q3True or false?\ It is possible that Independent-Set is in P and the problem of checking a graph has a Hamiltonian Path …
  4. Q4Figure question
  5. Q5Raj and Lata both designed an algorithm for the same minimization problem. Raj proved that his algorithm Alg1 is a 2-ap…
  6. Q6Recall 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…
  7. Q7Figure question
  8. Q8Recall the Dance Class problem: Problem Definition Dance Classes Input: A collection of n intervals given by their left…
  9. Q9Recall the Stable Matching problem: Stable Matching Input: Two sets given by M = {m_1, \ldots, m_n} (the men) and W = {…
  10. Q10Is the collection of outgoing 1/2-factors over the set A a matroid?
  11. Q11Is the collection of incoming 1/2-factors over the set A a matroid?
  12. Q12Is the collection of 1-factors over the set A a matroid?
  13. Q13Can the collection of 1-factors be defined as the intersection of two matroids?
  14. Q14Based on the above data, answer the given subquestions.
  15. Q15The memory of Bob's computer contains two interesting things: an array of integers and a virus. Each midnight the virus…
  16. Q16The memory of Bob's computer contains two interesting things: an array of integers and a virus. Each midnight the virus…
  17. Q18The memory of Bob's computer contains two interesting things: an array of integers and a virus. Each midnight the virus…
  18. Q19The memory of Bob's computer contains two interesting things: an array of integers and a virus. Each midnight the virus…
  19. Q20Consider the network given below with source s and sink t, with the numbers on the edges denoting maximum capacity acro…
  20. Q21You are supposed to start at the top of a number triangle and chose your passage all the way down by selecting between …
  21. Q22Consider the following orientation problem. We are given an undirected graph G = (V, E) and integer values p(v) for eve…
  22. Q23Consider the network given below with source s and sink t, with the numbers on the edges denoting maximum capacity acro…
  23. Q24Consider the partially carefully properly 5-colored graph below. What color should we give the vertex in the center to …
  24. Q25Based on the above data, answer the given subquestions.
  25. Q26In the Uncapacitated Facility Location (UCFL) problem, we are given (\mathcal{F} \uplus \mathcal{D}, d) as well auxilia…
  26. Q27Consider the followed randomized algorithm, which prints out some number of smiley faces (:)) and some number of asteri…
  27. Q28Consider the followed randomized algorithm, which prints out some number of smiley faces (:)) and some number of asteri…
  28. Q29Consider the followed randomized algorithm, which prints out some number of smiley faces (:)) and some number of asteri…
  29. Q30Consider the followed randomized algorithm, which prints out some number of smiley faces (:)) and some number of asteri…
  30. Q31Based on the above data, answer the given subquestions.
  31. Q32Based on the above data, answer the given subquestions.
  32. Q33Based on the above data, answer the given subquestions.
  33. Q34Recall the Traveling Salesman Problem: Definition Traveling Salesman Problem Input: A set of distinct cities {c_1, c_2,…