\bigskip
\handout{Homework 5,  Due Wednesday, November 4, 1:30 pm,  2020}
\bigskip

\bigskip

Turn in instructions:  Electronic submission on GradeScope.   Submit as a PDF,  with each problem on a separate page.  While we have encouraged typeset solutions (e.g.,  Word or LaTex) in the homework,  it is probably easiest to hand write solutions for the practice midterm exam (as the midterm was designed for pen and paper).  

\bigskip
This homework assignment has two parts - a programming component (Dijkstra!) and a sample midterm.  For the sample midterm,  you are strongly encouraged to take the midterm under exam conditions - closed book, 50 minutes,  to see how you perform on the questions as an assessment.  After you have completed the practice midterm,  you may take a second pass over the exam with additional time and resources to write up solutions to turn in.

\bigskip
The midterm questions are questions 1-7, and programming questions are 8-10.  A separate copy of the midterm is also available for download to use in a sample exam setting.  Problem number 6 requires material from Friday's lecture.  (The schedule slipped by a lecture.)

\problem{1 Graph Theory (5 points)}


\begin{itemize}
\item[a)] {\it True or false}:  Let $G=(V,E)$ be an undirected graph. If $G$ is a tree, then $G$ is bipartite.
Justify your answer\footnote{``Justify'' means give a short and convincing explanation.  Depending on the situation, justifications can involve counter examples, or cite results established in the text or in lecture.}.




\item[b)] {\it True or false}:  Let $G=(V,E)$ be a directed graph with $n$ vertices and $m$ edges.  It is possible to determine if $G$ has a cycle in $O(n+m)$ time. Justify your answer.
\end{itemize}

 




\problem{2 Stable Matching (5 points)}
Step through the Gale-Shapely stable matching algorithm on the instance below.  (You may choose the proposals in any order.)  The preference lists are:
$$
M=\begin{bmatrix}
m_1:&w_1&w_2&w_3&w_4\\
m_2:&w_1&w_3&w_4&w_2\\
m_3:&w_2&w_1&w_3&w_4\\
m_4:&w_2&w_1&w_3&w_4\\
\end{bmatrix}
$$

$$
W=\begin{bmatrix}
w_1:&m_3&m_4&m_1&m_2\\
w_2:&m_1&m_2&m_4&m_3\\
w_3:&m_3&m_4&m_1&m_2\\
w_4:&m_1&m_2&m_3&m_4\\
\end{bmatrix}
$$

\bigskip
Fill in the following table to trace the algorithm.    The first two rows are given.

\bigskip


\begin{tabular}{|c|r|r|r|}
    \hline
    Round&\hspace*{1in}Proposal&\hspace*{1in}Result&\hspace*{1.2in}Current Matching\\ \hline
    \rule{0pt}{20pt}0&&&$(m_1,*), (m_2,*), (m_3,*), (m_4,*)$\\ \hline
    \rule{0pt}{20pt}1&$m_1$ proposes to $w_1$&$w_1$ accepts $m_1$&$(m_1,w_1), (m_2,*), (m_3,*), (m_4,*)$\\ \hline
    \rule{0pt}{20pt}2&$m_2$ proposes to $w_1$&$w_1$ rejects $m_2$&$(m_1,w_1) ,(m_2,*), (m_3,*), (m_4,*)$\\ \hline
    \rule{0pt}{20pt}3&&&\\ \hline
    \rule{0pt}{20pt}4&&&\\ \hline
    \rule{0pt}{20pt}5&&&\\ \hline
    \rule{0pt}{20pt}6&&&\\ \hline
    \rule{0pt}{20pt}7&&&\\ \hline
    \rule{0pt}{20pt}8&&&\\ \hline
    \rule{0pt}{20pt}9&&&\\ \hline
    \rule{0pt}{20pt}10&&&\\ \hline
    \rule{0pt}{20pt}11&&&\\ \hline
    \rule{0pt}{20pt}12&&&\\ \hline
\end{tabular}






\problem{3 Shortest Cycle (5 points)}  
Let $G=(V,E)$ be an undirected graph.  Let $e = \{u,v\}$ be an edge in $G$.  Give an $O(n+m)$ time algorithm that finds the shortest cycle in $G$ which contains the edge $e$.    Explain why your algorithm is correct.
 



