Boston Public Schools has a mechanism for assigning incoming freshmen to high schools throughout the city. I have no ide

[answerhappygod]

Boston Public Schools has a mechanism for assigning incoming
freshmen to high schools throughout the city. I have no idea
how it works, so let’s assume the following.
There are F incoming freshmen and H high schools in
Boston. Each student has a set of schools they are interested
in attending. We will let Si be the set of
schools that student i is interested in (1 ≤ i ≤ F). Note that the
cardinalities of the Si ’s may not all be the same, but
they’re all non-empty.
Similarly, each school has a set of students they would like to
attend their school. We will let Tj be the set of students
that school j would like to attend their school (1 ≤ j ≤ H). We’ll
assume that each school could take on 150 students, but they
don’t necessarily need to fill all slots.
We would like to determine if there is a way to assign every
student to a school such that all constraints are
met. More precisely, we have the following inputs and desired
outputs:
• Input: The values F, H, S1, . . . , SF , T1, . . . , TH .
• Output: If possible, an assignment of students to schools such
that (1) every student is assigned, (2) every school is assigned at
most 150 students, (3) every student assigned to school j is
from the set Tj , and (4) the school that student i is assigned to
is in set Si .
Otherwise, ⊥ meaning that no such assignment is possible.
Show how to obtain a polynomial time algorithm for this problem
by using the integer maximum flow problem that we know how to
solve. Your algorithm should do the following (1) build a flow
network, (2) solve for the max flow on your flow network, (3) use
the resulting flow to determine if an assignment exists.
(a) How would you build a flow network from the inputs given
above? If you had a flow, what would the flow value on each edge
represent?
(b) Suppose you’ve used Ford-Fulkerson to solve MAXFLOW on the
graph from part (a).Which flow value(s) would correspond to a
desired student assignment existing (the “yes range”)? Which flow
value(s) correspond to no assignment existing (the “no range”)?
In the case where a desired assignment exists, how would you
find the assignment from the max flow? Argue why every
possible flow value is in either the yes range or no range.