\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,epsfig}
\setlength{\textwidth}{7in}
\setlength{\topmargin}{-0.575in}
\setlength{\textheight}{9.25in}
\setlength{\oddsidemargin}{-.25in}
\setlength{\evensidemargin}{-.25in}
\reversemarginpar
\setlength{\marginparsep}{-15mm}
\newcommand{\rmv}[1]{}
\newcommand{\bemph}[1]{{\bfseries\itshape#1}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcounter{qctr}
\newcounter{subqctr}
\newcommand{\qno}{\addtocounter{qctr}{1}\arabic{qctr}}
\newcommand{\question}[1]{\setcounter{subqctr}{0}\noindent\textbf{Question \qno.} ({#1} marks)\enspace}
\newcommand{\subqno}{\addtocounter{subqctr}{1}\alph{subqctr}}
\newcommand{\subquestion}[1][]{
\ifthenelse{\equal{#1}{}}
{\noindent\textbf{\subqno.} \enspace}
{\noindent\textbf{\subqno.} ({#1} marks)\enspace}
}
% Here the user must define certain strings for this homework assignment
%
\def\CourseCode{CS6901} % e.g. B38
\def\AssignmentNo{3} % e.g. 1
\def\DateHandedOut{Fall, 2016} % e.g. September 18, 2002
\def\DateDue{Nov 15, 2016} % e.g. October 1, 2002
\def\TimeDue{7pm on D2L} % e.g. 11 am
\begin{document}
\noindent
Computer Science \CourseCode \hfill \DateHandedOut\\
\begin{center}
Homework Assignment \#\AssignmentNo\\
Due: \DateDue, \TimeDue\\
\end{center}
\hrule\smallskip
\begin{enumerate}
\item \textbf{Difference constraints} \marginpar{[20]}\\
A system difference constraints is a system of equations of the form $x_j-x_i \leq b_k$. It can be represented in a matrix form as $Ax \leq b$, where $x$ and $b$ are vectors of length $n$ and $m$, respectively, and $A$ has at most two non-zero entries in every row. For example, the equations can be $x_1 - x_2 \leq 3$, $x_4 - x_1 \leq -1$, and $x_3-x_2 \leq 4$, with one possible solution $(0,0,4,-1)$.
To solve a system of difference constraints, we represent it as a graph (a constraint graph), with vertices $v_1 \dots v_n$ corresponding to variables $x_1 \dots x_n$, plus an extra vertex $s$. We put an edge $(v_i,v_j)$ of weight $b_k$ for each constraint $x_j-x_i \leq b_k$ (note the order of vertices versus variables in the constraint), together with edges of weight $0$ from $s$ to all other vertices. Now, there is a solution to the original system if and only if the graph contains no negative cycle; in particular, assigning to each variable its shortest distance from $s$ gives a solution.
\begin{enumerate}
\item What will be the constraint graph for the example above? Which algorithm will you use to find the solution? And what solution will this algorithm give for the graph in this example?
\item Now suppose that in addition to constraints of the form $x_j - x_i \leq b_k$, there are also constraints of the form $x_j-x_i=b_k$. How can you solve this more general problem using the same ideas?
\end{enumerate}
\item \textbf{"DNA matching" by combining substrings} \marginpar{[30]} \\
You are given a DNA string $y$ of length $m$ over alphabet
$\{A,T,C,G\}$, and "genes" strings $x_1, \dots, x_n$ of lengths
$k_1,\dots, k_n$ respectively, also over the alphabet $\{A,T,C,G\}$. Each
$x_i$ has an associated probability measure $0 < p_i <1$. The goal is
to find the most probable way of concatenating (with repetitions
allowed) some strings from $\{x_1, \dots, x_n\}$ to obtain $y$, if one
exists. The probability of a sequence of strings is a product of
the probabilities of individual strings.
For example, take $y=AGAGTC$, $x_1 =TC$, $x_2=AG$, $x_3=AGAG$
with probabilities $p_1=0.3, p_2 =0.7, p_3 = 0.4$. Then the two possible
mappings of $y$ are $y=x_2 x_2 x_1$ with probability $0.147$ and
$y=x_3 x_1$ with probability $0.12$. Your algorithm should find
the first mapping, since it has higher probability.
\begin{enumerate}
\item Give the definition of an array $A$ that you
will use to solve the problem.
How can you get the probability of the most probable sequence from
this array $A$? How can you check if there is no solution?
\item Give a recurrence to compute elements of $A$, including
initialization.
\item Show the filled array for the example above produced by your
algorithm.
\item Give pseudocode for a dynamic programming algorithm that finds
the \emph{probability} of the most probable matching.
\item Explain (in text and pseudocode) how to recover the actual sequence from
the array computed while finding the highest probability. You can add information to the array when computing it, if you wish.
\end{enumerate}
\item \textbf{Max Independent Set on Trees} \marginpar{[30]}\\
Given a tree $T=(V,E)$, rooted at a node $r\in V$, you need to find a maximum independent set of $T$ (i.e., a max-size
subset $S\subseteq V$ of nodes such that no two nodes in $S$ are connected by an edge of $T$). For example, if you have vertices $a,b,c,d$, edges $(a,b), (b,c), (b,d)$ and weights $w(a)=2$, $w(b)=3$, $w(c)=1$, $w(d)=4$, then the max weight independent set would be $\{a,c,d\}$ with weight 7, however if weight of $b$ is 10 rather than 3 (with the rest of weights the same), the max weight independent set is $\{b\}$ with weight 10.
\begin{enumerate}
\item Give the definition of an array $A$ that you will use to solve the problem. Hint: you might find it convenient to keep two arrays $A_1$ and $A_2$.
How can you get weight of the max independent set this array $A$ (or your two arrays)?
\item Give a recurrence to compute elements of $A$ (or $A_1$ and $A_2$), including initialization.
\item Show the filled arrays for the two examples above as produced by your algorithm.
\item Give pseudocode for a dynamic programming algorithm that finds weight of the max independent set.
\item Explain (in text and pseudocode) how to recover the actual set from the array(s). You can store extra information, if you find it useful.
\end{enumerate}
\item \textbf{Offering courses}\marginpar{[20]}\\
In a certain college, there are $n$ instructors and $m$ different
courses that the college can offer. For every instructor $i$, there is
a list of courses $C_i \subseteq \{1,\dots,m\} $ that this instructor
can teach. In one semester, an instructor can teach no more than three
courses.
\begin{enumerate}
\item Given the $n,m$ and $C_i$ for $1 \leq i \leq n$, determine
the maximal number of different courses the college can offer in one
semester. Hint: design a flow network that represents this problem.
\item Give an example of an input ($n, m$ and all $C_i$) and the
corresponding network where the college cannot offer all courses,
although there is somebody who can teach each course.
\item How can you recover the resulting assignment of instructors to
courses given the
maximum flow on your flow network?
\end{enumerate}
.
\end{enumerate}
\end{document}