\problem{4 Connected Components (5 points)}
Suppose $G=(V,E)$ is an undirected graph with $n$ vertices and $n$ edges.  (Note:  $G$ is not allowed to have self loops or parallel edges.)

\begin{itemize}
    \item[a)] What is the minimum number of connected components that $G$ can have?  Justify your answer.
    \item[b)] What is the maximum number of connected components that $G$ can have?  Justify your answer.
\end{itemize}



\problem{5 Interval Scheduling (5 points)}  
The input for an interval scheduling problem is a set of intervals $I = \{i_1,\ldots, i_n\}$ where $i_k$ has start time $s_k$, and finish time $f_k$.  The problem is to find a set of non-overlapping intervals that satisfies a given criteria.    
\bigskip

\begin{itemize}
    \item [a)]Suppose that you want to maximize the total length of the selected intervals.  {\it True or false}:  The greedy algorithm based on selecting intervals in order of decreasing length finds an optimal solution.  Justify your answer.


\item [b)]Suppose that all intervals have the same length, and you want to maximize the total length of the selected intervals.  {\it True or false}:  The greedy algorithm based on selecting intervals in order of increasing start time finds an optimal solution.  Justify your answer.

\end{itemize}






\problem{6 Recurrences (5 points)}  
Solve the following recurrences by unrolling the recursion tree.  Express your answers as $O(f(n))$.



\begin{itemize}
	
	\item[a)] $$T(n) =  \left\{\begin{array}{ll} 
	5T({n\over 3}) + n &\mbox{if $n>1$}\\
	1 & \mbox{if $n\le 1$}
	\end{array} \right.$$
	
	

	
	\item[b)] $$T(n) =  \left\{\begin{array}{ll} 
	T({4n\over 5}) + n &\mbox{if $n>1$}\\
	1 & \mbox{if $n\le 1$}
	\end{array} \right.$$
	
	

	
	\item[c)] $$T(n) =  \left\{\begin{array}{ll} 
	16T({n\over 4}) + n^2 &\mbox{if $n>1$}\\
	1 & \mbox{if $n\le 1$}
	\end{array} \right.$$

\end{itemize}




\problem{7 Dijkstra's Algorithm (5 points)} 

Use the following graph to simulate versions of Dijkstra's algorithm in parts a) and c) starting from the vertex $s$.

\begin{center}
	\def\bb{\makebox(0,0){$\bullet$}}
	\setlength{\unitlength}{0.25in}
	\begin{picture}(16,9)
	\put(0,4){\bb}
	\put(4,0){\bb}
	\put(4,8){\bb}
	\put(12,0){\bb}
	\put(12,8){\bb}
	\put(16,4){\bb}
	\put(0,4){\vector(1,1){3.9}}
	\put(0,4){\vector(1,-1){3.9}}
	\put(0,4){\vector(3,-1){11.9}}	
	\put(4,0){\vector(1,0){7.9}}
	\put(4,8){\vector(0,-1){7.9}}
	\put(4,8){\vector(1,0){7.9}}
	\put(4,8){\vector(3,-1){11.9}}
	\put(12,0){\vector(0,1){7.9}}
	\put(12,8){\vector(1,-1){3.9}}
	\put(12,0){\vector(1,1){3.9}}
	\put(-0.3,4){\makebox(0,0){$s$}}
	\put(4,8.4){\makebox(0,0){$a$}}
	\put(12,8.4){\makebox(0,0){$c$}}
	\put(16.4,4){\makebox(0,0){$e$}}
	\put(4,-0.4){\makebox(0,0){$b$}}
	\put(12,-0.4){\makebox(0,0){$d$}}
	\put(1.7,1.7){\makebox(0,0){$4$}}
	\put(1.7,6.3){\makebox(0,0){$2$}}
	\put(4.3,4){\makebox(0,0){$1$}}
	\put(8,1.8){\makebox(0,0){$7$}}
	\put(8,8.4){\makebox(0,0){$6$}}
	\put(8,6.2){\makebox(0,0){$9$}}
	\put(14.2,6.2){\makebox(0,0){$5$}}
	\put(8,-0.4){\makebox(0,0){$3$}}
	\put(12.3,4){\makebox(0,0){$4$}}	
	\put(14.2,1.8){\makebox(0,0){$3$}}
	\end{picture}
\end{center}


\begin{itemize}
	\item[a)] Simulate Dijkstra's shortest path algorithm on the graph above by filling in the table.
	  The entries should contain the preliminary distance values. 
	  
	\begin{center}
	\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
		\hline
		Round\rule{0pt}{.22in}&Vertex&$s$&$a$&$b$&$c$&$d$&$e$\\ \hline
		1\rule{0pt}{.22in}&&\hspace*{.22in}&\hspace*{.22in}&\hspace*{.22in}&\hspace*{.22in}&\hspace*{.22in}&\hspace*{.22in} \\\hline
		2\rule{0pt}{.22in}&&&&&&& \\\hline
		3\rule{0pt}{.22in}&&&&&&& \\\hline
		4\rule{0pt}{.22in}&&&&&&& \\\hline
		5\rule{0pt}{.22in}&&&&&&& \\\hline
		6\rule{0pt}{.22in}&&&&&&& \\\hline

	\end{tabular}
\end{center}

	\item[b)] Draw the back edges found by your simulation of Dijkstra's algorithm.
	
	\begin{center}
		\def\bb{\makebox(0,0){$\bullet$}}
		\setlength{\unitlength}{0.25in}
		\begin{picture}(16,9)
		\put(0,4){\bb}
		\put(4,0){\bb}
		\put(4,8){\bb}
		\put(12,0){\bb}
		\put(12,8){\bb}
		\put(16,4){\bb}
		\put(0,4){\vector(1,1){3.9}}
		\put(0,4){\vector(1,-1){3.9}}
		\put(0,4){\vector(3,-1){11.9}}	
		\put(4,0){\vector(1,0){7.9}}
		\put(4,8){\vector(0,-1){7.9}}
		\put(4,8){\vector(1,0){7.9}}
		\put(4,8){\vector(3,-1){11.9}}
		\put(12,0){\vector(0,1){7.9}}
		\put(12,8){\vector(1,-1){3.9}}
		\put(12,0){\vector(1,1){3.9}}
		\put(-0.3,4){\makebox(0,0){$s$}}
		\put(4,8.4){\makebox(0,0){$a$}}
		\put(12,8.4){\makebox(0,0){$c$}}
		\put(16.4,4){\makebox(0,0){$e$}}
		\put(4,-0.4){\makebox(0,0){$b$}}
		\put(12,-0.4){\makebox(0,0){$d$}}
		\end{picture}
	\end{center}


