\documentclass[11pt]{article}\pagestyle{empty}
\usepackage{amsmath,amssymb,amsthm,color,graphicx}
\usepackage{euscript}
\usepackage{mathpazo}

\usepackage[top=1.5in,bottom=1.5in,left=1.25in,right=1.25in]{geometry}
%improve trypography

\usepackage{microtype}
\usepackage{fixltx2e}
\usepackage{fullpage}
\usepackage{xspace}
\usepackage{tikz}
\usepackage{enumitem}


{\catcode`\@=11
\gdef\setft#1#2#3{%
\def\@oddfoot{%
{\setbox0=\hbox{#1}%
\setbox1=\hbox{#3}%
\ifdim\wd0>\wd1%
\dimen0=\wd0%
\box0\hfil#2\hfil\hbox to\dimen0{\hfil\hfil\box1}%
\else \dimen0=\wd1%
\hbox to\dimen0{\box0\hfil}\hfil#2\hfil\box1\fi%
}}}}

{\catcode`\@=11
\gdef\sethd#1#2#3{%
\def\@oddhead{\vbox{\hbox to\hsize{{#1}\hfil{#2}\hfil{#3}}%
\vspace{0.06in}%
\hbox to \hsize{\hrulefill}\vspace*{-0.09in}}}
\def\@evenhead{\@oddhead}
	}
}

\def\reals{\mathbb{R}}
\def\sphere{\mathbb{S}}
\def\xx{\mathbf{x}}
\def\norm#1{\Vert #1 \Vert}
\def\hint#1{(\textbf{Hint:} #1)}

\DeclareMathOperator*{\argmin}{arg\,min}


\marginparsep=1pt
\oddsidemargin=0.25in
%
%%%%%% A few macros %%%%%%%%%%%%%%%%
\newtheorem{probm}{Problem}
\newenvironment{prob}{\noindent{\bf Problem \addtocounter{probm}{1}
\hspace{-1mm}\theprobm:\hspace{2mm}}}{\vspace{2mm}}

\def\hint#1{\noindent ({\bf Hint:} {\it #1})}
\def\eps{\varepsilon}
\def\conv{\mathop{\mathrm{conv}}}

\parskip=2mm
\sethd{{\sc Assignment 3}}{}{{\sc Course: COMPSCI531D}}
\setft{{\sc Fall 2021}}{{\sc Introduction to Algorithms}}{{\sc Page \thepage}}

\begin{document}
\vspace*{2mm}

\noindent\textbf{Due Date: September 30, 11:59pm}

\noindent In all problems, prove the correctness of your algorithm and analyze its running time.

\begin{prob}[10pts]
Let $S = \{[s_i, f_i]: 1\le i\le n\}$ be a set of $n$ intervals. Each interval $[s_i,f_i]$ has a weight $w_i$. A subset $R\subseteq S$ is called \emph{feasible} if no two intervals in $R$ overlap, i.e. if $[s_i, f_i], [s_j, f_j] \in R$ then $[s_i,f_i] \cap [s_j,f_j] = \varnothing$. Describe an algorithm to find a feasible subset of $S$ of maximum weight. 
\end{prob}

\begin{prob}
	Let $T_1 = \langle p_1, \dots, p_r\rangle $ and $T_2 = \langle q_1, \dots, q_s\rangle$ be two sequences of points in $\reals^2$. A \emph{correspondence} is an ordered pair of the form $(p_i, q_j)$. A set $C$ of correspondences is \emph{monotone} if for any two correspondences $(p_i, q_j)$ and $(p_{i'}, q_{j'})$ in $C$ with $i < i'$, we have $j < j'$. Furthermore, $C$ is called an \emph{assignment} if every point $p_i$ $(1\le i \le r)$ and $q_j$ $(1\le j \le s)$ appears in at least one pair in $C$. The \emph{dynamic time warping} (DTW) cost of a monotone assignment $C$ is 
	\[
	\mathsf{dtw}(T_1, T_2, C) = \sum_{(p, q)\in C}\norm{p-q}^2
	\]
	where $\norm{p-q}$ is the Euclidean distance between $p$ and $q$. Define $\mathsf{dtw}(T_1,T_2) = \argmin_C \mathsf{dtw}(T_1, T_2, C)$, where the minimum is taken over all monotone assignments.   

	\begin{enumerate}[label=(\alph*)]
		\item {[10pts]} Describe an $O(rs)$-time algorithm to compute $\mathsf{dtw}(T_1, T_2)$. 
		\item {[10pts]} Suppose that $s$ is much larger than $r$, and we want to find a contiguous subsequence $R_2$ of $T_2$ such that $\mathsf{dtw}(T_1, R_2)$ is minimized among all contiguous subsequences of $T_2$. How would you adapt the algorithm in (a) to compute $\mathsf{dtw}(T_1, R_2)$ such that the asymptotic running time stays the same?
	\end{enumerate}
	
	
\end{prob}



\end{document}
