\usepackage{ifthen}
\usepackage{soul}
\usepackage{fullpage, prettyref}
\usepackage{fancyhdr}
%\usepackage{palatino}
\usepackage{graphicx}
\usepackage{marvosym}
\usepackage{ifthen}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}

\usepackage{mdframed}
\usepackage{amsmath, amssymb, amsthm}
\usepackage{url}
\usepackage{fullpage, prettyref}
\usepackage{boxedminipage}
\usepackage{wrapfig}
\usepackage{ifthen}
\usepackage{color,xcolor}
\usepackage{transparent}
\usepackage{enumitem}
\usepackage{varwidth}
\usepackage[pagebackref,colorlinks=true,pdfpagemode=none,urlcolor=blue,linkcolor=blue,citecolor=violet,pdfstartview=FitH]{hyperref}
\usepackage[noabbrev,nameinlink]{cleveref}


\def\bar{\overline}


\def\plus{{\tt (+)}}
\def\2plus{{\tt (++)}}
\def\3plus{{\tt (+++)}}
\def\4plus{{\tt (++++)}}
\def\5plus{{\tt (+++++)}}






\usepackage{ifthen}
\usepackage{soul}
\usepackage{fullpage, prettyref}
\usepackage{fancyhdr}
\usepackage{color,xcolor}

\newcommand{\Lim}{\lim}
\usepackage{times}
%\usepackage{palatino}
\usepackage{graphicx}
\usepackage{marvosym}
\usepackage{ifthen}
\usepackage{algorithm}

