#LyX file created by tex2lyx 1.6.4
\lyxformat 264
\begin_document
\begin_header
\textclass article
\begin_preamble
\usepackage{fancyheadings}\usepackage{enumerate}\usepackage{xspace}\chead{CS4104(Fall2009):MidtermExamination}
\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\}}}}
\end_preamble
\language english
\inputencoding auto
\font_roman default
\font_sans default
\font_typewriter default
\font_default_family default
\font_sc false
\font_osf false
\font_sf_scale 100
\font_tt_scale 100
\graphics default
\paperfontsize default
\spacing single
\papersize default
\use_geometry false
\use_amsmath 2
\use_esint 1
\cite_engine basic
\use_bibtopic false
\paperorientation portrait
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\defskip medskip
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle fancy
\tracking_changes false
\output_changes false
\end_header
\begin_body
\begin_layout Title
\begin_inset VSpace 0.5in
\end_inset
\series bold
Midterm Examination
\series default
\end_layout
\begin_layout Author
CS 4104 (Fall 2009)
\end_layout
\begin_layout Date
\end_layout
\begin_layout Standard
\align center
Assigned: October 12, 2009.
\end_layout
\begin_layout Standard
\align center
Due: at the beginning of class on October 21, 2009.
\end_layout
\begin_layout Standard
\align center
\begin_inset Tabular
\begin_inset Text
\begin_layout Standard
Name:
\end_layout
\end_inset

\begin_inset Text
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Standard
\backslash
underline{
\backslash
phantom{}}
\end_layout
\end_inset
\end_layout
\end_inset

\begin_inset Text
\end_inset

\begin_inset Text
\end_inset

\begin_inset Text
\begin_layout Standard
PID:
\end_layout
\end_inset

\begin_inset Text
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Standard
\backslash
underline{
\backslash
phantom{}}
\end_layout
\end_inset
\end_layout
\end_inset

\end_inset
\end_layout
\begin_layout Section*
Instructions
\end_layout
\begin_layout Standard
\begin_inset LatexCommand label
name "sec:instructions"
\end_inset
\end_layout
\begin_layout Enumerate
For every algorithm you describe, prove its correctness and analyse its running time. I am looking for clear descriptions of algorithms and for the most efficient algorithms and analysis that you can come up with. I am not specifying the desired running time for each algorithm. I will give partial credit to inefficient algorithms, as long as they are correct.
\end_layout
\begin_layout Enumerate
You may consult the textbook, your notes, or the course web site to solve the problems in the examination. You
\series bold
may not
\series default
work on the exam with anyone else, ask anyone questions, or consult other textbooks or sites on the Web for answers.
\series bold
Do not use
\series default
concepts from Chapters 6 and later in the textbook.
\end_layout
\begin_layout Enumerate
You must prepare your solutions digitally and submit a hardcopy.
\end_layout
\begin_layout Enumerate
I prefer that you use LaTeX\InsetSpace \space{}
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\InsetSpace \space{}
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:
\end_layout
\begin_deeper
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Standard
\backslash
begin{verbatim}
\end_layout
\end_inset
\begin_inset ERT
status collapsed
\begin_layout Standard
%
\backslash
solution{
\end_layout
\begin_layout Standard
\end_layout
\end_inset
\begin_inset ERT
status collapsed
\begin_layout Standard
% }
\end_layout
\begin_layout Standard
\end_layout
\end_inset
\begin_inset ERT
status collapsed
\begin_layout Standard
\backslash
end{verbatim}
\end_layout
\end_inset
\end_layout
\begin_layout Standard
You can uncomment these lines and type in your solution within the curly braces.
\end_layout
\end_deeper
\begin_layout Enumerate
Do not forget to staple the hard copy you hand in.
\end_layout
\begin_layout Standard
Good luck!
\end_layout
\begin_layout Standard
\newpage
\end_layout
\begin_layout Description
Problem 1 (25 points) Solve the following recurrence relation. Note that the recurrence involves two variables
\begin_inset Formula $n$
\end_inset
and
\begin_inset Formula $k$
\end_inset
.
\end_layout
\begin_deeper
\begin_layout Standard
\begin_inset Formula \begin{equation}
T(n, k) \leq
\begin{cases}
2T(n, k  1) + ckn & \text{if $k > 1$,}\\
cn & \text{if $k = 1$.}
\end{cases}
\end{equation}
\end_inset
You can assume that
\begin_inset Formula $c$
\end_inset
is a positive constant.
\emph on
Hint:
\emph default
Unrolling the recurrence may yield a sum that seems hard to analyse. At this point, make a reasonable guess about this sum, and prove the guess by induction (as discussed in class). You may have to play around with your guess till the proof by induction works out correctly.
\end_layout
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Standard
%
\backslash
solution{
\end_layout
\begin_layout Standard
\end_layout
\end_inset
\begin_inset ERT
status collapsed
\begin_layout Standard
% }
\end_layout
\begin_layout Standard
\end_layout
\end_inset
\end_layout
\end_deeper
\begin_layout Description
Problem 2 (15 points) Consider the problem of minimising lateness that we discussed in class. We are given
\begin_inset Formula $n$
\end_inset
jobs. For each job
\begin_inset Formula $i,
1\leq i \leq n$
\end_inset
, we are given a time
\begin_inset Formula $t(i)$
\end_inset
and a deadline
\begin_inset Formula $d(i)$
\end_inset
. Let us assume that all the deadlines are distinct. We want to schedule all jobs on one resource. Our goal is to assign a starting time
\begin_inset Formula $s(i)$
\end_inset
to each job such that each job is delayed as little as possible. A job
\begin_inset Formula $i$
\end_inset
is
\emph on
delayed
\emph default
if
\begin_inset Formula $f(i) > d(i)$
\end_inset
; the
\emph on
lateness of the job
\emph default
is
\begin_inset Formula $\max(0, f(i)  d(i)).$
\end_inset
\end_layout
\begin_deeper
\begin_layout Standard
Define
\end_layout
\begin_layout Enumerate
the
\emph on
lateness of a schedule
\emph default
as
\begin_inset Formula $\max_i \big( \max \big(0, f(i)
 d(i) \big) \big) $
