Assignment # 2

CSC 373H1

Worth: 10%

1. [20 marks]

A hospital is scheduling doctors for work. The hospital has a desired number of doctors a1,…,an

that they would like to work on each of the next n days. Furthermore, each doctor who works at the

hospital has a list Aj ⊆ {1,…,n} of days when they would like to work.

(a) [5 marks]

You are given the numbers a1,…,an and the lists A1,…,Ak of the doctors’ availabilities. Using

this data, design an algorithm using network flow to output a schedule S1,…, Sk

for each doctor

such that

• Each doctor works only when they are available (i.e. Si ⊆ Ai

), and

• Exactly ai doctors work on day i

or the algorithm reports that no schedule is possible given the doctors’ availabilities.

(b) [5 marks]

Briefly justify correctness and runtime of the algorithm designed in part (a).

(c) [5 marks]

Due to COVID-19 scenario, the hospital finds that it may be necessary to schedule doctors for

times outside when they report they are available to work. They decide that doctors can be

scheduled for up to c days outside their availability list, for some integer c > 0. Modify the

algorithm designed in part (a) so a schedule S1,…, Sk

is produced with:

• Si containing at most c days not in Ai

, and

• Exactly ai doctors work on day i

or the algorithm reports that no such schedule is possible.

(d) [5 marks]

Briefly justify correctness and runtime of the modified algorithm designed in part (c).

2. [20 marks]

An edge in a flow network is called critical if decreasing the capacity of this edge reduces the

maximum possible flow in the network.

Give an efficient algorithm that finds a critical edge in a network. Give a rigorous argument that

your algorithm is correct and analyse its running time.

3. [20 marks]

(a) [8 marks]

Suppose we want to compute a shortest path from node s to node t in a directed graph G = (V ,E)

with integer edge weights `e > 0 for each e ∈ E.

Show that this is equivalent to finding a pseudo-flow f from s to t in G such that |f | = 1 and

P

e∈E

`e

f (e) is minimized. There are no capacity constraints.

Part of this problem requires you to define precisely what we mean by “pseudo-flow” in a

general, directed graph. This is a natural extension of the notion of flow in a network.

(b) [12 marks]

Write the shortest path problem as a linear or integer program where your objective function

is minimized, based on your answer to the previous part. Give a detailed justification that

your solution is correct.

1 Page 1 of 2

Dept. of Computer Science

University of Toronto

Assignment # 2

(Due July 17, 11:59 pm)

CSC 373H1

Summer 2021

4. [20 marks]

Linear programming is often used to solve statistical and machine learning problems. We consider

two examples here. We are given n data points (xi

,yi

) and wish to find a line of best fit y = ax + b

for some coefficients a,b that best approximates the behaviour of the data points. The `1 distance

between a point (xi

,yi

) and a line y = ax + b is defined as the quantity |yi − axi − b|.

(a) [10 marks]

Suppose we want to minimize the `1 error for the line of best fit, defined as minimum of the

sum of the `1 distances over the set of data points. Give a linear program that produces a line of

best fit with minimum `1 error.

(b) [10 marks]

In the classification problem, you are given m data points of type 1 and n data points of type 2.

We say that a line y = ax + b separates the points if all data points of type 1 satisfy yi < axi + b

and all data points of type 2 satisfy yi > axi +b. Give a linear program that determines if there is

a line that separates the points, and if one exists, maximizes the gap δ defined as min(e1, e2),

where ei

is the minimum `1 distance between the line and points of type i.

2 Page 2 of 2