\documentclass[11pt]{article}
\usepackage{handout2e}
\usepackage{algorithmic}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\newcommand{\Infected}{\mbox{{\sc Infected}}}
\newcommand{\InfTime}{\mbox{{\sc InfTime}}}
\newcommand{\InfBy}{\mbox{{\sc InfBy}}}
\newcommand{\fuel}{\mbox{fuel}}
\newcommand{\dist}{\mbox{dist}}

\head{CS5800}{Algorithms}{Spring 2011}{5 March 2011}{12}

\begin{center}
\Large{\bf Some Practice Problems for Midterm}
\end{center}

{\bf 1.} Derive an asymptotically tight bound for the following
recurrence.  Assume that $T(n)$ is $\Theta(1)$ for $n\le 4$.

\[ T(n) = T(n/2) + T(3n/4) + n^2.\]

{\bf 2.} Problem 1.42 of text.

{\bf 3.}  A {\em hamiltonian path}\/ of a directed graph $G$ is a
simple path in $G$ that visits every vertex in $G$ exactly once.

Design a linear time algorithm to determine whether a given directed
acyclic graph has a hamiltonian path.


{\bf 4.} For each of the following claims, indicate whether it is true
or false.  Briefly justify your answers.
\begin{itemize}
\item[{\bf (a)}]  If $T$ is a minimum spanning tree of a weighted undirected graph $G$,
then the minimum-weight edge of $T$ is also a minimum-weight edge of
$G$.

\vfill

\item[{\bf (b)}]  Let $G$ be a given weighted undirected graph.
Let $T_1$ and $T_2$ be two minimum spanning trees of $G$ that differ
in only one edge.  Let $e_1$ be the edge in $T_1$ that is not in $T_2$
and $e_2$ be the edge in $T_2$ that is not in $T_1$.  Prove or
disprove the following statement: The cycle obtained when $e_1$ is
added to $T_2$ contains $e_2$.

\vfill

\item[{\bf (c)}] Let $G$ be a weighted directed graph and $s$ be a
  vertex in $G$.  Let $p$ denote a shortest path from $s$ to $t$.  If
  we increase the weight of every edge in the graph by $1$, then $p$
  remains a shortest path from $s$ to $t$.  
  
  \vfill
\end{itemize}

{\bf 5.} Problem 4.21 (a) of text.

\end{document}