Quiz Space

Advanced Algorithms · End Term · 24 Dec 2023 · September 2023 term · Set FDB1

Question 1: In one term of an academic program, we have n days. Stude…

Question 1

+2 marksNumerical answer

In one term of an academic program, we have nn days. Students have to earn at least PP credits during these nn days to remain in the program. There are two ways to earn points — completing practical tasks and attending lessons. For each task, a student earns TT points, and for each lesson, a student earns LL points.

Practical tasks are unlocked “each week” as the term goes on: the first task is unlocked on day 1 (and can be completed on any day from 1 to nn), the second task is unlocked on day 8 (and can be completed on any day from 8 to nn), the third task is unlocked on day 15, and so on.

Every day from 1 to nn, there is a lesson which can be attended by the students of the program. And every day, students choose whether to study or to rest the whole day. When a student decides to study, he or she attends a lesson and can complete no more than 2 tasks, which are already unlocked and not completed yet. If a student rests the whole day, he skips a lesson and ignores tasks.

Students naturally wants to have as many days off as possible, i. e. they want to maximize the number of rest days. Let's calculate this maximum.

As an example: if n=100,P=20,L=1n = 100, P = 20, L = 1 and T=10T = 10, then by studying only on day 42 we attend a lesson gives (1 point), and can solve 2 out of 6 available tasks to get another 20 points. This is necessary and sufficient, and leads to 99 rest days.

Based on the above data, answer the given subquestions.

Show answer

Correct answer: 0

Question 1 of 24 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) End Term paper sat on 24 Dec 2023, in the September 2023 term (IIT M DEGREE FN EXAM FDB1 24 Dec 2023). It carries 2 marks.

More questions from this paper

  1. Q2In one term of an academic program, we have n days. Students have to earn at least P credits during these n days to rem…
  2. Q3In one term of an academic program, we have n days. Students have to earn at least P credits during these n days to rem…
  3. Q4In one term of an academic program, we have n days. Students have to earn at least P credits during these n days to rem…
  4. Q5Figure question
  5. Q6Choose the correct options
  6. Q7Consider the following instance of Set Cover problem: Universe \mathcal{U} = {a, b, c} Family \mathcal{F} = {S_1 = {a, …
  7. Q8What is the answer if R = C = N and all the squares along a diagonal are cut out? In particular, assume the square at t…
  8. Q9What is the answer if R = C = N and all the squares on the topmost row and rightmost column (i.e, a L-shape) are cut ou…
  9. Q10Consider the following bipartite graph: the set A is composed of elements corresponding to every row of the board, whil…
  10. Q11What is the number of valid placements of N mutually non-attacking rooks if R = C = N and there are no cut out squares?…
  11. Q12Consider the following instance of Set Cover problem: Universe \mathcal{U} = {a, b, c, d} Family \mathcal{F} = \left{S_…
  12. Q13Consider the following instance of Set Cover problem: Universe \mathcal{U} = {a, b, c, d} Family \mathcal{F} = \left{S_…
  13. Q14The three-bonaci numbers are defined as follows (please read the definition carefully, as it may not be the generalizat…
  14. Q15The three-bonaci numbers are defined as follows (please read the definition carefully, as it may not be the generalizat…
  15. Q16The three-bonaci numbers are defined as follows (please read the definition carefully, as it may not be the generalizat…
  16. Q17In the MIN-2-SAT problem, we are given a 2-CNF formula \phi and an integer k, and the objective is to decide whether th…
  17. Q18Consider the given statements and answer if they are true or false. The worst-case running time and expected running ti…
  18. Q19Consider the given statements and answer if they are true or false.
  19. Q20Every linear program has a unique optimal solution.
  20. Q21Recall that in the vertex cover problem, we are trying to find a smallest subset S of vertices in a graph G such that G…
  21. Q22Consider the algorithm in the previous question. Does the algorithm always output an optimal vertex cover?
  22. Q23Consider the algorithm in the previous question. Does the algorithm always output a 2- approximate vertex cover?
  23. Q24Recall that the size of an optimal vertex cover is at most twice the size of a maximum matching of a graph G. Are there…