Standard Exam

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

% Uncomment to show answers
% \printanswers

\pagestyle{headandfoot}
\header{CS 330 Midterm}{Fall Semester}{\oddeven{Page \thepage\ of \numpages}{}}
\footer{}{}{\iflastpage{End of exam.}{Continue.}}
\runningheadrule
\runningfootrule

\begin{document}

\begin{center}
  {\LARGE\bfseries CS 330 -- Midterm Exam}\\[0.3em]
  {\large Duration: 90 minutes \;\;--\;\; Total points: \numpoints}
\end{center}

\vspace{1em}
\noindent\textbf{Name:} \hrulefill \hspace{2em}\textbf{Student ID:} \hrulefill

\vspace{0.5em}
\noindent\emph{Closed book. Calculators permitted. Show your work for partial credit.}

\vspace{1em}
\hrule
\vspace{1em}

\begin{questions}

\question[10] Define ``asymptotic tight bound'' ($\Theta$-notation) precisely.
\vspace{4cm}

\question[15] State and prove the Master Theorem for $T(n) = aT(n/b) + f(n)$.
\vspace{6cm}

\question[10] Rank by asymptotic order: $n^3$, $2^n$, $n!$, $n\log n$, $\log n$.
\vspace{3cm}

\question[15] Give pseudocode for Mergesort and analyze its worst-case running time.
\vspace{6cm}

\question[10] Multiple choice.
\begin{parts}
  \part Which of the following is $O(n)$?
  \begin{choices}
    \choice Sorting via comparisons
    \CorrectChoice Counting elements
    \choice Computing determinants
    \choice All-pairs shortest paths
  \end{choices}
\end{parts}

\question[10] True or False. Explain briefly.
\begin{parts}
  \part Dijkstra handles negative edge weights correctly.
  \part Quicksort has worst-case $O(n\log n)$.
  \part Every DAG has a topological ordering.
\end{parts}

\question[15] Design an algorithm to find the $k$-th smallest element of an unsorted array in expected linear time.
\vspace{6cm}

\question[15] Prove that the problem of 3-SAT is NP-complete.

\end{questions}

\end{document}