%Do not change
\documentclass[12pt, oneside]{article}
\usepackage{amssymb,amsmath,amsthm}
\usepackage[margin=1in]{geometry}
\usepackage{textpos}
\usepackage{mathtools}
\usepackage{xspace}
\usepackage{enumitem}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}
\newcommand\myeq{\stackrel{\mathclap{\normalfont\mbox{?}}}{=}}
\newcommand\eq{\stackrel{\mathclap{\normalfont\mbox{def}}}{=}}
% You may add the packages you need here
\newcommand\rd{\textsuperscript{rd}\xspace}
\newcommand\nth{\textsuperscript{th}\xspace}
\renewcommand{\vec}[1]{\boldsymbol{\mathrm{#1}}}
\newif\iftemplate
%\templatefalse
\templatetrue
\usepackage{tikz}
\usetikzlibrary{arrows.meta}
\begin{document}
% Do not modify
%Do not modify other than putting your name, Purdue ID and names of collaborators where stated
\begin{textblock*}{30cm}(-1.7cm,-2.3cm)
\noindent {\large CS 381-Fall 2019} \\
\iftemplate
\noindent {\large Name: } \\
\noindent {\large Purdue ID: } \\
\noindent {\large Date: \today}
\fi
\end{textblock*}
\vspace{1cm}
%Do not modify other than typing the homework number after #
\begin{center}
\textbf{\Large Homework 6} \\
\textbf{Due Date: November 14, 2019 at 11:59PM on Gradescope.} \\
\textbf{Instructor: Jeremiah Blocki}\\
\end{center}
\subsection*{Homework Guideline Reminders}
\begin{itemize}
\item Assignments must be typed. Submit one pdf file to Gradescope by 11:59PM, or else late penalties will apply. The pdf file can include hand-drawn images of figures.
\item Each question needs to start with the resources and collaborator (RC) statement. You will not be penalized for using resources or having collaborators if your answers are expressed {\em entirely} in your own words. If you consulted no resources outside of course material or had no collaborators, you must state so. A question without a complete RC statement will not be graded.
\end{itemize}
\subsection*{Question 1: Where Are We Eating?}
Jane wants to have a dinner party with her $n-1$ friends, but they simply can't agree on a place to eat. Each person $i$ (including Jane) has a preferred restaurant $R[i]$ with a unique price $C[i]$. Let $G=(V, E)$ be a directed ``influence'' graph with $n$ nodes and $m$ edges. Each node in $G$ represents one of Jane or her friends, and a path from node $i$ to $j$ represents ``influence'' from person $i$ to person $j$. When casting his or her vote, person $j$ will consider voting for restaurant $R[i]$ if and only if person $j$ is influenced by person $i$ (note that person $j$ is influenced by his/her own preference) --- person $j$ will vote for the cheapest restaurant under consideration.
%
%Every person is willing to vote for their preferred restaurant, but additionally, if person $j$ is influenced by person $i$, then person $j$ is willing to vote for any restaurant at which person $i$ is willing to vote. Note that anybody with a path from $i$ will be influenced by $i$, not just the immediate neighbors of $i$.
At the final vote, every person will vote for the restaurant with the least price out of all of their willing restaurants. Consider the following example:
\begin{table}[H]
\centering
\begin{tabular}{|l|l|l|}
\hline
\textbf{Person} & \textbf{R} & \textbf{C} \\ \hline
Jane (J) & Dynamic Pizzeria & 8 \\ \hline
Elizabeth (E) & Gushing Gummy Bears & 20 \\ \hline
Lydia (L) & Greedy Grill & 16 \\ \hline
Charles (C) & Dinner \& Coffee & 14 \\ \hline
William (W) & Big O Bar & 12 \\ \hline
George (G) & NP Cafe & 10 \\ \hline
\end{tabular}
\end{table}
\begin{figure}[H]
\centering
\begin{tikzpicture}[xscale=2, yscale=1.5]
\node[draw, circle] (J) at (1, 0) {$J$};
\node[draw, circle] (E) at (-2, 0) {$E$};
\node[draw, circle] (L) at (2, 0) {$L$};
\node[draw, circle] (C) at (0, 0) {$C$};
\node[draw, circle] (W) at (-1, 0) {$W$};
\node[draw, circle] (G) at (-0.5, 1) {$G$};
\path [-{Latex[length=3mm]}] (E) edge (W);
\path [-{Latex[length=3mm]}] (W) edge (G);
\path [-{Latex[length=3mm]}] (G) edge (C);
\path [-{Latex[length=3mm]}] (C) edge (W);
\path [-{Latex[length=3mm]}] (C) edge (J);
\path [-{Latex[length=3mm]}] (J) edge (L);
\end{tikzpicture}
\caption{Influence Graph $G$}
\end{figure}
In this example, Elizabeth is not influenced by anybody, so she only considers voting for Gushing Gummy Bears. William, George, and Charles are all influenced by Elizabeth and each other, so they are each willing to consider four restaurants: Gushing Gummy Bears, Dinner \& Coffee, Big O Bar and NP Cafe. Since NP Cafe is the cheapest option of these four options William, George and Charles will all vote for NP Cafe. Jane is influenced by everybody else except Lydia, so she considers voting for every restaurant except Greedy Grill. Jane votes for her preference of Dynamic Pizzeria due to the price. Lydia is influenced by everybody and considers voting for all restaurants. She votes for Dynamic Pizzeria --- the cheapest restaurant. Hence, it can be determined that Gushing Gummy Bears will have 1 vote, NP Cafe will have 3 votes, Dynamic Pizzeria will have 2 votes, and all others have no votes, so the entire group will eat at NP Cafe.
Help Jane and her friends choose a place to eat by designing an efficient algorithm that determines the restaurant with the most votes (breaking ties arbitrarily). Briefly argue the correctness of your algorithm (no formal proof required). Analyze the time complexity of your algorithm. An $O(m+n)$ runtime solution is required for full credit, but sub-optimal solutions will be accepted for partial credit.
\iftemplate
\medskip
\noindent {\bf Resources: }
\\
\noindent {\bf Collaborators: }
\\
\noindent {\bf Solution: } \\
\else
% omit
\fi
\subsection*{Question 2: Max Flow Exercise}
A max-flow algorithm has been performed part-way to achieve the flow in the network shown below. Edges represent current capacity out of max capacity. To answer the following questions, you may include photographs of hand-drawn graphs.
\begin{figure}[H]
\centering
\begin{tikzpicture}[xscale=3.5, yscale=2.5]
\node[draw, circle] (s) at (-2, 0) {$S$};
\node[draw, circle] (a) at (-1, 1) {$A$};
\node[draw, circle] (b) at (-1, 0) {$B$};
\node[draw, circle] (c) at (-1, -1) {$C$};
\node[draw, circle] (d) at (0, 1) {$D$};
\node[draw, circle] (e) at (0, 0) {$E$};
\node[draw, circle] (f) at (0, -1) {$F$};
\node[draw, circle] (g) at (1, 1) {$G$};
\node[draw, circle] (h) at (1, 0) {$H$};
\node[draw, circle] (i) at (1, -1) {$I$};
\node[draw, circle] (t) at (2, 0) {$T$};
\path [-{Latex[length=2mm]}] (s) edge node [above left] {9/12} (a);
\path [-{Latex[length=2mm]}] (s) edge node [above] {4/4} (b);
\path [-{Latex[length=2mm]}] (s) edge node [above right] {7/15} (c);
\path [-{Latex[length=2mm]}] (a) edge node [above] {7/12} (d);
\path [-{Latex[length=2mm]}] (b) edge node [above] {6/6} (e);
\path [-{Latex[length=2mm]}] (c) edge node [below] {7/7} (f);
\path [-{Latex[length=2mm]}] (d) edge node [above] {7/10} (g);
\path [-{Latex[length=2mm]}] (e) edge node [above] {7/10} (h);
\path [-{Latex[length=2mm]}] (f) edge node [above] {6/6} (i);
\path [-{Latex[length=2mm]}] (g) edge node [above right] {7/7} (t);
\path [-{Latex[length=2mm]}] (h) edge node [above] {12/12} (t);
\path [-{Latex[length=2mm]}] (i) edge node [above left] {1/6} (t);
\path [-{Latex[length=2mm]}] (a) edge node [left] {2/2} (b);
\path [-{Latex[length=2mm]}] (d) edge node [above left] {0/4} (b);
\path [-{Latex[length=2mm]}] (b) edge node [below left] {0/2} (f);
\path [-{Latex[length=2mm]}] (e) edge node [right] {0/5} (d);
\path [-{Latex[length=2mm]}] (f) edge node [left] {1/5} (e);
\path [-{Latex[length=2mm]}] (h) edge node [above left] {0/8} (f);
\path [-{Latex[length=2mm]}] (h) edge node [left] {0/2} (g);
\path [-{Latex[length=2mm]}] (i) edge node [left] {5/5} (h);
\end{tikzpicture}
\end{figure}
\begin{enumerate}[label=\textbf{(\alph*)}]
\item Draw the residual graph for this flow network.
\item Run one iteration of Ford Fulkerson. Show the augmenting path and draw the flow network with the updated flow.
\item What is the partition of vertices for the minimum cut? Explain how you arrived at your answer.
\item What is the max-flow of this network?
\end{enumerate}
\iftemplate
\medskip
\noindent {\bf Resources: }
\\
\noindent {\bf Collaborators: }
\\
\noindent {\bf Solution: } \\
\else
% omit
\fi
\subsection*{Question 3: It's Party Time!}
Elizabeth is an event planner at Prof.\ Blocki's event management company. Christmas party season is right around the corner and Prof.\ Blocki is organizing $m$ parties. Since Prof.\ Blocki is very popular, Elizabeth has requests from $n$ people who wish to attend these parties.
For each person $i$ you are given the list of parties $P_i$ that $i$ is willing to attend. You are also given the maximum capacity of each party, $j$, denoted by $M_j$. Additionally, some of the attendees are married. You are given a list of couples, $C$, where if $\{a, b\}$ is in $C$, then person $a$ and person $b$ are married. Of course, marriage is symmetric (i.e. if $a$ is married to $b$, then $b$ is married to $a$), and each person is only married to at most one other person. Married attendees must avoid their spouse, otherwise they will get angry at each other's party habits, so a person will not attend a party that their spouse is attending. Each person has time to attend at most $2$ parties.
Devise an efficient algorithm to determine the maximum total attendance possible to all parties given the constraints. Briefly argue the correctness of your algorithm (no formal proof required). Analyze the time complexity of your algorithm.
\iftemplate
\medskip
\noindent {\bf Resources: }
\\
\noindent {\bf Collaborators: }
\\
\noindent {\bf Solution: } \\
\else
% omit
\fi
\subsection*{Question 4: Capacity Scaling Proof}
Let $G$ be a flow network with integral capacities $c(e) \geq 1$ on each edge $e$ and let $C = \max_{e} c(e)$ be the maximum capacity of any edge $e$ in the flow network. Let $v^*$ denote the value of the maximum flow.
In this question we will prove that the Capacity Scaling algorithm from lecture computes a maximum flow of value $v^*$ in polynomial time in $n$ and $\log C$.
\begin{enumerate}
\item Explain why the outer while loop repeats at most $1+\lceil \log_2 C\rceil$ times.
\item Suppose that the edge $e = (u,v)$ in $G$ has capacity $c(e)$ and let $f$ be any flow. Lower bound $f(e)$ in terms of $c(e)$ and $\Delta$ assuming that the edge $e$ does not appear in $G_f(\Delta)$. Upper bound $f(e)$ assuming that the reversed edge $(v,u)$ does not appear in $G_f(\Delta)$.
\item Let $f$ be a flow at the end of a scaling phase (i.e., such that $G_f(\Delta)$ has no augmenting path). Prove that $v^*\leq v(f) + m \Delta$. ({\bf Hint:} It may be useful to think about running a BFS in $G_f(\Delta)$).
\item Prove that each scaling phase ends after {\em at most} $O(m)$ augmentations. ({\bf Hint:} Try to lower bound the amount each augmentation increases the flow).
\item Upper bound the total running time of the Capacity scaling algorithm.
\end{enumerate}
\iftemplate
\medskip
\noindent {\bf Resources: }
\\
\noindent {\bf Collaborators: }
\\
\noindent {\bf Solution: } \\
\else
% omit
\fi
\end{document}