Comprehensive Final Exam

\documentclass[11pt,addpoints]{exam}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{xcolor}
\usepackage[hidelinks]{hyperref}

\lstset{basicstyle=\ttfamily\footnotesize,frame=single,breaklines=true}

\pagestyle{headandfoot}
\header{CS 410 Final Exam}{Spring Semester}{Page \thepage\ of \numpages}
\footer{}{}{\iflastpage{End of exam.}{Continue.}}

\begin{document}

\begin{center}
  {\LARGE\bfseries CS 410 -- Final Examination}\\[0.3em]
  {\large Duration: 3 hours \;\;--\;\; Total points: \numpoints}
\end{center}

\vspace{1em}
\noindent\textbf{Name:}~\hrulefill\quad\textbf{ID:}~\hrulefill

\vspace{0.5em}
\begin{itemize}
  \item Closed book.
  \item Write clearly. Show all work.
  \item You have 3 hours. Budget your time.
\end{itemize}

\begin{questions}

\question[20] \textbf{Short Answer.}
\begin{parts}
  \part Define NP-completeness.
  \part Give two examples of NP-complete problems.
  \part State Cook's theorem.
\end{parts}

\question[25] \textbf{Algorithm Design.}
Give an efficient algorithm for the following: given a DAG $G$ and two vertices $s$, $t$,
count the number of distinct paths from $s$ to $t$. Analyze time and space.

\question[25] \textbf{Proof.}
Prove that if $P \neq NP$ then there are problems in $NP$ that are neither in $P$ nor NP-complete
(Ladner's theorem). A sketch is acceptable.

\question[15] \textbf{Code.}
Implement a function in Python that solves the 0/1 knapsack problem using dynamic programming.
\begin{lstlisting}
def knapsack(weights, values, capacity):
    # Your code here
    pass
\end{lstlisting}

\question[15] \textbf{Analysis.}
Consider the algorithm:
\begin{lstlisting}
def f(n):
    if n <= 1: return 1
    return f(n-1) + f(n-2) + f(n-3)
\end{lstlisting}
Give a tight asymptotic bound on the running time and justify.

\end{questions}

\end{document}