\documentclass{article}
\usepackage[top=1in,bottom=1in,left=1in,right=1in]{geometry}
\usepackage{fancyheadings,enumerate,xspace,amsmath,graphicx}
\pagestyle{fancy}
\chead{CS 5114 (Spring 2008): Midterm Examination}
\newcommand{\solution}[1]{\textbf{Solution:} #1}
\newcommand{\cut}[1]{\ensuremath{\mathnormal{}{cut}(#1)}}
\newcommand{\calg}{\ensuremath{{\cal G}}\xspace}
\newcommand{\calo}{\ensuremath{{\cal O}}\xspace}
\newcommand{\opt}[1]{\ensuremath{\text{OPT}(#1)}}
\newcommand{\length}[1]{\ensuremath{\overline{#1}}}
% macro for a set. extra pair of braces inside \ensuremath to ensure
% the set is typseset in one line.
\newcommand{\set}[1]{\ensuremath{{\{#1\}}}}
\begin{document}
\title{\vspace{-0.5in}\textbf{Midterm Examination}}
\author{CS 5114 (Spring 2008)}
\date{}
\maketitle
\begin{center}
Assigned: March 10, 2008.
Due: at the beginning of class on March 17, 2008.
\end{center}
\begin{center}
\begin{tabular}[c]{rr}
Name: & \underline{\phantom{--------------------------------}}\\
\\
PID: & \underline{\phantom{--------------------------------}}
\end{tabular}
\end{center}
\section*{Instructions}
\label{sec:instructions}
\begin{enumerate}
\item For every algorithm you describe, prove its correctness and
analyse its running time and space used. I am looking for clear
descriptions of algorithms and for the most efficient algorithms you
can come up with.
\item You may consult the textbook, your notes, or the course web site
to solve the problems in the examination. You \textbf{may not} work on
the exam with anyone else, ask anyone questions, or consult other
textbooks or sites on the Web for answers. \textbf{Do not use}
concepts from Chapters 7 and later in the textbook.
\item You must prepare your solutions digitally and submit a hard-copy
at the beginning of class on March 17.
\item I prefer that you use \LaTeX\ to prepare your solutions. However,
I will not penalise you if you use a different system. To use \LaTeX,
you may find it convenient to download the \LaTeX\ source file for
this document from the link on the course web site. At the end of each
problem are three commented lines that look like this:
\begin{verbatim}
% \solution{
%
% }
\end{verbatim}
You can uncomment these lines and type in your solution within the curly
braces.
\item Do not forget to staple the hard copy you hand in.
\end{enumerate}
Good luck!
\newpage
\begin{description}
\item[Problem 1] (20 points) Solve the following recurrence relation.
You can assume that $T(1) = 0$ and $T(2) = 1$.
$$\sum_{i = 1}^{n - 1} \big(T(n) - T(i) \big) = O(n^2).$$
% \solution{
%
% }
\item[Problem 2] (10 points) You work for a company that operates gas
stations. Your company wants to place one gas station on a long
country road so as to best serve all the houses on that road. For
convenience, assume that the road is a straight line running west to
east and that the position of each house on that road is given by the
$x$-coordinate of the house. Suppose there are $n$ houses with
$x$-coordinates $x_1, x_2, \ldots, x_n$ (these coordinates may not be
in sorted order). There are various ways to measure the distance from
each house to the gas station. Your company wants to find the best
placement of the gas station for different cost models. Suppose $\mu$
is a proposed location for the gas station. Let $d(r, \mu)$ denote the
distance between a house at $x$-coordinate $r$ and the gas station.
Let $C(\mu)$ denote the cost of travelling to the gas station (over
all the houses). Devise an algorithm to compute the value of $\mu$
that minimises $C(\mu)$ under each of the following definitions of~$d(r, \mu)$
and $C(\mu)$ (thus, you should provide two algorithms in total):
\begin{enumerate}[(i)]
\item $d(r, \mu) = (r - \mu)^2$ and $C(\mu) = \sum_{i=1}^n d(x_i, \mu).$
\item $d(r, \mu) = |r - \mu|$ and $C(\mu) = \max_{i=1}^n d(x_i, \mu).$
\end{enumerate}
% \solution{
%
% }
\item[Problem 3] (30 points) We say that one two-dimensional
point $p = (p_x, p_y)$ \emph{looks down on} another two-dimensional
point $q = (q_x, q_y)$ if $p_x \geq q_x$ and $p_y \geq q_y$. For
example, the point $(2, 10)$ looks down upon the point $(-5, 8)$ but
not upon the point $(-5, 12)$. In a set $P$ of $n$ two-dimensional
points, a point $p$ is said to be \emph{majestic} if no point in $P$
looks down upon $p$. Devise an efficient algorithm to compute all majestic
points in $P$.
% \solution{
%
% }
\item[Problem 4] (20 points) The curriculum in the Department of
Computer Science at the University of Draconia consists of $n$
courses. Each course is mandatory. The prerequisite graph $G$ has a
node for each course, and an edge from course $v$ to course $w$ if and
only if $v$ is a prerequisite for $w$. In such a case, a student
cannot take course $w$ in the same or an earlier semester than she
takes course $v$. A student can take any number of courses in a single
semester. Design an algorithm that computes the minimum number of
semesters necessary to complete the curriculum. You may assume that
$G$ does not contain cycles, i.e., it is a directed acyclic graph.
% \solution{
%
% }
\item[Problem 5] (20 points) Many object-oriented programming language
implement a class for manipulating strings. A primitive operation
supported by such languages is to split a string into two pieces. This
operation usually involves copying the original string. Hence, it
takes $n$ units of time for a string of length $n$, regardless of the
location of the split. However, if we want to split a string into many
pieces, the order in which we make the breaks can affect the total
running time of all the splits. For example, if we want to split a
20-character string at positions 3 and 10, then making the first cut
at position 3 incurs a total cost of 20 + 17 = 37, while doing so at
position 10 first has a better cost of 20 + 10 = 30. Design an
algorithm that, given the locations of $m$ cuts in a string of length $n$,
finds the minimum cost of breaking the string into $m + 1$ pieces at
the given locations.
% \solution{
%
% }
\end{description}
\end{document}