\usepackage[noend]{algpseudocode}
\algrenewcomment[1]{\(\triangleright\) {\small{\emph{\color{blue} #1}}}}
\algnewcommand{\LineComment}[1]{\State \(\triangleright\) \emph{\color{blue} #1}}
\algnewcommand{\Invariant}[1]{\State \(\triangleright\) \emph{\color{red} #1}}
%\newcommand{\Lim}{\lim}


\usepackage{amsmath, amssymb, amsthm}
\usepackage{url}
\usepackage{fullpage, prettyref}
%\usepackage{pstricks,pst-node,pst-text}
\usepackage{boxedminipage}
\usepackage{wrapfig}
\usepackage{ifthen}

\usepackage{transparent}
\usepackage{enumitem}
\usepackage{varwidth}

\theoremstyle{definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{claim}{Claim}
\newtheorem{corollary}{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{proposition}{Proposition}
\newtheorem{fact}{Fact}
\newtheorem{example}{Example}
\newtheorem{exercise}{Problem}
\newtheorem{drill}{Exercise}
\newtheorem{assumption}{Assumption}
\newtheorem{observation}{Observation}

\newcommand{\comment}[1]{\textsl{\small[#1]}\marginpar{\tiny\textsc{To Do!}}}
\newcommand{\ignore}[1]{}



\def\plus{{\tt (+)}}
\def\2plus{{\tt (++)}}
\def\3plus{{\tt (+++)}}
\def\4plus{{\tt (++++)}}
\def\5plus{{\tt (+++++)}}




\newenvironment{proofof}[1]{\smallskip\noindent{\bf Proof of #1:}}%
{\hspace*{\fill}$\Box$\par}

\setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{0in}
\setlength{\textheight}{8.5in}
\newlength{\algobox}
\setlength{\algobox}{6.5in}

\newcommand{\true}{\mathsf{true}}
\newcommand{\false}{\mathsf{false}}
\newcommand{\xor}{\oplus}
\newcommand{\range}{\mathrm{range}}


\def\Coursename{CS 36/236: Approximation Algorithms (Winter 2021)~} %This needs to be modified each course.

\def\Math{{\color{red} \Libra}}

\ifthenelse{\equal{\showsols}{1}}
{
	\newcommand{\qcomm}[1]{#1}
	\newcommand{\acomm}[1]{\ignore{#1}}
	\newcommand{\comm}[1]{\begin{mdframed}[backgroundcolor=blue!10,topline=false,bottomline=false,leftline=false,rightline=false]{\bf Comments:} #1\end{mdframed}}
	\newcommand{\solution}[1]{\noindent {\color{blue} {\bf Solution:}} {\color{gray} {#1}}}
	\newcommand{\announce}[1]{{\begin{quote}\Large \bf These are solution sketches to a problem set assigned in \Coursename at Dartmouth College, Hanover, NH. If you are not a student in this course in this term, 
				please STOP READING and delete this file (if email) or shred this paper (if hard copy). 
				
				You may be violating an Honor Code at your institution.\end{quote}}}
	\setlength{\headheight}{16pt}
	\pagestyle{fancy}
	\fancyhead{}
	\chead{{\Large \bf Only for \Coursename students}}
	\rhead{}
}
{
	\newcommand{\solution}[1]{\ignore{#1}}	
	\newcommand{\announce}[1]{\ignore{#1}}
	\newcommand{\comm}[1]{\ignore{#1}}
	\newcommand{\acomm}[1]{#1} %\acomm{blah} is ignored in the answer copy but taken care of in question
	\newcommand{\qcomm}[1]{\ignore{#1}} %\qcomm{blah} is ignored in the qn copy but taken care of in answr
	
}


\ifthenelse{\equal{\showhints}{1}}
{
	\newcommand{\hint}[1]{\begin{mdframed}[backgroundcolor=brown!20,topline=false,bottomline=false,leftline=false,rightline=false]{\color{brown}{\bf  Hint}}: {\color{gray} {#1}}\end{mdframed}}
}
{
	\newcommand{\hint}[1]{\ignore{#1}}	
}






\renewcommand{\theenumi}{\alph{enumi}}

%%%%%%%%%%%%%%%%%%%%   SHORTCUTS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%Calligraphic Letters
\newcommand{\script}[1]{\mathcal{#1}}

\newcommand{\cA}{\mathcal{A}}
\newcommand{\cB}{\mathcal{B}}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\cD}{\mathcal{D}}
\newcommand{\cE}{\mathcal{E}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cG}{\mathcal{G}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cI}{\mathcal{I}}
\newcommand{\cJ}{\mathcal{J}}
\newcommand{\cK}{\mathcal{K}}
\newcommand{\cL}{\mathcal{L}}
\newcommand{\cM}{\mathcal{M}}
\newcommand{\cN}{\mathcal{N}}
\newcommand{\cO}{\mathcal{O}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\cQ}{\mathcal{Q}}
\newcommand{\cR}{\mathcal{R}}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\cT}{\mathcal{T}}
\newcommand{\cU}{\mathcal{U}}
\newcommand{\cV}{\mathcal{V}}
\newcommand{\cW}{\mathcal{W}}
\newcommand{\cX}{\mathcal{X}}
\newcommand{\cY}{\mathcal{Y}}
\newcommand{\cZ}{\mathcal{Z}}

\newcommand{\calA}{\mathcal{A}}
\newcommand{\calB}{\mathcal{B}}
\newcommand{\calC}{\mathcal{C}}
\newcommand{\calD}{\mathcal{D}}
\newcommand{\calE}{\mathcal{E}}
\newcommand{\calF}{\mathcal{F}}
\newcommand{\calG}{\mathcal{G}}
\newcommand{\calH}{\mathcal{H}}
\newcommand{\calI}{\mathcal{I}}
\newcommand{\calJ}{\mathcal{J}}
\newcommand{\calK}{\mathcal{K}}
\newcommand{\calL}{\mathcal{L}}
\newcommand{\calM}{\mathcal{M}}
\newcommand{\calN}{\mathcal{N}}
\newcommand{\calO}{\mathcal{O}}
\newcommand{\calP}{\mathcal{P}}
\newcommand{\calQ}{\mathcal{Q}}
\newcommand{\calR}{\mathcal{R}}
\newcommand{\calS}{\mathcal{S}}
\newcommand{\calT}{\mathcal{T}}
\newcommand{\calU}{\mathcal{U}}
\newcommand{\calV}{\mathcal{V}}
\newcommand{\calW}{\mathcal{W}}
\newcommand{\calX}{\mathcal{X}}
\newcommand{\calY}{\mathcal{Y}}
\newcommand{\calZ}{\mathcal{Z}}


%MathBB letters
\newcommand{\RR}{\mathbb{R}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\ZZ}{\mathbb{Z}}


%Mathbold letters
\newcommand{\ba}{\mathbf{a}}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\bc}{\mathbf{c}}
\newcommand{\bd}{\mathbf{d}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bff}{\mathbf{f}}
\newcommand{\bg}{\mathbf{g}}
\newcommand{\bh}{\mathbf{h}}
\newcommand{\bi}{\mathbf{i}}
\newcommand{\bj}{\mathbf{j}}
\newcommand{\bk}{\mathbf{k}}
\newcommand{\bl}{\mathbf{l}}
\newcommand{\bmm}{\mathbf{m}}
\newcommand{\bn}{\mathbf{n}}
\newcommand{\bo}{\mathbf{o}}
\newcommand{\bp}{\mathbf{p}}
\newcommand{\bq}{\mathbf{q}}
\newcommand{\br}{\mathbf{r}}
\newcommand{\bs}{\mathbf{s}}
\newcommand{\bt}{\mathbf{t}}
\newcommand{\bu}{\mathbf{u}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\bw}{\mathbf{w}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bz}{\mathbf{z}}

\newcommand{\bI}{\mathbf{I}}

\newcommand{\bone}{\mathbf{1}}
\newcommand{\bzero}{\mathbf{0}}

\newcommand{\bA}{\mathbf{A}}
\newcommand{\bD}{\boldsymbol{D}}
\newcommand{\bG}{\boldsymbol{G}}

\newcommand{\bR}{\boldsymbol{R}}
\newcommand{\bS}{\boldsymbol{S}}
\newcommand{\bX}{\boldsymbol{X}}
\newcommand{\bY}{\boldsymbol{Y}}
\newcommand{\bZ}{\boldsymbol{Z}}



%Commonly used text in mathmode
\newcommand{\sgn}{\mathrm{sgn}}
\newcommand{\poly}{\mathrm{poly}}
\newcommand{\polylog}{\mathrm{polylog}}
\newcommand{\littlesum}{\mathop{{\textstyle \sum}}}

\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\newcommand{\wh}{\widehat}
\newcommand{\wt}{\widetilde}

\newcommand{\barx}{\overline{x}}
\newcommand{\bary}{\overline{y}}

\newcommand{\lee}{\leqslant}
\newcommand{\gee}{\geqslant}
\newcommand{\ceil}[1]{{\left\lceil{#1}\right\rceil}}
\newcommand{\floor}[1]{{\left\lfloor{#1}\right\rfloor}}

\DeclareMathOperator*{\Exp}{\ensuremath{{\mathbf{Exp}}}}
\DeclareMathOperator*{\Var}{\ensuremath{{\mathbf{Var}}}}
\DeclareMathOperator*{\Prob}{\ensuremath{\mathbf{Pr}}}
\renewcommand{\Pr}{\Prob}
\newcommand{\EX}{\Exp}
\newcommand{\Ex}{\Exp}
\newcommand{\bigO}[1]{\ensuremath{O\Paren{#1}}}

\newcommand{\prob}[1]{\Pr\paren{#1}}
\newcommand{\expect}[1]{\Exp\bracket{#1}}
\newcommand{\var}[1]{\textnormal{Var}\bracket{#1}}
\newcommand{\eexp}[1]{\exp\paren{#1}}
\newcommand{\set}[1]{\ensuremath{\left\{ #1 \right\}}}

\newcommand{\tvd}[2]{\ensuremath{\norm{#1 - #2}_{tvd}}}
\newcommand{\eps}{\ensuremath{\varepsilon}}
\newcommand{\Paren}[1]{\Big(#1\Big)}
\newcommand{\Bracket}[1]{\Big[#1\Big]}
\newcommand{\bracket}[1]{\left[#1\right]}
\newcommand{\paren}[1]{\ensuremath{\left(#1\right)}\xspace}
\newcommand{\card}[1]{\left\vert{#1}\right\vert}
\newcommand{\Ot}{\ensuremath{\widetilde{O}}}
\newcommand{\Omgt}{\ensuremath{\widetilde{\Omega}}}
\newcommand{\half}{\ensuremath{{1 \over 2}}}


\newcommand{\abs}[1]{\left\lvert #1 \right\rvert}
\newcommand{\norm}[1]{\left\lVert #1 \right\rVert}
\newcommand{\psdgeq}{\succcurlyeq}
\newcommand{\eqdef}{\overset{\mathrm{\tiny def}}{=\joinrel=}}
\newcommand{\grad}{\nabla}
\newcommand{\minimize}{\mathrm{minimize}\quad}
\newcommand{\maximize}{\mathrm{maximize}\quad}
%% Hyper-linked References
%\newcommand{\Sec}[1]{\hyperref[sec:#1]{\S\ref*{sec:#1}}} %section
%\newcommand{\Eqn}[1]{\hyperref[eq:#1]{(\ref*{eq:#1})}} %equation
%\newcommand{\Fig}[1]{\hyperref[fig:#1]{Fig.\,\ref*{fig:#1}}} %figure
%\newcommand{\Tab}[1]{\hyperref[tab:#1]{Tab.\,\ref*{tab:#1}}} %table
%\newcommand{\Thm}[1]{\hyperref[thm:#1]{Theorem\,\ref*{thm:#1}}} %theorem
%\newcommand{\Fact}[1]{\hyperref[fact:#1]{Fact\,\ref*{fact:#1}}} %fact
%\newcommand{\Lem}[1]{\hyperref[lem:#1]{Lemma\,\ref*{lem:#1}}} %lemma
%\newcommand{\Prop}[1]{\hyperref[prop:#1]{Prop.~\ref*{prop:#1}}} %property
%\newcommand{\Cor}[1]{\hyperref[cor:#1]{Corollary~\ref*{cor:#1}}} %corollary
%\newcommand{\Conj}[1]{\hyperref[conj:#1]{Conjecture~\ref*{conj:#1}}} %conjecture
%\newcommand{\Def}[1]{\hyperref[def:#1]{Definition~\ref*{def:#1}}} %definition
%\newcommand{\Alg}[1]{\hyperref[alg:#1]{Alg.~\ref*{alg:#1}}} %algorithm
%\newcommand{\Ex}[1]{\hyperref[ex:#1]{Ex.~\ref*{ex:#1}}} %example
%\newcommand{\Clm}[1]{\hyperref[clm:#1]{Claim~\ref*{clm:#1}}} %example
%
%\renewcommand{\Re}{\mathbf{R}}

%%%%%%%%%%%%
\newcommand{\OPT}{\mathtt{OPT}}
\newcommand{\ALG}{\mathtt{ALG}}
\newcommand{\opt}{\mathtt{opt}}
\newcommand{\cost}{\mathtt{cost}}
\newcommand{\alg}{\mathsf{alg}}
\newcommand{\spn}{\mathsf{span}}
\newcommand{\row}{\mathsf{row}}
\newcommand{\supp}{\mathsf{supp}}

\newcommand{\APX}{\ensuremath{\mbox{APX}}}
\newcommand{\apx}{\ensuremath{\mbox{apx}}}



%%%%%%%%%%%%%%%
\newcommand{\etal}{{\it et al.\,}}
\newcommand{\goodetal}{{\it et al.\/}}


\newcommand\dom{\mathbf{dom}}
\newcommand\epi{\mathbf{epi}}
\renewcommand\st{\quad\mathrm{~s.~t.~}\quad}
\newcommand\rand{\mathsf{rand}}
\newcommand{\eq}{\leftarrow}

\newcommand{\remark}[1]{\begin{mdframed}[backgroundcolor=yellow!10,topline=false,bottomline=false,leftline=false,rightline=false] 
		{\bf Remark: }{\em #1} 
\end{mdframed}}

\newcommand{\summ}[1]{\begin{mdframed}[backgroundcolor=orange!10,topline=false,bottomline=false,leftline=false,rightline=false] 
		{\bf Summary: }{\em #1} 
\end{mdframed}}

\newcommand{\todo}[1]{ \begin{mdframed}[backgroundcolor=teal!10,topline=false,bottomline=false,leftline=false,rightline=false] 
		{\bf Ponder This:}{\em #1}
\end{mdframed}}

\newcommand{\problem}[2]{\begin{mdframed}[backgroundcolor=blue!05,topline=false,bottomline=false,leftline=false,rightline=false] 
		{\underline{{\sc #1}}} \\
		#2 
\end{mdframed}}

\newcommand{\thingstoadd}[1]{\begin{mdframed}[backgroundcolor=red!10,topline=false,bottomline=false,leftline=false,rightline=false] 
		{\bf Things to add: }{\em #1} 
\end{mdframed}}

\newenvironment{thm}{
	\begin{mdframed}[backgroundcolor=gray!20,topline=false,bottomline=false,leftline=false,rightline=false]\begin{theorem}
		}{
		\end{theorem}
	\end{mdframed}
}