<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">%\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{\problemset}[3]{
   \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{lecnum}{#1}
   \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 Problem Set #1  \hfill} }
       \vspace{2mm}
       \hbox to 6.28in { {\it Out: #2 \hfill Due: #3} }
      \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{##}$&amp;$\displaystyle{{}##}$\hfil
      \crcr#1\crcr}}\,}
\def\eqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &amp;$\displaystyle{{}##}$\hfil\tabskip\@centering
    &amp;\llap{$##$}\tabskip\z@skip\crcr
    #1\crcr}}
\def\leqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &amp;$\displaystyle{{}##}$\hfil\tabskip\@centering
    &amp;\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}
\problemset{1}{April 8}{\bf April 15}


Reminder: you are encouraged to work in groups of two or three;
however you must turn in your own write-up and note with whom you
worked. You may consult the course notes and the optional text (CLRS). The full honor code guidelines can be found in the course syllabus.


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.}
\begin{enumerate}


\item
\begin{enumerate}

\item Consider the following recurrence: $T(n) = 2\cdot T(n-1)$
  and $T(1) = 1$.  Here is a faulty proof that $T(n) \le
  O(n)$, by induction on $n$: the base case when $n = 1$ is easy, and
\[T(n) = 2\cdot T(n-1) =  O(T(n-1)) = O(n-1) = O(n)\]
where the third equality uses the induction hypothesis. Explain what
is wrong with this proof and give a correct solution to the
recurrence together with a correct proof.

\item Prove that any recurrence of the form: $T(n) = O(T(n/2)) + O(n)$
  and $T(1) = O(1)$, satisfies $T(n) \leq O(n^c)$ for some constant $c &gt; 0$. 
\end{enumerate}

\item
\begin{enumerate}
\item For a directed graph $G$, and a strongly-connected component of $G$, denote by $f(C)$ the {\em latest} finishing time for a given DFS traversal of $G$. Prove that if there is an edge from a vertex in strongly-connected component $C_1$ to a vertex in strongly-connected component $C_2$ (with $C_1 \ne C_2$), then $f(C_1) &gt; f(C_2)$.

\item Let $G_{\mbox{SCC}}$ denote the DAG whose nodes are the strongly-connected components of $G$, with an edge from component $C_1$ to component $C_2$ iff there is an edge in $G$ from a vertex of $C_1$ to a vertex of $C_2$.
Prove that a DFS traversal (Lecture 2, slide 12) of $G^T$ that selects vertices in line 3 by decreasing order of finishing times visits the strongly-connected components of $G^T_{\mbox{SCC}}$ in reverse topological order (i.e, the first component visited is a sink, and the next is a sink after the removal of the first component, etc...). This is the basis for the correctness of the algorithm from class for finding an SCC decomposition.

\item With all the ``reversals'' in the previous part, it is tempting
  to try to identify a SCC decomposition by having the second DFS
  operate on $G$ (rather than $G^T$), and select vertices in line 3 by
  {\em increasing} (rather than decreasing) order of finishing times. Prove that this does not work: specify a small directed graph  with two strongly-connected components, label them with discovery and finishing times for an initial DFS traversal, and show that the proposed second DFS produces a DFS forest with only one tree (instead of two, one covering each strongly connected component).

\item Give an $O(m + n)$ time algorithm to determine if a directed graph $G$ contains an odd length (simple, directed) cycle. Hint: start by considering a strongly connected graph. Consider a DFS traversal that labels vertices with ``odd'' or ``even'' discovery times.
\end{enumerate}


\item  Consider a {\em comparison-based} implementation of an $n$-element max-heap: just
  as with sorting, this means that the implementation only ever makes
  choices based on {\em comparisons} between key values. Let $f(n)$ be
  the worst-case time for a single {\sc
    insert} and let $g(n)$ be the worst-case time for a  single {\sc
    extract-max} operation. Prove that $f(n) + g(n) \ge \Omega(\log
  n)$.

\item Using the min-heaps from class with {\sc insert}, {\sc decrease-key}, and {\sc extract-min} operations all taking $O(\log n)$ time, Dijkstra's algorithm can be implemented to run in $O(m\log n)$ time. Give an alternative implementation of Dijkstra's algorithm that runs in time
    \[O \left (\frac{m \log n}{\log (m/n)} \right ).\]
Hint: Construct heaps from $d$-ary trees for $d &gt; 2$.

\item In a directed graph with non-negative weights, the {\em weight}
  of a path from $u$ to $v$ is the sum of the edges weights
  along the path. The {\em bottleneck weight} of a path from $u$ to
  $v$ is the {\em maximum} of the edge weights along the path. Give an
  algorithm to compute the smallest bottleneck-weighted paths from a
  source vertex $s$ to all other vertices, using a min-heap, with running
  time $O(n + m)$ plus the time for $n$ {\sc insert} operations, $m$ {\sc decrease-key} operations, and  $n$ {\sc extract-min} operations.



\end{enumerate}

\end{document}
</pre></body></html>