\documentclass[11pt]{article}
\usepackage{fullpage,amsmath,hyperref,graphicx,xcolor}
\newcommand{\eps}{\varepsilon}
\newcommand{\fig}[2]{\begin{center}\includegraphics[scale=#2]{#1.pdf}\end{center}}
\begin{document}
\begin{center}\Large\bf
CS/ECE 374 A (Spring 2020)\\
{\Large Homework 10} (due Apr 23 Thursday at 10am)
\end{center}
\medskip\noindent
{\bf Instructions:} As in previous homeworks.
\begin{description}
\bigskip
\item[Problem 10.1:]
We are given $n$ intervals $[a_1,b_1],\ldots, [a_n,b_n]$, which are
pairwise disjoint (i.e., non-overlapping). The intervals are not given in sorted order.
We are also given a number $k$ (which could be less than or greater than $n$).
Your objective is to pick $k$ numbers $p_1,\ldots,p_k$,
such that each $p_i$ lies in $[a_1,b_1]\cup\cdots [a_n,b_n]$, so as the maximize the separation
$$\Delta := \min_{i,j:\: i\neq j} |p_i-p_j|.$$
(In these times, social distancing is important!)
For example: for the intervals $[1,4], [5,8], [11,12], [13,17], [19,23]$ and $k=4$,
one solution is to pick the numbers $1,8,15,23$, which has separation $\Delta=7$ (this appears to be optimal). Note that some intervals may contain none of the numbers you pick; on the other hand, some intervals could contain multiple numbers.
\begin{enumerate}
\item[(a)] ($7.5$ points) First consider the decision problem: decide whether there is a solution with separation at least $r$, for a given value $r$ (and if so, output one such solution). Give an efficient greedy algorithm to solve this decision problem.
Analyze its running time as a function of $n$ and $k$.
({\em Important Note}: for greedy algorithm, you must give a full proof of correctness.)
\item[(b)] ($2.5$ points) Using (a), give an algorithm (the fastest you can achieve) to solve the original problem. You may assume that all $a_i$ and $b_i$ are
integers in $\{1,\ldots,U\}$, and you may analyze the running time in terms of $n$, $k$, and $U$.
\end{enumerate}
\newcommand{\diam}{\textrm{diam}}
\bigskip
\item[Problem 10.2:]
We consider one formulation of a clustering problem where we want to divide a dataset into two clusters.
Specifically, given a set $P$ of $n$ points,
we want to partition $P$
into two subsets $P_1,P_2$ to minimize the following cost function:
$$c(P_1,P_2)=\max\{\diam(P_1),\diam(P_2)\},$$
where (in the corrected version)
\begin{quote}
$\diam(P_i)$ is the smallest value $r$ such that for every
$p,q\in P_i$, there is a path from $p$ to $q$ where every edge
$uv$ in the path has $d(u,v)\le r$.
\end{quote}
%$\diam(P_i)=\max_{p,q\in P_i} d(p,q)$ denotes
%the farthest pair distance in $P_i$. (You may assume that
%$d(p,q)$ can be evaluated in constant time.)
Give an algorithm to solve this problem in $O(n^2)$ time.
Prove correctness of your algorithm.
(\emph{Hint}: consider the largest MST edge\ldots)
\emph{Added bonus}:
2.0 bonus points if you also have a correct algorithm
with $O(n^2)$ or $O(n^2\log n)$ running time
for the original version of the problem with $\diam(P_i)=\max_{p,q\in P_i}d(p,q)$ instead.
\bigskip
\item[Problem 10.3:]
For each of the following languages, either prove that it is
undecidable, or describe an algorithm that decides
this language. (Note that you cannot use Rice
Theorem in solving this problem.)
\begin{enumerate}
\item[(a)]
$\{\langle M,N\rangle \mid \mbox{$L(M)\cap L(N)$ is context-free, where
$M$ is a Turing machine and $N$ is an NFA}\}$
\item[(b)]
$\{\langle M,R\rangle \mid \mbox{$L(M)\subseteq L(R)$,
where $M$ is a DFA and $R$ is a regular expression}\}$
\item[(c)]
$\{\langle M\rangle \mid \mbox{for every $i\ge 1$, $M$ halts on exactly two strings of length $i$, where $M$ is a Turing machine}\}$
\end{enumerate}
\end{description}
\end{document}