\end_inset
and
\end_layout
\begin_layout Enumerate
the
\emph on
delay of a schedule
\emph default
as
\begin_inset Formula $\sum_{i=1}^n \big( \max
\big(0, f(i)  d(i) \big) \big)$
\end_inset
.
\end_layout
\begin_layout Standard
Note that although the words
\begin_inset Quotes eld
\end_inset
lateness
\begin_inset Quotes erd
\end_inset
and
\begin_inset Quotes eld
\end_inset
delay
\begin_inset Quotes erd
\end_inset
are synonyms, for the purpose of this problem we are defining them to mean different quantities: the lateness of a schedule is the
\emph on
maximum
\emph default
of the latenesses of the individual jobs, while the delay of a schedule is the
\emph on
sum
\emph default
of the latenesses of the individual jobs.
\end_layout
\begin_layout Standard
Consider the algorithm that we discussed in class for computing a schedule with the smallest lateness: we sorted all the jobs in increasing order of deadline and scheduled them in this order. In this problem, we will show in two different ways that this algorithm does not compute the schedule with the smallest delay:
\end_layout
\begin_deeper
\begin_layout Standard
[(i)]
\end_layout
\end_deeper
\begin_layout Enumerate
(5 points) Provide a counterexample to show that this algorithm will not compute the schedule with the smallest delay. You will not need more than two jobs in your counterexample.
\end_layout
\begin_layout Enumerate
(10 points) We proved that the earliestdeadlinefirst algorithm correctly solves the problem of minimising lateness. If we were to use the
\emph on
same proof
\emph default
to try to demonstrate that the algorithm correctly solves the problem of minimising delay, where does the proof break down?
\end_layout
\end_deeper
\begin_layout Description
Problem 3 (30 points) We say that one twodimensional point
\begin_inset Formula $p =
(p_x, p_y)$
\end_inset
\emph on
looks down on
\emph default
another twodimensional point
\begin_inset Formula $q =
(q_x, q_y)$
\end_inset
if
\begin_inset Formula $p_x \geq q_x$
\end_inset
and
\begin_inset Formula $p_y \geq q_y$
\end_inset
. For example, the point
\begin_inset Formula $(2, 10)$
\end_inset
looks down upon the point
\begin_inset Formula $(5, 8)$
\end_inset
but not upon the point
\begin_inset Formula $(5, 12)$
\end_inset
. In a set
\begin_inset Formula $P$
\end_inset
of
\begin_inset Formula $n$
\end_inset
twodimensional points, a point
\begin_inset Formula $p$
\end_inset
is said to be
\emph on
majestic
\emph default
if no point in
\begin_inset Formula $P$
\end_inset
looks down upon
\begin_inset Formula $p$
\end_inset
. Devise an efficient algorithm to compute all majestic points in
\begin_inset Formula $P$
\end_inset
. Note that the number of majestic points can vary anywhere from
\begin_inset Formula $1$
\end_inset
(e.g., if all points are on the line
\begin_inset Formula $x= y$
\end_inset
, then the point with the largest
\begin_inset Formula $y$
\end_inset
coordinate is the only majestic point) to
\begin_inset Formula $P$
\end_inset
(e.g., if all points are on the line
\begin_inset Formula $x + y = 1$
\end_inset
, then all points are majestic). Your algorithm must automatically determine the correct subset of
\begin_inset Formula $P$
\end_inset
that make up the majestic points. Therefore, your proof of correctness must show that
\end_layout
\begin_deeper
\begin_layout Enumerate
all points returned by your algorithm are majestic and
\end_layout
\begin_layout Enumerate
all majestic points in
\begin_inset Formula $P$
\end_inset
are computed by your algorithm.
\end_layout
\end_deeper
\begin_deeper
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Standard
%
\backslash
solution{
\end_layout
\begin_layout Standard
\end_layout
\end_inset
\begin_inset ERT
status collapsed
\begin_layout Standard
% }
\end_layout
\begin_layout Standard
\end_layout
\end_inset
\end_layout
\end_deeper
\begin_layout Description
Problem 4 (30 points) The curriculum in the Department of Computer Science at the University of Draconia consists of
\begin_inset Formula $n$
\end_inset
courses. Each course is mandatory. The prerequisite graph
\begin_inset Formula $G$
\end_inset
has a node for each course, and an edge from course
\begin_inset Formula $v$
\end_inset
to course
\begin_inset Formula $w$
\end_inset
if and only if
\begin_inset Formula $v$
\end_inset
is a prerequisite for
\begin_inset Formula $w$
\end_inset
. In such a case, a student cannot take course
\begin_inset Formula $w$
\end_inset
in the same or an earlier semester than she takes course
\begin_inset Formula $v$
\end_inset
. 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
\begin_inset Formula $G$
\end_inset
does not contain cycles, i.e., it is a directed acyclic graph. Chapter 3.6 of the textbook discusses directed acyclic graphs. The graph can be split into multiple components. For example, an extreme case is when there are no prerequisites at all, in which case each course is in a separate component. Of course, one semester suffices in this trivial case.
\end_layout
\begin_deeper
\begin_layout Standard
If you are concerned about how
\begin_inset Formula $G$
\end_inset
is represented, assume that for each course, you have a list of courses for which it is a prerequisite (the adjacency list representation). If you need, you can assume that the
\begin_inset Quotes eld
\end_inset
list
\begin_inset Quotes erd
\end_inset
for each course is stored in an array. if you want to use another representation, please describe it.
\emph on
Do not use an adjacency matrix representation.
\emph default
\end_layout
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Standard
%
\backslash
solution{
\end_layout
\begin_layout Standard
\end_layout
\end_inset
\begin_inset ERT
status collapsed
\begin_layout Standard
% }
\end_layout
\begin_layout Standard
\end_layout
\end_inset
\end_layout
\end_deeper
\end_body
\end_document