Quiz Space

Advanced Algorithms · Quiz 1 · 16 Jul 2023 · May 2023 term

Question 7: We have a set of jobs to be performed, and we are given t…

Question 7

+4 marksNumerical answer

We have a set of jobs to be performed, and we are given the following information about each job: a job ID, the duration required to complete the job, and the time by which the job is due. All jobs have to be performed on a single machine, which can perform one job at a time. Given a schedule for the jobs, the lateness of a job is defined as 0 if it is completed before it is due, and is defined as the difference between the completion time and the time it is due otherwise. This machine has to rest for an hour mandatorily after every 5 hours of continuous work but the machine can take rest for one hour even before 5 hours.
If the jobs are executed in an optimal sequence, what is the total lateness?

Lateness=∑id=03L(i)Lateness = \sum_{id=0}^{3} L(i)

L(i)={if TimeDelivered(i)>TimeDue(i), TimeDelivered(i)−TimeDue(i)else,0}L(i) = \left\{\begin{matrix} if\ TimeDelivered(i) > TimeDue(i),\ TimeDelivered(i) - TimeDue(i) \\ else, 0 \end{matrix}\right\}

IdTime requiredDue time
0210
112
248
337
Show answer

Correct answer: 3

Question 7 of 16 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) Quiz 1 paper sat on 16 Jul 2023, in the May 2023 term (IIT M DEGREE AN2 EXAM QPE2 16 JULY 2023). It carries 4 marks.

More questions from this paper

  1. Q1Figure question
  2. Q2A circuit in a matroid is a minimal dependent set. In other words, a subset S of the universe U is a circuit if S is no…
  3. Q3Consider the following set system:\ ● The universe is the set of edges of a graph G\ ● A subset S of U is an independen…
  4. Q4Suppose there are M mice out on a field and there are H holes scattered across the ground that the mice can hide in. Ea…
  5. Q5Let L be an array of n integers. Our array indices start from 0.\ Let maxSum[i] denote the largest contiguous sum possi…
  6. Q6Recall the task scheduling problem: suppose you have n tasks to complete in n days; each task requires your attention f…
  7. Q8Consider the following tree: What is the size of the maximum-size independent set for this tree?
  8. Q9Consider the following instance of the stable matching problem. Suppose there are 3 women (A, B, C) and 3 men (X, Y, Z)…
  9. Q10Consider the following instance of the stable matching problem. Suppose there are 3 women (A, B, C) and 3 men (X, Y, Z)…
  10. Q11What is the value of f(6)?
  11. Q12Which of the following is a valid recurrence for f(n)?
  12. Q13You have a collection of n elements with weights, which may be positive or negative numbers (but never zero). You want …
  13. Q14You have a collection of n elements with weights, which may be positive or negative numbers (but never zero). You want …
  14. Q15You have a collection of n elements with weights, which may be positive or negative numbers (but never zero). You want …
  15. Q16You have a collection of n elements with weights, which may be positive or negative numbers (but never zero). You want …