$($a$)$ Apply the Ford$-$Fulkerson algorithm to find the maximum flow of the network in Figure $4.$ You

should show clearly the augmenting path and the resulting residual network after each step, and the

final maximum flow $($both the total value and the flow on each edge$).$

$($Note: you must draw the residual networks and you must use the same notations as in the lecture

notes. Any alternative notations, textual description of the network, or any textbased "drawings" will

not be accepted.$)$

Job Time window Length

Figure $4$: Flow network for Q$6($a$)($b$).$

$($b$)$ A student claims that the minimum cut of the network in Figure $4$ has value $22,$ because: $"$a

cut down the left $(sa,sb)$ has value $12+10=22,$ a cut down the right $(ct,$ dt$,$et$)$ has value $8+6+9=23,$

and a cut down the middle $6$ edges is clearly even worse." Is the student correct? Explain.

$($c$)$ A number of jobs are to be scheduled in a cloud computing server over a number of

timeslots. The time slots are numbered $1,2,3,$dots Each job can only be scheduled within a time

window $r,d$ meaning that it cannot be scheduled earlier than time slot $r$ or later than time slot $d.$

Each job has a length which is the number of time slots it needed to run. A job does not necessarily

need to be allocated its full length of time slots, and the time slots given to a job need not be

consecutive. Each time slot can accommodate at most one job.

For example, a job may have a schedulable window $3,7$ and length $2,$ meaning it requires up to $2$

time slots from time slots $3,4,5,6,7.$ It can be allocated time slots $3$ and $4$ ; or $4$ and $7$ ; or only $5$

$($which means it is only partially executed$)$; or many other possibilities.

The objective is to assign the jobs to the time slots so that the number of busy time slots $($those with

scheduled jobs$)$ is as large as possible.

The following table shows the details of the jobs: