Consider the following greedy algorithm. Iterate through the jobs j = 1, 2, 3, . . . , n one by one. When considering job j, assign it to the machine that currently has the smallest load (breaking ties arbitrarily).

i. For the four-job instance (4 jobs with sizes 7, 8, 5, 6) , what would be an assignment of jobs to machines under this algorithm?

ii. What is the value of the makespan under this assignment?

iii. Consider the following statement: for every such job scheduling instance, this greedy algorithm computes a job assignment with makespan at most c times that of an optimal (minimum makespan) job assignment. Which of the following is the smallest choice of the constant c that makes this statement true?

A. 2 B. 4 C. 6/5 D. 3/2

iv. Now suppose that, prior to running the greedy algorithm in the previous part, we first sort the jobs from biggest to smallest. Consider the following statement: for every such job scheduling instance, the greedy algorithm (with this sorting preprocessing step) computes a job assignment with makespan at most c times that of an optimal (minimum-makespan) job assignment. Which of the following is the smallest choice of the constant c that makes this statement true?

A. 3/2 B. 4 C. 2 D. 6/5