\documentclass[11pt, a4paper, notitlepage, onecolumn, oneside, openany]{article}

\input{packages}
\input{layout}
\input{common_math}
\input{theorem_names_en}

\setlist[enumerate]{label={(\alph*)}, ref={(\alph*)}}
\setlist[description]{labelindent={2em}}


% Number algorithms under problems
\makeatletter
\renewcommand\thealgocf{%
  \theproblem.\arabic{algocf}}
\@addtoreset{algocf}{problem}
\makeatother


\title{%
  CMSC~28100-1 / MATH~28100-1\\
  Introduction to Complexity Theory\\
  Fall~2017 -- Homework~2
}
\author{\relax}
\date{\today}

\begin{document}
\maketitle

\begin{exercise}
  The \emph{Knapsack Problem} is defined as follows. The input is a set~$S$ of~$\lvert S\rvert = n$ items,
  each with a positive integer weight~$w_i$ and a non-negative value~$v_i$ ($i\in S$), a positive integer knapsack
  capacity~$W$, and a positive integer target total value~$V$. The output should be ``Yes'' if there is a
  subset~$S'\subseteq S$ of items such that~$\sum_{i\in S'}w_i\leq W$ and~$\sum_{i\in S'} v_i\geq V$ and
  should be ``No'' otherwise.

  \begin{enumerate}
  \item Give an algorithm for the Knapsack Problem. If you give a dynamic programming algorithm, state the
    precise ``English'' definitions of your sub-problems, state base cases, and the recurrence. Try to make it
    as efficient as you can. Prove its correctness and analyze its running time. Does it run in polynomial
    time?
    \label{it:knapalg}
  \item Define the~\emph{$\epsilon W$-Knapsack Problem} for a fixed constant~$\epsilon$ as the Knapsack
    Problem above, except that you have the guarantee that, in the input, we have~$\epsilon W\leq w_i$ for
    every~$i\in S$ (i.e., there are no arbitrarily small weights). Can you come up with a polynomial time
    algorithm for this problem? Or is your algorithm for part~\ref{it:knapalg} already polynomial time for
    this problem? Why? Analyze. (Note: the expected answer is short and~$\epsilon$ is \emph{not} part of the
    input.)
  \item Define the~\emph{$\epsilon V$-Knapsack Problem} for a fixed constant~$\epsilon$ as the Knapsack
    Problem above, except that you have the guarantee that, in the input, we have~$\epsilon V\leq v_i$ for
    every~$i\in S$ (i.e., there are no arbitrarily small values). Can you come up with a polynomial time
    algorithm for this problem? Why? Analyze. (Note: the expected answer is short and~$\epsilon$ is \emph{not}
    part of the input.)
  \end{enumerate}
\end{exercise}

\begin{exercise}
  We are given an array~$A[1..n]$ of~$n$ rational numbers with~$n\geq 3$ and the special property
  that~$A[1]\geq A[2]$ and~$A[n-1]\leq A[n]$. We say that an element~$A[x]$ is a \emph{local minimum of~$A$}
  if~$A[x-1]\geq A[x]$ and~$A[x]\leq A[x+1]$. First, note that, given the condition~$A[1]\geq A[2]$
  and~$A[n-1]\leq A[n]$, the array~$A$ must have at least one local minimum, and it is trivial to find it
  in~$O(b\cdot n)$ time, where~$b$ is the largest bitlength of an element of~$A$. Give an algorithm to find
  and return a local minimum of~$A$ in~$O(b\cdot(\log n)^2)$ time. Analyze the running time of your
  algorithm. Prove the correctness of your algorithm.
\end{exercise}

\begin{exercise}
  A \emph{cycle} in an undirected simple graph~$G = (V,E)$ is a sequence of vertices
  \begin{align*}
    (v_0,v_1,\ldots,v_k)
  \end{align*}
  with~$v_0 = v_k$, $k\geq 3$ and~$\{v_i,v_{i+1}\}\in E(G)$, $v_i\neq v_{i+1}$ and~$v_i\in V(G)$ for
  every~$i\in\{0,1,\ldots,k-1\}$.

  In this exercise, we consider that access to a graph~$G$ with vertex set~$V(G) = \{1,\ldots,n\}$ is given by
  the following subroutines.
  \begin{itemize}
  \item The subroutine~$\operatorname{vertices}()$ returns the number of vertices~$n$ in time~$O(\log n)$
    (which is the bitlength of~$n$).
  \item The subroutine~$\operatorname{nextneighbor}(i,j)$ returns the smallest~$k\geq j$ such that~$\{i,k\}\in
    E(G)$ and returns ``NONE'' if no such~$k$ exists. This subroutine also takes time~$O(\log n)$.
  \end{itemize}

  Design an algorithm that, using the subroutines above, runs in time~$O(n\log n)$ and returns a cycle of the
  graph~$G$ if one exists and returns ``ACYCLIC'' if~$G$ does not contain any cycle. Prove the correctness of
  your algorithm.

  Observation: the graph may have much more than~$O(n)$ edges (it can have up to~$\Omega(n^2)$ edges), so your
  algorithm cannot inspect all edges of the graph. Note also that your algorithm can only make at most~$O(n)$
  calls to the subroutines above.
\end{exercise}

\end{document}

%%  LocalWords:  vertices bitlength
