clrs4e-solutions.tex

\documentclass[oneside,11pt,openany,titlepage]{book}

% project-wide constants
\newlength{\lmarginparwidth}\setlength{\lmarginparwidth}{1in}
\newlength{\thinrulethickness}\setlength{\thinrulethickness}{.5pt}
\newlength{\thickrulethickness}\setlength{\thickrulethickness}{5pt}
\setlength{\parindent}{1em}
\setlength{\labelsep}{1em}
\setlength{\marginparsep}{-40pt}
\newlength{\vertexsize}\setlength{\vertexsize}{1.5em}
\newlength{\cellsize}\setlength{\cellsize}{1.3em}
%

\usepackage[T1]{fontenc}
\usepackage[fleqn]{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{stringstrings}
\usepackage{calc}
\usepackage[
    lines=40,
    reversemp,
    lmargin=1in+\lmarginparwidth,
    includehead]{geometry}
\usepackage{tocloft}
\usepackage{titlesec}
\usepackage[twoside]{fancyhdr}
\usepackage[
    font=footnotesize,
    labelfont=bf,
    labelsep=quad,
    singlelinecheck=false]{caption}
\usepackage[
    font=footnotesize,
    labelfont=rm,
    singlelinecheck=true,
    labelformat=simple]{subcaption}
\usepackage[shortlabels]{enumitem}
\PassOptionsToPackage{table}{xcolor}
\usepackage[screen]{clrscode4e}
\usepackage[tikz]{bclogo}
\usepackage{fmtcount}
\usepackage{letltxmacro}
\usepackage{import}

\usepackage[largesc]{newtxtext}
% TODO: To make math fonts even more consistent with the textbook, acquire the mtpro2 complete version, and switch to the below command:
% \usepackage[mtpcal,mtphrb,subscriptcorrection,zswash]{mtpro2}
\usepackage[
    lite,
    eucal,
    amsbb,
    subscriptcorrection,
    zswash]{mtpro2}

\usepackage[
    pdfborder={0 0 0},
    pdftex,
    pdfauthor={Krzysztof Wojtas},
    pdftitle={clrs4e-solutions},
    pdfsubject={Introduction to Algorithms, 4th ed. -- solutions to exercises and problems},
    bookmarksnumbered,
    hypertexnames=false,
    psdextra,
    unicode]{hyperref}

\selectcolormodel{HTML}
\definecolor{lightorange}{HTML}{fcba61}
\definecolor{orange}{HTML}{f5811f}
\definecolor{darkorange}{HTML}{df771b}
\definecolor{darktan}{HTML}{c08a78}
\definecolor{lightblue}{HTML}{aae0f9}
\definecolor{blue}{HTML}{00adef}
\definecolor{darkblue}{HTML}{0084b7}
\definecolor{red}{HTML}{c8232b}
\definecolor{darkred}{HTML}{a51c1f}
\definecolor{yellow}{HTML}{fff200}
\definecolor{darkyellow}{HTML}{e1d200}
\definecolor{lightgray}{HTML}{f5f4e6}
\definecolor{gray}{HTML}{c7c9cb}

\renewcommand{\thepart}{\partname~\Roman{part}}
\renewcommand{\thechapter}{\arabic{chapter}}
\renewcommand{\thesection}{\thechapter.\arabic{section}}
\renewcommand{\thesubsection}{\thesection-\arabic{subsection}}
\renewcommand{\thesubsubsection}{\alph{subsubsection}.}

\renewcommand{\thefigure}{\thesubsection}
\renewcommand{\thesubfigure}{(\alph{subfigure})}
\DeclareCaptionLabelFormat{continued}{#1~#2, continued}
\captionsetup[ContinuedFloat]{labelformat=continued}

\counterwithout{equation}{chapter}

\pagestyle{fancy}
\renewcommand{\chaptermark}[1]{\markboth{\chaptertitlename~\thechapter\hspace\labelsep#1}{}}
\renewcommand{\sectionmark}[1]{\markright{\thesection\hspace\labelsep#1}}
\fancyhead[LO]{\nouppercase{\footnotesize\textit{\rightmark}}}
\fancyhead[RE]{\nouppercase{\footnotesize\textit{\leftmark}}}
\fancyhead[LE,RO]{\footnotesize\textit{\thepage}}
\fancyheadoffset[LE]{\lmarginparwidth}
\fancyfoot{}
\renewcommand{\headrulewidth}{0pt}

\fancypagestyle{plain}{\fancyhf{}}

\titleformat{\part}[display]
  {\normalfont\color{darkblue}\Large\bfseries\itshape}
  {}
  {0pt}
  {\titlerule[\thickrulethickness]\vspace{2in}\titlerule[\thinrulethickness]\vspace{1pt}%
    \thepart\hspace{\lmarginparwidth-\widthof{\thepart}}\vspace{-\baselineskip}}
\titlespacing*{\part}{-\lmarginparwidth}{-\baselineskip-\topskip}{0pt}

\titleformat{\chapter}[display]
  {\normalfont\color{darkblue}\Large\bfseries}
  {}
  {0pt}
  {\titlerule[\thickrulethickness]\vspace{8pt}%
    \thechapter\hspace{\lmarginparwidth-\widthof{\thechapter}}}
\titlespacing*{\chapter}{-\lmarginparwidth}{-\baselineskip-\topskip}{1.5in}

\let\originalchapter=\chapter
\renewcommand{\chapter}[1]{%
    \originalchapter{#1}
    \titleformat{\section}[display]{\large\bfseries}{}{0pt}{%
        \titlerule[\thinrulethickness]\vspace{3pt}\probablestar\thesection\hspace\labelsep}
    \titleformat{\subsection}[runin]{\bfseries\itshape}{\makebox[\lmarginparwidth][l]{\thesubsection}}{0pt}{}
    \titlespacing*{\subsection}{-\lmarginparwidth}{*3}{0pt}
    \renewcommand{\thesection}{\thechapter.\arabic{section}}
    \fancyhead[LO]{\nouppercase{\footnotesize\textit{\rightmark}}}
}

\newcommand{\problems}{%
    \titleformat{\section}[display]{\large\bfseries}{}{0pt}{\titlerule[\thinrulethickness]\vspace{3pt}}
    \titleformat{\subsection}[hang]{\bfseries\itshape}{\makebox[\lmarginparwidth][l]{\thesubsection}}{0pt}{}
    \titlespacing*{\subsection}{-\lmarginparwidth}{*3}{*2}
    \setcounter{section}{0}
    \section*{Problems}
    \phantomsection\addcontentsline{toc}{section}{Problems}
    \setcounter{subsection}{0}
    \renewcommand{\thesection}{\thechapter}
    \fancyhead[LO]{\footnotesize\textit{Problems for \chaptertitlename~\thechapter}}
}

\titlespacing*{\section}{-\lmarginparwidth}{*5}{*2}
\titleformat{\subsubsection}[runin]{\bfseries\itshape}{\thesubsubsection}{1em}{}

\newcommand{\exercise}{\subsection{}\label{sol:\thesubsection}}
\newcommand{\subexercise}{%
    \ifnum\value{subsubsection}=0%
        % this is needed to remove the vertical skip before the first subexercise of an exercise
        \titlespacing*{\subsubsection}{0pt}{-\baselineskip}{*2}%
    \else
        \titlespacing*{\subsubsection}{0pt}{*3}{*2}%
    \fi
    \subsubsection{}\label{sol:\thesubsection\thesubsubsection}
}
\newcommand{\problem}[1]{\subsection{#1}\label{sol:\thesubsection}}
\newcommand{\subproblem}{\subsubsection{}\label{sol:\thesubsection\thesubsubsection}}

\newcommand{\clarification}[2][0]{%
    {\itshape#2%
    \ifnum#1>0%
        \ Corrected in \ordinalstringnum{#1} printing.
    \fi}%
    \bigskip%
    \par\noindent\ignorespaces
}
\newcommand{\customstar}{{\Large$\star$}}
\newcommand{\starred}{%
    \rlap{%
        \protect\makebox[-.1\lmarginparwidth][r]{\customstar}%
        \vspace*{-\baselineskip}}}

\setlength{\logowidth}{15pt}
\newcommand{\workinprogress}{%
    \vspace*{20pt}\marginpar{\bcpanchant}\vspace{-20pt}%
    {\itshape Work in progress.}}

\newcommand{\bignegskip}{\vspace{-\bigskipamount}}

% this is to align pseudocode boxes with the right margin (override the default value from clrscode4e)
\setlength{\screenboxwidth}{\textwidth}
\addtolength{\screenboxwidth}{-7pt}

\renewcommand{\cfttoctitlefont}{\normalfont\color{darkblue}\Large}
\renewcommand{\cftbeforetoctitleskip}{0pt}
\renewcommand{\cftaftertoctitleskip}{1.5in}
\renewcommand{\cftdotsep}{\cftnodots}
\setcounter{tocdepth}{1}
\setcounter{secnumdepth}{3}

\setlist{itemsep=0.5ex}
\setlist[itemize]{leftmargin=*,labelsep=1em,label=\tiny\textbullet}
\setlist[enumerate]{leftmargin=*,labelsep=0.5em}
\setlist[description]{leftmargin=1.5em,labelindent=0pt,labelsep=1em}

\renewcommand{\footnoterule}{\kern-3pt\hrule width\textwidth\kern2pt}

\newtheoremstyle{clrs}{}{}{}{}{\bfseries\itshape}{}{\newline}{%
    \thmname{#1}\thmnumber{\bfseries\itshape{ #2}}\thmnote{ (#3)}}
\theoremstyle{clrs}
\newtheorem*{theorem}{Theorem}
\newtheorem*{lemma}{Lemma}
\newtheorem{numberedlemma}{Lemma}
\renewcommand{\qedsymbol}{\hfill\ensuremath{\blacksquare}{\parfillskip=0pt\par}}

\makeatletter
\renewenvironment{proof}[1][\proofname]{\par
\pushQED{\qed}%
\normalfont \topsep6\p@\@plus6\p@\relax
\trivlist
\item\relax
{\bfseries\itshape #1}\hspace\labelsep\ignorespaces
}{%
\popQED\endtrivlist\@endpefalse
}
\makeatother

\newcommand{\dash}{\,---\,}
\newcommand{\concept}[1]{\textcolor{darkblue}{\textbf{\itshape{#1}}}}
\newcommand{\refExercise}[1]{Exercise~\mbox{\ref{sol:#1}}}
\newcommand{\refProblem}[1]{Problem~\mbox{\ref{sol:#1}}}
\newcommand{\refFigure}[1]{Figure~\mbox{\ref{fig:#1}}}

\makeatletter
\newcommand{\labelledVariable@unstarred}[2]{\ensuremath{#1_\mathrm{#2}}}
\newcommand{\labelledVariable@starred}[2]{\ensuremath{#1^\mathrm{#2}}}
\newcommand{\labelledVariable}{\@ifstar{\labelledVariable@starred}{\labelledVariable@unstarred}}
\makeatother

\LetLtxMacro{\oldsqrt}{\sqrt}
\renewcommand{\sqrt}[2][]{\mathop{}\oldsqrt[#1]{#2}}

\DeclareMathOperator{\degree}{degree}
\renewcommand{\Pr}[1]{\operatorname{Pr}\left\{#1\right\}}
\newcommand{\E}[1]{\operatorname{E}\left[#1\right]}
\newcommand{\Esquared}[1]{\operatorname{E}^2\left[#1\right]}
\newcommand{\Var}[1]{\operatorname{Var}\left[#1\right]}
\newcommand{\I}[1]{\operatorname{I}\left\{#1\right\}}
\renewcommand{\min}[1]{\operatorname{min}\left\{#1\right\}}
\renewcommand{\max}[1]{\operatorname{max}\left\{#1\right\}}
\newcommand{\transpose}[1]{\labelledVariable*{#1}{T}}
\DeclareMathOperator{\rank}{rank}

\makeatletter
\newcommand{\oset}[2]{{\mathpalette\o@set{{#1}{#2}}}}
\newcommand{\o@set}[2]{\o@@set{#1}#2}
\newcommand{\o@@set}[3]{%
  \vbox{\offinterlineskip
    \ialign{\hfil##\hfil\cr
      $\m@th\o@set@demote{#1}#2$\cr
      \noalign{\vskip.1ex}
      $\m@th#1#3$\cr
    }%
  }%
}
\newcommand{\o@set@demote}[1]{%
  \ifx#1\displaystyle\scriptstyle\else
  \ifx#1\textstyle\scriptstyle\else
  \scriptscriptstyle\fi\fi
}
\makeatother

\newenvironment{liftalign*}{%
    \setlength{\abovedisplayskip}{-\baselineskip}%
    \csname align*\endcsname
}{%
    \csname endalign*\endcsname
    \setlength{\abovedisplayskip}{1.5ex plus 1pt minus 2pt}%
}

\newcommand{\Chapter}{}
\newcommand{\starwithsep}{\customstar\hspace\labelsep}
\newcommand{\MakeChapter}[4]{%
    \chapter{#1}%
    \caselower[q]{\chaptertitlename\thechapter}
    \renewcommand{\Chapter}{\thestring}
    \foreach \Title [count=\Section] in {#2}{%
        \global\let\probablestar\relax
        \foreach \SectionToStar in {#3}{%
            \ifthenelse{\numexpr\value{section}+1=\SectionToStar}{%
                % it has to be \global\let, becasue \foreach runs iterations in a local scope
                \global\let\probablestar=\starwithsep
            }{}%
        }%
        \section{\Title}%
        \foreach \Exercise in {1,...,16}{%
            \IfFileExists{\Chapter/sections/\Section/\Exercise}{%
                \exercise
                \import{\Chapter/sections/\Section/}{\Exercise}
            }{}%
        }%
    }%
    \problems
    \foreach \Title [count=\Problem] in {#4}{%
        \problem{\Title}
        \IfFileExists{\Chapter/problems/\Problem/main}{%
            \import{\Chapter/problems/\Problem/}{main}
        }{}%
        \foreach \SubProblem in {a,...,j}{%
            \IfFileExists{\Chapter/problems/\Problem/\SubProblem}{%
                \subproblem
                \import{\Chapter/problems/\Problem/}{\SubProblem}
            }{}%
            \IfFileExists{\Chapter/problems/\Problem/post_\SubProblem}{%
                \bigskip\par\noindent\import{\Chapter/problems/\Problem/}{post_\SubProblem}
            }{}%
        }%
    }%
}

\usetikzlibrary{
    arrows.meta,
    bending,
    calc,
    decorations.pathreplacing,
    matrix,
    positioning,
    topaths}

\tikzset{
    font=\footnotesize,
    >={Stealth[scale length=1.5, scale width=1.25]},
    element/.style = {text height=1ex, text depth=0ex, inner sep=0pt},
    index/.style = {font=\scriptsize, rectangle, draw=none, fill=none, inner sep=0pt, minimum size=1ex},
    vertex/.style = {element, circle, minimum size=\vertexsize, label distance=1pt},
    tan vertex/.style = {vertex, fill=tan, draw=orange},
    orange vertex/.style = {vertex, fill=orange, draw=darkorange},
    light blue vertex/.style = {vertex, fill=lightblue, draw=blue},
    red vertex/.style = {vertex, fill=red, draw=darkred},
    cell/.style = {element, draw, minimum size=\cellsize},
    array/.style = {matrix of nodes, column sep=-\pgflinewidth, row 1/.style={nodes=cell}, nodes in empty cells},
    indexed array/.style = {matrix of nodes, column sep=-\pgflinewidth, row 1/.style={nodes=index, row sep=.5ex}, row 2/.style={nodes=cell}, nodes in empty cells},
    level/.style = {level distance=1.7\vertexsize, sibling distance=11\vertexsize/2^#1},
    transition edge/.style n args = {3}{decorate, decoration={show path construction,
        lineto code={
            \draw[#1] (\tikzinputsegmentfirst) -- ($(\tikzinputsegmentfirst) ! #3 ! (\tikzinputsegmentlast)$);
            \draw[#2] ($(\tikzinputsegmentfirst) ! #3 ! (\tikzinputsegmentlast)$) -- (\tikzinputsegmentlast);
        }
    }},
    very densely dashed/.style = {dash pattern=on 1.5pt off 1pt}
}


\begin{document}
    \let\probablestar\relax
    \setlength{\mathindent}{0pt}
    \setlength{\abovedisplayskip}{1.5ex plus 1pt minus 2pt}
    \setlength{\belowdisplayskip}{1.5ex plus 1pt minus 2pt}

    \frontmatter

    \import{./}{frontcover.tex}
    \pagebreak
    \import{./}{disclaimer.tex}
    \vspace*{5ex}
    \import{./}{acknowledgements.tex}
    \vfill

    \ifpdf
        \addtocontents{toc}{\protect\pdfbookmark{Contents}{toc}}
    \fi

    \tableofcontents

    \mainmatter

    \part{Foundations}

    \MakeChapter{The Role of Algorithms in Computing}{
        Algorithms,
        Algorithms as a technology}{}{
        Comparison of running times}

    \MakeChapter{Getting Started}{
        Insertion sort,
        Analyzing algorithms,
        Designing algorithms}{}{
        Insertion sort on small arrays in merge sort,
        Correctness of bubblesort,
        Correctness of Horner's rule,
        Inversions}

    \MakeChapter{Characterizing Running Times}{
        {$O$-notation, $\Omega$-notation, and $\Theta$-notation},
        Asymptotic notation: formal definitions,
        Standard notations and common functions}{}{
        Asymptotic behavior of polynomials,
        Relative asymptotic growths,
        Ordering by asymptotic growth rates,
        Asymptotic notation properties,
        Manipulating asymptotic notation,
        Variations on $O$ and $\varOmega$,
        Iterated functions}

    \MakeChapter{Divide-and-Conquer}{
        Multiplying square matrices,
        Strassen's algorithm for matrix multiplication,
        The substitution method for solving recurrences,
        The recursion-tree method for solving recurrences,
        The master method for solving recurrences,
        Proof of the continuous master theorem,
        Akra-Bazzi recurrences}{6,7}{
        Recurrence examples,
        Parameter-passing costs,
        Solving recurrences with a change of variables,
        More recurrence examples,
        Fibonacci numbers,
        Chip testing,
        Monge arrays}
    
    \MakeChapter{Probabilistic Analysis and Randomized Algorithms}{
        The hiring problem,
        Indicator random variables,
        Randomized algorithms,
        Probabilistic analysis and further uses of indicator random variables}{4}{
        Probabilistic counting,
        Searching an unsorted array}

    \part{Sorting and Order Statistics}
    
    \MakeChapter{Heapsort}{
        Heaps,
        Maintaining the heap property,
        Building a heap,
        The heapsort algorithm,
        Priority queues}{}{
        Building a heap using insertion,
        Analysis of $d$-ary heaps,
        Young tableaus}

    \setcounter{part}{7}
    \part{Appendix: Mathematical Background}

    \appendix

    \MakeChapter{Summations}{
        Summation formulas and properties,
        Bounding summations}{}{
        Bounding summations}

    \MakeChapter{Sets, Etc.}{
        Sets,
        Relations,
        Functions,
        Graphs,
        Trees}{}{
        Graph coloring,
        Friendly graphs,
        Bisecting trees}

    \MakeChapter{Counting and Probability}{
        Counting,
        Probability,
        Discrete random variables,
        The geometric and binomial distributions,
        The tails of the binomial distribution}{5}{
        The Monty Hall problem,
        Balls and bins}

    \MakeChapter{Matrices}{
        Matrices and matrix operations,
        Basic matrix properties}{}{
        Vandermonde matrix,
        Permutations defined by matrix-vector multiplication over GF(2)}

    \backmatter

    \let\chapter=\originalchapter
    \titleformat{\chapter}{\normalfont\color{darkblue}\Large}{}{0pt}{}
    \titlespacing*{\chapter}{0pt}{0pt}{1.5in}
    \bibliographystyle{plain}
    {\footnotesize\bibliography{clrs4e-solutions}}
    \nocite{*}

\end{document}