\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}


{\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\hint#1{(\textbf{Hint:} #1)}

\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 1}}{}{{\sc Course: COMPSCI531D}}
\setft{{\sc Fall 2021}}{{\sc Introduction to Algorithms}}{{\sc Page \thepage}}

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

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

\begin{prob}[10pts]
	An \emph{inversion} in an array $A[1...n]$ is a pair of indices $(i,j)$ such that $i < j$ and $A[i] > A[j]$. Describe and analyze an algorithm that counts the number of inversions in an $n$-element array in $O(n\log n)$ time. \hint{Modify mergesort.}
\end{prob}

\begin{prob}[10pts]
Let $S = \{p_i=(x_i, y_i): 1 \le i \le n\}$ be a set of $n$ points on a 2D plane. We say that a point $p_i$ \emph{dominates} $p_j$ if $x_i \ge x_j$ and $y_i \ge y_j$. A point $p_i$ is a maximal point of $S$ if there are no other points in $S$ dominating $p_i$. In the example below, the red points are maximal points of $S$. Describe and analyze an algorithm that returns the maximal points in $O(n\log n)$ time. \\
\hint{Divide $S$ into two sets based on the $x$-coordinates of points. What is the merge step?}
\begin{figure}[htp]
\centering
\begin{tikzpicture}[scale=0.6]
	\draw [<->,thick] (0,6) node (yaxis) [above] {$y$}
	|- (9,0) node (xaxis) [right] {$x$};
	\foreach \Point in {(1,1), (3,4), (2,3), (4, 2), (7,1)}{
    	\fill \Point circle[radius=2.5pt];
	}
	\foreach \Point in {(8, 2), (3, 5), (6, 4)}{
		\fill[color=red] \Point circle[radius=2.5pt];
	}
\end{tikzpicture}
\end{figure}
\end{prob}

\begin{prob}[10pts]
Recall that the algorithm \textbf{LazySelect} we see in class performs $2n+o(n)$ comparisons with probability at least $1-O(n^{-\frac 14})$. Proved that the expected number of comparisons can be improved to $1.5n+o(n)$ by modifying the algorithm.
\end{prob}


\end{document}
