CSCI $270$ Homework $\backslash$#$7$

Due Date: Wednesday, November $20$th$,3$:$15$pm

$1.$ Let $\backslash ($ G$=($V$,$ E$)\backslash )$ be a flow network with source $\backslash ($ s$,\backslash$operatorname$\{$sink$\}$ t $\backslash ),$ and integer capacities. Suppose that we are given a maximum flow in $\backslash ($ G $\backslash ).$

$($a$)$ Suppose that we increase the capacity of a single edge $\backslash (($u$,$ v$)\backslash$in E $\backslash )$ by $1.$ Give an $\backslash ($ O$($V$+$E$)\backslash )-$time algorithm to update the maximum flow.

$($b$)$ Suppose that we decrease the capacity of a single edge $\backslash (($u$,$ v$)\backslash$in E $\backslash )$ by $1.$ Give an $\backslash ($ O$($V$+$E$)\backslash )-$time algorithm to update the maximum flow.

$2.$ At a dinner party, there are $\backslash ($ n $\backslash )$ families $\backslash ($ a$\_\{1\},$ a$\_\{2\},\backslash$cdots$,$ a$\_\{$n$\}\backslash )$ and $\backslash ($ m $\backslash )$ tables $\backslash ($ b$\_\{1\},$ b$\_\{2\},\backslash$cdots$,$ b$\_\{$m$\}\backslash ).$ The $\backslash ($ i$^\{\backslash$text $\{$th $\}\}\backslash )$ family $\backslash ($ a$\_\{$i$\}\backslash )$ has $\backslash ($ g$\_\{$i$\}\backslash )$ members and the $\backslash ($ j$^\{\backslash$text $\{$th $\}\}\backslash )$ table $\backslash ($ b$\_\{$j$\}\backslash )$ has $\backslash ($ h$\_\{$j$\}\backslash )$ seats. Everyone is interested in making new friends and the dinner party planner wants to seat people such that no two members of the same family are seated at the same table. Design a polynomial$-$time algorithm that decides if there exists a seating assignment such that everyone is seated and no two members of the same family are seated at the same table, and explain your answer.

$3.$ You must assign $\backslash ($ n $\backslash )$ students to $\backslash ($ m $\backslash )$ summer programs as evenly as possible. Each student has provided a list of programs he or she is willing to attend, and every program has at least one interested student. Ideally, the students would be evenly spread between the programs, so that no program takes more than $\backslash (\backslash$left$\backslash$lceil$\backslash$frac$\{$n$\}\{$m$\}\backslash$right$\backslash$rceil $\backslash )$ students. However, this will likely be impossible. Design a polynomial$-$time algorithm to find an assignment that minimizes the number of students assigned to the fullest program.

$4.$ On your homework assignment, you are asked to provide your first name, last name, and ID number. Unfortunately, each student only provided two of the three pieces of information on their latest homework. If only a name and ID are given, it is impossible to distinguish whether the name is a first name or a last name. If a first name and last name are given, the first name will always come first, followed by the last name.

Some students provided their information more than once on different homework assignments $($but not necessarily the same two pieces of information they provided before$).$ Some students may have submitted multiple times for the same assignment, and other students may not have submitted at all. Assume that no student gave contradictory information. It is guaranteed that the ID will be unique, but first name and last name are not necessarily unique.

Give a polynomial runtime algorithm to determine the minimum possible number of students enrolled in the class, and explain your reasoning.