\end{itemize}

\problem{8 Grid graph generator (5 points)}  The purpose of this problem is to construct a random graph generator that should be interesting for shortest path's algorithms. An $n \times n$ directed grid graph has the vertex set $$V=\{ \langle i,j \rangle \mid 1\le i \le n \mbox{ and } 1 \le j \le n \} $$ and edge set
$$E=\{ (\langle i,j \rangle, \langle i+1,j \rangle)  \mid 1\le i \le n-1 \mbox{ and } 1 \le j \le n \} \cup 
\{ (\langle i,j \rangle, \langle i,j+1 \rangle)  \mid 1\le i \le n \mbox{ and } 1 \le j \le n-1 \}.$$

The base graph, for a given $n$ is an $n\times n$ grid graphs.  The edge costs are random real (or floating point) numbers $x$ chosen uniformly in the range $0\le x < 1$.

For this problem, create the generator,  and print an example random grid graph for $n=4$.  It is sufficient to print out a list of edges (and costs) that the graph has.


\problem{9 Dijkstra's Shortest Path Algorithm Implementation (10 points)}
Implement Dijkstra's Shortest Path algorithm and run the algorithm on the grid graph from problem 8.  The starting vertex is $s = \langle 1, 1 \rangle$ and you are interested in finding the distance to $t= \langle n, n \rangle$.
For running your algorithm,  you may use $n=100$ (although you could probably use a much larger value of $n$, maybe as large as $n=10,000$).
Run your algorithm for a number of runs (say 10) to compute the average distance between $s$ and $t$.   Before you run your algorithm,  you may want to estimate what the distance should be.


\problem{10 Dijkstra's Bottleneck Path Algorithm (10 points)}
Same as problem 9,  but implement the algorithm to compute the bottleneck path distance.
