%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Wednesday 08 Jun 2022 12:52:47pm -03 by yoshi on ponpoko.local>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno,a4paper]{amsart}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
%----------------------------

%right pdf-output for special characters
\usepackage[T1]{fontenc}
\usepackage{ae}
\usepackage{aecompl}

%\usepackage{lmodern}
\usepackage{amssymb}

\usepackage{xcolor}
\usepackage[backref]{hyperref}
\hypersetup{
    colorlinks,
    linkcolor={red!60!black},
    citecolor={green!60!black},
    urlcolor={blue!60!black}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%  Page Layout
\usepackage{fullpage}
\usepackage{setspace}
\usepackage{bbm}
\footskip28pt
\usepackage{fancyhdr}
\pagestyle{fancy}

\lhead{}
\chead{}
\rhead{}
%\lfoot{}
\cfoot{}
%\rfoot{\today, \currenttime}
\fancyfoot[RO,LE]{\thepage}
\fancyfoot[LO,RE]{{\footnotesize\today, \currenttime}}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%------------------ disjoint union with dot -------------------------------%
\makeatletter
\def\moverlay{\mathpalette\mov@rlay}
\def\mov@rlay#1#2{\leavevmode\vtop{%
   \baselineskip\z@skip \lineskiplimit-\maxdimen
   \ialign{\hfil$\m@th#1##$\hfil\cr#2\crcr}}}
\newcommand{\charfusion}[3][\mathord]{
    #1{\ifx#1\mathop\vphantom{#2}\fi
        \mathpalette\mov@rlay{#2\cr#3}
      }
    \ifx#1\mathop\expandafter\displaylimits\fi}
\makeatother

\newcommand{\dcup}{\charfusion[\mathbin]{\cup}{\cdot}}
\newcommand{\bigdcup}{\charfusion[\mathop]{\bigcup}{\cdot}}
%------------------ disjoint union with dot -------------------------------%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{datetime}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{lineno}
\newcommand*\patchAmsMathEnvironmentForLineno[1]{%
\expandafter\let\csname old#1\expandafter\endcsname\csname #1\endcsname
\expandafter\let\csname oldend#1\expandafter\endcsname\csname end#1\endcsname
\renewenvironment{#1}%
{\linenomath\csname old#1\endcsname}%
{\csname oldend#1\endcsname\endlinenomath}}% 
\newcommand*\patchBothAmsMathEnvironmentsForLineno[1]{%
\patchAmsMathEnvironmentForLineno{#1}%
\patchAmsMathEnvironmentForLineno{#1*}}%
\AtBeginDocument{%
\patchBothAmsMathEnvironmentsForLineno{equation}%
\patchBothAmsMathEnvironmentsForLineno{align}%
\patchBothAmsMathEnvironmentsForLineno{flalign}%
\patchBothAmsMathEnvironmentsForLineno{alignat}%
\patchBothAmsMathEnvironmentsForLineno{gather}%
\patchBothAmsMathEnvironmentsForLineno{multline}%
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\let\:=\colon
\let\epsilon=\varepsilon
\let\phi=\varphi
\let\rho=\varrho
\def\e{{\rm e}}
\def\mdc{\mathop{\rm mdc}\nolimits}
\def\dist{\mathop{\rm dist}\nolimits}
\def\dim{\mathop{\rm dim}\nolimits}
\def\supp{\mathop{\rm supp}\nolimits}
\def\ex{\mathop{\rm ex}\nolimits}
\def\im{\mathop{\rm im}\nolimits}
\def\bsigma{\bar\sigma}
\def\RR{\mathbb R}
\def\NN{\mathbb N}
\def\ZZ{\mathbb Z}
\def\One{{\ensuremath{\mathbbm{1}}}}
\def\({\left(}
\def\){\right)}  
\def\<{\langle}
\def\>{\rangle}
\let\sim=\thicksim

\def\inR{\mathrel{\in_{\text R}}} 
\def\inU{\mathrel{\in_{\text U}}} 

\def\cA{\mathcal A}
\def\cB{\mathcal B}
\def\cC{\mathcal C}
\def\cD{\mathcal D}
\def\cE{\mathcal E}
\def\cF{\mathcal F}
\def\cG{\mathcal G}
\def\cH{\mathcal H}
\def\cI{\mathcal I}
\def\cK{\mathcal K}
\def\cL{\mathcal L}
\def\cP{\mathcal P}
\def\cR{\mathcal R}
\def\cS{\mathcal S}
\def\cZ{\mathcal Z}

\def\tG{\widetilde G}
\def\tcG{\widetilde\cG}

\def\barp{{\bar p}}

\def\Ave{\mathop{{\rm Ave}}}
\def\Bi{\mathop{{\rm Bi}}\nolimits}
\def\Var{\mathop{{\rm Var}}\nolimits}
\def\Cov{\mathop{{\rm Cov}}\nolimits}
\def\dev{\mathop{{\rm dev}}\nolimits}
\def\og{\mathop{{\rm og}}\nolimits}
\def\diam{\mathop{{\rm diam}}\nolimits}
\def\PG{\mathop{{\rm PG}}\nolimits}

\def\EE{\mathop{\hbox{\hbox{${\mathbb E}$}}}\nolimits}
\def\PP{\mathop{\hbox{\raise.03ex\hbox{${\mathbb P}$}}}\nolimits}
\def\FF{\mathop{\hbox{\raise.03ex\hbox{${\mathbb F}$}}}\nolimits}

\def\RP{\mathbf{RP}}
\def\BPP{\mathbf{BPP}}

\def\bfa{\textbf{a}}
\def\bfb{\textbf{b}}
\def\bfd{\textbf{d}}
\def\bff{\textbf{f}}
\def\bfp{\textbf{p}}
\def\bfx{\textbf{x}}
\def\bfy{\textbf{y}}
\def\bfX{\textbf{X}}
\def\bfdelta{\boldsymbol\delta}

\def\ldens{\underline\bfd}
\def\udens{\overline\bfd}
\def\lldens{\underline\bfdelta}
\def\uldens{\overline\bfdelta}

\makeatletter
\renewcommand{\labelenumi}{\theenumi.}
\makeatother
\usepackage{enumitem}
\newcommand\rmlabel{\upshape({\itshape\roman*\,\/})}
\newcommand\RMlabel{\upshape(\Roman*)}
\newcommand\alabel{\upshape({\itshape\alph*\,\/})}
\newcommand\Alabel{\upshape({\itshape\Alph*\,\/})}
\newcommand\nlabel{\upshape({\itshape\arabic*\,\/})}
\newcommand\nlabelp{\upshape(P\arabic*)}
\newcommand\nlabelE{\bf\upshape E\arabic*.}
\newcommand\nlabelS{\bf\upshape S\arabic*.}

\def\datedue#1{{\bf$\boldsymbol\{$\textsl{Data de entrega}: #1$\boldsymbol\}$}}
\def\sugestao#1{[\textit{Sugestão.} #1]}
\let\hint\sugestao
\def\observacao#1{[\textit{Observação.} #1]}
\let\NB\observacao

\begin{document}
\title[CCM128 Computação II]%
{CCM128 Computação II\\
  \bigskip\bigskip{\bf\textit{1{\tiny o.} Semestre de 2022}}\\
  \bigskip\bigskip Exercícios feitos em sala
}  

\shortdate
\yyyymmdddate
\def\today{\number\year/\number\month/\number\day}
\settimeformat{ampmtime}
\date{Versão de \today, \currenttime}
%\date{Versão de \today}

\maketitle

\linenumbers 
\onehalfspace
%\pagestyle{plain}
\pagestyle{fancy}

\begin{enumerate}[label=\nlabelS]
  
\item (16/3/2022) Desenhe a árvore de decisão que representa o
  algoritmo executado pelo mergesort no caso em que o array de entrada
  contém os elementos $a$, $b$ e~$c$, nessa ordem.  Note que a raiz
  dessa árvore contém o comparação ``$b<a$''.  Considere a
  implementação do mergesort em Merge.java, de S\&W.

\item (23/3/2022) Considere o array de inteiros~$a$ dado abaixo:
  \begin{equation*}
    a=[56, -67, 79, 67, -77, -25, 38, 12, -12, 92, -88, -34, 29, 86,  9, 62, -3, -26, -5, -59]
  \end{equation*}
  (isto é, $a[0]=56$, $a[1]=-67$, etc).  Encontre uma permutação~$p$
  de $0,1,\dots,19$ tal que
  \begin{equation*}
    a[p[0]]\leq\dots\leq a[p[19]]. 
  \end{equation*}
  \NB{Note que Merge.indexSort($a$) devolve tal permutação $p$.}

\item (30/3/2022)
  \begin{enumerate}
  \item Considere o array de inteiros~$a$ dado abaixo:
    \begin{equation}
      \label{eq:3}
      a=[44, 11, 33, 22, 66, 55, 77].
    \end{equation}
    Liste todas as comparações que ocorrem entre elementos de~$a$ quando
    a chamada \verb|partition(a, 0, 6)| é executada.  Aqui,
    \verb|partition()| é a função de partição em Quick.java.  Quantas
    comparações são?
    \NB{A primeira comparação é \texttt{11 < 44?}.}
  \item Encontre uma instância de $N=31$ elementos na qual
    \verb|sort()| de Quick.java, sem aleatorização, executa
    $(N+1)\lfloor\log_2N\rfloor = 128$ comparações entre elementos do
    array sendo ordenado.  \hint{Quantas comparações faz
      \texttt{sort()} quando executado com o array~$a$
      em~\eqref{eq:3}?}
  \end{enumerate}

\item (20/4/2022) Considere a função de rebaixamento em heaps binários
\begin{verbatim}
    private static void sink(Comparable[] pq, int k, int N) {
        while (2*k <= N) {
            int j = 2*k;
            if (j < N && less(pq, j, j+1)) j++;
            if (!less(pq, k, j)) break;
            exch(pq, k, j);
            k = j;
        }
    }
\end{verbatim}
  \begin{enumerate}[label=\rmlabel]
  \item Seja \textit{pq} um array de objetos comparable que contém~$N$
    itens (nas posições $\mathit{pq}[1\,.\,.\,N]$).  Suponha que a ABC
    enraizada em~$2k$ é um heap binário e que a ABC enraizada
    em~$2k+1$ é um heap binário.  Prove que a execução de
    $\mathit{sink}(\mathit{pq}, k, N)$ converte a ABC enraizada em~$k$ em um
    heap binário.
  \item\label{it:heapify} Prove que
\begin{verbatim}
    for (int k = N/2; k >= 1; k--)
        sink(pq, k, N);
\end{verbatim}
    transforma o array \textit{pq} em um heap binário.
  \item Quantas comparações (execuções de $\mathit{less}()$) são feitas
  ao se transformar o array
\begin{verbatim}
    a = {S, O, R, T, E, X, A, M, P, L, E}
\end{verbatim}
  em um heap binário quando usamos o algoritmo em~\ref{it:heapify}?
  \end{enumerate}

\item (4/5/2022) Considere o programa abaixo:
\begin{verbatim}
public class Index {
    public static void main(String[] args) {

        ST<String, Queue<Integer>> st = new ST<>(); 

        for (int i = 0; !StdIn.isEmpty(); i++) {
            String key = StdIn.readString();
            if (!st.contains(key))
                st.put(key, new Queue<Integer>());
            st.get(key).enqueue(i);
        }
        
        for (String s : st.keys())
            StdOut.println(s + " " + st.get(s));
    }
} 
\end{verbatim}
  Suponha que executamos o programa acima com a entrada
\begin{verbatim}
    it was the best of times it was the worst of times
    it was the age of wisdom it was the age of foolishness
\end{verbatim}
  Dê a saída dessa execução.

\item (18/5/2022) Considere o programa abaixo:
\begin{verbatim}
public class S6 {

    private static class Node {
        private int item;
        private Node next;

        Node(int item, Node next) 
        { this.item = item; this.next = next; }
    }

    private static void print(Node h) {
        for (Node x = h; x != null; x = x.next)
            StdOut.print(x.item + " ");
        StdOut.println();
    }

    private static Node read() {
        Node first = null;
        while (!StdIn.isEmpty()) {
            int item = StdIn.readInt();
            first = new Node(item, first);
        }
        return first;
    }

    private static Node split(Node c) {
        if (c.next == null)
            return null;
        Node b = c.next;
        while ((b != null) && (b.next != null)) {
            c = c.next;
            b = b.next.next;
        }
        b = c.next; c.next = null;
        return b;
    }

    public static void main(String[] args) {
        Node first = read();
        print(first);
        print(split(first));
        print(first);
    }

}
\end{verbatim}
  Suponha que temos os arquivos \verb|data6.in| e \verb|data7.in| tais
  que
\begin{verbatim}
$ cat data6.in
11 22 33 44 55 66
$ cat data7.in
11 22 33 44 55 66 77
$ 
\end{verbatim}
  \begin{enumerate}[label=\rmlabel]
  \item Diga qual é a saída de
\begin{verbatim}
$ java-algs4 S6 < data6.in
\end{verbatim}
  \item Diga qual é a saída de
\begin{verbatim}
$ java-algs4 S6 < data7.in
\end{verbatim}
  \end{enumerate}

%  \pagebreak
  
  \def\IPL{\mathop{{\rm IPL}}}  
  \def\EPL{\mathop{{\rm EPL}}}  

\item (1/6/2022) Seja~$T$ uma árvore binária com~$N$ nós (internos).
  Prove que
  \begin{equation}
    \label{eq:1}
    \EPL(T)=\IPL(T)+2N. 
  \end{equation}

\item (8/6/2022) Seja~$x_1\dots x_8$ seu número USP.  Considere a
  sequência ordenada de chaves
  \begin{equation}
    \label{eq:2}
    x_11,\,x_22,\,\dots,\,x_88,\,x_19,\,x_20.
  \end{equation}
  Suponha que começamos com uma ARNE vazia, e inserimos as chaves
  em~\eqref{eq:2} uma a uma, na ordem dada.  Desenhe as $10$~ARNES que
  encontramos nesse processo.  \observacao{Se seu NUSP fosse~$12345678$,
    então a sequência em~\eqref{eq:2} seria
    $11,22,33,44,55,66,77,88,19,20$.}. 
  
\end{enumerate}  

\endgroup
\end{document}

%%% Local Variables:
%%% mode: latex
%%% eval: (auto-fill-mode t)
%%% eval: (LaTeX-math-mode t)
%%% eval: (flyspell-mode t)
%%% TeX-master: t
%%% End:
