#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 
<lyxtabular version="3" rows="3" columns="2">
<features>
<column alignment="right" valignment="top">
<column alignment="right" valignment="top">
<row>
<cell alignment="right" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Standard

Name: 
\end_layout

\end_inset
</cell>
<cell alignment="right" valignment="top" usebox="none">
\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
</cell>
</row>
<row>
<cell alignment="none" valignment="top" usebox="none">
\begin_inset Text

\end_inset
</cell>
<cell alignment="none" valignment="top" usebox="none">
\begin_inset Text

\end_inset
</cell>
</row>
<row>
<cell alignment="right" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Standard

PID: 
\end_layout

\end_inset
</cell>
<cell alignment="right" valignment="top" usebox="none">
\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
</cell>
</row>
</lyxtabular>

\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 hard-copy.
\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 counter-example to show that this algorithm will not compute the schedule with the smallest delay. You will not need more than two jobs in your counter-example. 
\end_layout

\begin_layout Enumerate

(10 points) We proved that the earliest-deadline-first 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 two-dimensional point 
\begin_inset Formula $p =
  (p_x, p_y)$
\end_inset

 
\emph on
looks down on
\emph default
 another two-dimensional 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

 two-dimensional 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 pre-requisites 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 pre-requisite (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