\handout{Practice midterm,  originally planned for November 2, 2020}

\bigskip

\bigskip


\begin{trivlist}
\item[] NAME: \rule{2in}{\fboxrule}  \hfill UW Net ID: \rule{2in}{\fboxrule}


\item[] {\bf Instructions}: \\ \\
    \begin{minipage}{4in}
    \begin{itemize}
        \item Closed book, closed notes, no calculators
        \item Time limit:  50 minutes
        \item Answer the problems on the exam paper.
        \item If you need extra space use the back of a page
        \item Problems are not of equal difficulty, if you get stuck
              on a problem, move on.
    \end{itemize}
    \end{minipage}
\hfill\begin{tabular}{|r|r|}
    \hline
    1&\hspace*{.5in}/10\\ \hline
    2&/10\\ \hline
    3&/10\\ \hline
    4&/10\\ \hline
    5&/10\\ \hline
    6&/15\\ \hline
    7&/10\\ \hline
    Total&/75\\ \hline
\end{tabular}
\end{trivlist}

\endpage



\problem{1 Graph Theory (10 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.}.

\vfil


\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}

 


\vfil

\eject


\problem{2 Stable Matching (10 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}




\vfil
\eject


\problem{3 Shortest Cycle (10 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.
 

\vfil
\eject

\problem{4 Connected Components (10 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.
    \vfil
    \item[b)] What is the maximum number of connected components that $G$ can have?  Justify your answer.
\end{itemize}

\vfil
\eject

\problem{5 Interval Scheduling (10 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.

\vfil
\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}

\vfil
\eject




\problem{6 Recurrences (15 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.$$
	
	
	\vfil
	
	\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.$$
	
	
	\vfil
	
	\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}

\vfil

\eject

\problem{7 Dijkstra's Algorithm (10 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}
