% Instructions: you don't need to change anything in the macros, but
% feel free to define new commands as you wish. Starting from the main
% body, change the specs (e.g., your
% name). use \begin{solution} \end{solution} environment to write your
% solutions. Don't forget to list your collaborators.

\documentclass[12pt,answers]{exam}
%============Macros==================%
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\usepackage[margin=1in]{geometry}
%--------------Cosmetic----------------%
\usepackage{mathtools}
\usepackage{hyperref}
\usepackage{fullpage}
\usepackage{microtype}
\usepackage{xspace}
\usepackage[svgnames]{xcolor}
\usepackage[sc]{mathpazo}
\usepackage{enumitem}
\setlist[enumerate]{itemsep=1pt,topsep=2pt}
\setlist[itemize]{itemsep=1pt,topsep=2pt}
%----------Header--------------------%
\def\course{CS 584/684 Algorithm Design and Analysis}
\def\term{Portland State U, Winter 2021}
\def\prof{Lecturer: Fang Song}
\newcommand{\handout}[5]{
   \renewcommand{\thepage}{\arabic{page}}
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 5.78in { \hfill \large{\course} \hfill }
       \vspace{2mm}
       \hbox to 5.78in { {\Large \hfill \textbf{#5}  \hfill} }
       \vspace{2mm}
       \hbox to 5.78in { \term \hfill \emph{#2}}
       \hbox to 5.78in { {#3 \hfill \emph{#4}}}
      }
   }
   \end{center}
   \vspace*{4mm}
}
\newcommand{\hw}[4]{\handout{#1}{#2}{#3}{#4}{Homework #1}}

%-----defs and commands-----%
\def\veps{\varepsilon}
\newcommand{\bit}{\{0,1\}}
\newcommand{\negl}{\text{negl}}
\newcommand{\corr}[1]{{\color{blue}{#1}}}
\newcommand{\alg}[1]{\textsf{#1}}
%=======Main document==============%
\begin{document}

%----Specs: change accordingly-----%
\newif\ifstudent % comment out false
 \studenttrue 
% \studentfalse

\def\texbp{5} % bonus for typing in latex
\def\hwnum{4} %
\def\issuedate{01/26/21} % 
\def\duedate{02/02/21} % 
\def\yourname{your name} % type your name here

%------------------------------%
\ifstudent
\hw{\hwnum}{\issuedate}{Student: \yourname}{Due: \duedate}%
\else
\hw{\hwnum}{\issuedate}{\prof}{Due: \duedate}%
\fi

\noindent \textbf{Instructions.} This problem set contains \numpages\
pages (including this cover page) and \numquestions\ questions. A
random subset of problems will be graded.

\begin{itemize}
\item Your solutions will be graded on \emph{correctness} and
  \emph{clarity}. You should only submit work that you believe to be
  correct, and you will get significantly more partial credit if you
  clearly identify the gap(s) in your solution. It is good practice to
  start any long solution with an informal (but accurate) summary that
  describes the main idea. You may opt for the ``I take 15\%'' option.

\item You need to submit a PDF file before the deadline. Either a
  clear scan of you handwriting or a typeset document is accepted. You
  will get $\texbp$ bonus points for typing in LaTeX (Download and use
  the accompany TeX file).

\item You may collaborate with others on this problem set.  However,
  you must \textbf{{write up your own solutions}} and \textbf{{list
      your collaborators and any external sources}} for each
  problem. Be ready to explain your solutions orally to a course staff
  if asked.

\item For problems that require you to provide an algorithm, you must
  give a precise description of the algorithm, together with a proof
  of correctness and an analysis of its running time. You may use
  algorithms from class as subroutines. You may also use any facts
  that we proved in class or from the book.

\end{itemize}

\newpage

\begin{questions}

\question (Semi-connected graphs) A directed graph $G$ is
  \emph{semi-connected} if, for every pair of vertices $u$ and $v$,
  either $u$ is reachable from $v$ or $v$ is reachable from $u$ (or
  both).
  \begin{parts}
  \part[5] Give an example of a DAG with a unique source (a source is
    a vertex with no entering edges) that is \textbf{not}
    semi-connected.
  \part[10] Give an algorithm to determine whether a
    given DAG is semi-connected. 
    \part[10] 
      Give an algorithm to determine whether an
      arbitrary directed graph is semi-connected.
  \end{parts}

  \newpage
\def\scc{\text{SCC}}  
\question (Component graph) Given a directed graph $G=(V,E)$, we
  define another graph $G^{\scc} =(V^\scc, E^\scc)$ called the
  \emph{component graph} as follows. Suppose that $G$ has strongly
  connected components $C_1, C_2, \ldots, C_k$. The vertex set
  $V^\scc$ is $\{v_1,\ldots,v_k\}$ where $v_i\in C_i$. There is an
  edge $ (v_i,v_j) \in E^\scc$ if $G$ contains a directed edge
  $x\to y$ for some $x\in C_i$ and some $y\in C_j$. Alternatively,
  imagine contracting all edges whose incident vertices are within the
  same strongly connected component of $G$, and the resulting graph
  will be $G^\scc$.
  \begin{parts}
  \part[10] Prove or disprove that $G^\scc$ is a DAG.
    
    \bonuspart[10] Give an $O(|V|+|E|)$-time algorithm to compute the
    component graph of a directed graph $G = (V,E)$.
    
  \end{parts}

\newpage  
  \question[20] (Longest forward-backward contiguous substring) Describe
  and analyze an efficient algorithm to find the length of the longest
  \emph{contiguous} substring that appears both \emph{forward} and
  \emph{backward} in an input string $T[1,\ldots,n]$. The forward and
  backward substrings must NOT overlap.  Here are several examples.
  \begin{itemize}
  \item Given the input string \texttt{ALGORITHM}, your algorithm
    should return 0.

  \item Given the input string
    \texttt{\underline{R}ECU\underline{R}SION}, your algorithm should
    return 1, for the substring \texttt{R}.
  \item Given the input string
    \texttt{R\underline{EDI}V\underline{IDE}}, your algorithm should
    return 3, for the substring \texttt{EDI}. (The forward and backward
    substrings must not overlap!)
  \item Given the input string
    \texttt{D\underline{YNAM}ICPROGRAMMING\underline{MANY}TIMES}, your
    algorithm should return 4, for the substring \texttt{YNAM}. (It
    should not return 6, for the subsequence \texttt{YNAMIR}, because
    it's not contiguous.).
  \end{itemize}

\end{questions}


\end{document}
