%\documentstyle[10pt,twoside]{article}
\documentstyle[twoside, 11pt]{article}
\setlength{\oddsidemargin}{0.25 in}
\setlength{\evensidemargin}{-0.25 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}



%
% The following commands sets up the lecnum (lecture number)
% counter and make various numbering schemes work relative
% to the lecture number.
%
\newcounter{lecnum}
\renewcommand{\thepage}{\thelecnum-\arabic{page}}
\renewcommand{\thesection}{\thelecnum.\arabic{section}}
\renewcommand{\theequation}{\thelecnum.\arabic{equation}}
\renewcommand{\thefigure}{\thelecnum.\arabic{figure}}
\renewcommand{\thetable}{\thelecnum.\arabic{table}}

%
% The following macro is used to generate the header.
%
\newcommand{\midterm}[2]{
   \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{lecnum}{0}
   \setcounter{page}{1}
   \noindent
   \begin{center}
   \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.28in { {\bf CS~38~~~Introduction to Algorithms
                        \hfill Spring 2014} }
       \vspace{4mm}
       \hbox to 6.28in { {\Large \hfill Midterm  \hfill} }
       \vspace{2mm}
       \hbox to 6.28in { {\it Out: #1 \hfill Due: #2} }
      \vspace{2mm}}
   }
   \end{center}
   \vspace*{4mm}
}
%
% Convention for citations is authors' initials followed by the year.
% For example, to cite a paper by Leighton and Maggs you would type
% \cite{LM89}, and to cite a paper by Strassen you would type \cite{S69}.
% (To avoid bibliography problems, for now we redefine the \cite command.)
%
\renewcommand{\cite}[1]{[#1]}

\input{epsf}

%Use this command for a figure; it puts a figure in wherever you want it.
%usage: \fig{NUMBER}{FIGURE-SIZE}{CAPTION}{FILENAME}
\newcommand{\fig}[4]{
            \vspace{0.2 in}
            \setlength{\epsfxsize}{#2}
            \centerline{\epsfbox{#4}}
            \begin{center}
            Figure \thelecnum.#1:~#3
            \end{center}
    }

% Use these for theorems, lemmas, proofs, etc.
\newtheorem{theorem}{Theorem}[lecnum]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}}

% Some useful equation alignment commands, borrowed from TeX
\makeatletter
\def\eqalign#1{\,\vcenter{\openup\jot\m@th
  \ialign{\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
      \crcr#1\crcr}}\,}
\def\eqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &$\displaystyle{{}##}$\hfil\tabskip\@centering
    &\llap{$##$}\tabskip\z@skip\crcr
    #1\crcr}}
\def\leqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &$\displaystyle{{}##}$\hfil\tabskip\@centering
    &\kern-\displaywidth\rlap{$##$}\tabskip\displaywidth\crcr
    #1\crcr}}
\makeatother

% **** IF YOU WANT TO DEFINE ADDITIONAL MACROS FOR YOURSELF, PUT THEM
% HERE:


\newcommand{\set}[1]{\left \{{#1} \right \}}

\begin{document}
\midterm{April 29}{\bf May 6}


{\bf This is a midterm.} You may consult only the course notes and
the optional text (CLRS). {\em You may not collaborate.} The full honor code guidelines can be found in the course syllabus.


There are 5 problems
on 2 pages. Please attempt all problems. {\bf To facilitate
grading, please turn in each problem on a separate sheet of paper
and put your name on each sheet. Do not staple the separate
sheets.} Good luck!
\begin{enumerate}
\item Given an undirected graph $G = (V, E)$ in adjacency list format, we are interested in determining whether or not it contains a triangle; i.e., three vertices $a,b,c$ for which $(a,b), (b,c)$, and $(a,c)$ are all edges.
\begin{enumerate}
\item One idea is to use a BFS traversal, and when we are currently at vertex $u$, if we see an edge $(u,v)$ to an already-explored vertex $v$, we say there is a triangle if the predecessor of $u$ in the BSF tree and the predecessor of $v$ in the BFS tree are the same. Give a small counterexample showing that this idea fails.
\item Give an algorithm that runs in time $O(n^{\alpha})$ for some constant $\alpha < 3$. Hint: the intended solution requires you to work with the adjacency {\em matrix} $A$ of the graph. What does entry $(i,j)$ of $A^2$ tell you?
\end{enumerate}

\item Given a weighted, connected, undirected graph $G = (V,E)$ and a subset $F \subseteq E$ of ``mandatory edges'', design an algorithm to find the spanning tree of $G$ that contains $F$, of minimum cost among all such trees. Do this via the following two steps.
\begin{enumerate}
\item Show that for a matroid ${\mathcal I}$ on universe $E$, and an element $e \in E$, the set system on $E' = E \setminus \{e\}$ defined by
\[{\mathcal I}' = \{A : (A \cup \{e\}) \in {\mathcal I}\}\]
is a matroid.
\item Argue that the subsets of $G$'s edges that, together with $F$, form spanning trees, constitute the bases of a matroid. Show that you can find the minimum cost such tree in time $O(m \log m)$ by assigning weights and implementing the greedy algorithm to find a maximum weight independent set in this matroid.
\end{enumerate}

\item Given three lists of integers $a_1, a_2, \ldots, a_n$, $b_1, b_2, \ldots, b_n$, and $c_1, c_2, \ldots c_n$, we are interested in determining whether there exist $i,j,k$ such that $a_i + b_j + c_k = 0$.
\begin{enumerate}
\item Show how to solve this problem using $O(n^2\log n)$ operations (you may count a comparison or addition operation between two integers from the lists and copying/moving an integer from the lists to be single operations, even though the integers may be large).
\item Suppose we know that all of the integers lie in the range $[-M, M]$. Show how to solve this problem using $O(M \log M)$ operations.
\end{enumerate}
Hint: for both parts, use binary search; for the second part, use, in addition, fast polynomial multiplication. Given a set $S$, your polynomials will have the form $f(X) = \sum_{i \in S}X^i$.

\item Given $n$ points in the plane, we want to find the lightest triangle, i.e., the triple of points $a,b,c$ such that $d(a,b) + d(b,c) + d(c,a)$ is minimum, where $d(\cdot, \cdot)$ is the Euclidian distance function. Give a divide-and-conquer algorithm for this problem that runs in time $O(n \log^2 n)$.


\item Given a directed graph, a Hamilton cycle in $G$ is a cycle that visits every vertex exactly once. You may recall that the problem of finding a Hamilton cycle is NP-complete, so we do not expect a polynomial time solution. The brute-force algorithm which tries all orderings of the $n$ vertices takes $n!$ time.

    Give a dynamic programming algorithm that decides if $G$ contains a Hamilton cycle, and that runs in time $O(n^22^n)$ (this time bound is much better than $O(n!)$). Hint: your dynamic programming table will be indexed by pairs $(S, v)$ where $S$ is a subset of vertices, and $v$ is a vertex. Subproblem $(S,v)$ is to determine if there is a path starting at vertex $x$ (a fixed vertex) and passing through all of $S$, ending at $v$.
\end{enumerate}

\end{document}

