%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Friday 09 Oct 2026 08:50:05p.m. -03 by yoshi on ponpoko>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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{lmodern}

\usepackage{dsfont}
\usepackage{amssymb}
\usepackage{mathtools}

% \usepackage{xcolor}
\usepackage[dvipsnames]{xcolor}
\newcommand\myshade{85}
\colorlet{mylinkcolor}{violet}
\colorlet{mycitecolor}{YellowOrange}
\colorlet{myurlcolor}{Aquamarine}

\usepackage[backref]{hyperref}
% \hypersetup{
%     colorlinks,
%     linkcolor={red!60!black},
%     citecolor={green!60!black},
%     urlcolor={blue!90!black}
%   }
\hypersetup{
  linkcolor  = mylinkcolor!\myshade!black,
  citecolor  = mycitecolor!\myshade!black,
  urlcolor   = myurlcolor!\myshade!black,
  colorlinks = true,
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%  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[mathlines]{lineno}
\usepackage{etoolbox} %% <- for \pretocmd, \apptocmd and \patchcmd

% Patch 'normal' math environment: (currently unused, but good to have)
\newcommand*\linenomathpatch[1]{%
   \expandafter\pretocmd\csname #1\endcsname {\linenomath}{}{}%
   \expandafter\pretocmd\csname #1*\endcsname{\linenomath}{}{}%
   \expandafter\apptocmd\csname end#1\endcsname {\endlinenomath}{}{}%
   \expandafter\apptocmd\csname end#1*\endcsname{\endlinenomath}{}{}%
 }
% Patch AMS math environment:
\newcommand*\linenomathpatchAMS[1]{%
    \expandafter\pretocmd\csname #1\endcsname {\linenomathAMS}{}{}%
    \expandafter\pretocmd\csname #1*\endcsname{\linenomathAMS}{}{}%
    \expandafter\apptocmd\csname end#1\endcsname {\endlinenomath}{}{}%
    \expandafter\apptocmd\csname end#1*\endcsname{\endlinenomath}{}{}%
}

%% Definition of \linenomathAMS depends on whether the mathlines option
%% is provided
\expandafter\ifx\linenomath\linenomathWithnumbers
\let\linenomathAMS\linenomathWithnumbers
%% The following line gets rid of an extra line numbers at the bottom:
\patchcmd\linenomathAMS{\advance\postdisplaypenalty\linenopenalty}{}{}{}
\else
\let\linenomathAMS\linenomathNonumbers
\fi

% \linenomathpatch{equation} %% <- unnecessary, equation is already patched
\linenomathpatchAMS{gather}
\linenomathpatchAMS{multline}
\linenomathpatchAMS{align}
\linenomathpatchAMS{alignat}
\linenomathpatchAMS{flalign}
\linenomathpatch{equation}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\let\:=\colon
\let\epsilon=\varepsilon
\let\phi=\varphi
\let\rho=\varrho
\def\e{{\rm e}}
\def\id{\mathop{\rm id}\nolimits}
\def\Div{\mathop{\rm Div}\nolimits}
\def\mdc{\mathop{\rm mdc}\nolimits}
\def\occ{\mathop{\rm occ}\nolimits}
\def\dist{\mathop{\rm dist}\nolimits}
\def\dim{\mathop{\rm dim}\nolimits}
\def\diag{\mathop{\rm diag}\nolimits}
\def\supp{\mathop{\rm supp}\nolimits}
\def\ex{\mathop{\rm ex}\nolimits}
\def\Im{\mathop{\rm Im}\nolimits}
\def\prof{\mathop{\rm prof}\nolimits}
\def\bsigma{\bar\sigma}
\def\CC{\mathbb C}
\def\RR{\mathbb R}
\def\NN{\mathbb N}
\def\ZZ{\mathbb Z}
\def\QQ{\mathbb Q}
\def\One{{\ensuremath{\mathbbm{1}}}}
\def\({\left(}
\def\){\right)}  
\def\<{\langle}
\def\>{\rangle}
\def\llfloor{\left\lfloor}
\def\rrfloor{\right\rfloor}  
\def\llceil{\left\lceil}
\def\rrceil{\right\rceil)}  
\let\sim=\thicksim
\def\qand{\quad\text{e}\quad}
\def\qqand{\qquad\text{e}\qquad}

\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\Null{\mathop{\rm Null}}
\def\Row{\mathop{\rm Row}}
\def\Col{\mathop{\rm Col}}
\def\Ker{\mathop{\rm Ker}}
\def\Span{\mathop{\rm Span}}
\def\Sol{\mathop{\rm Sol}}
\def\posto{\mathop{\rm posto}}
\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\GF{\mathop{\rm GF}\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\FF{\mathbb{F}}

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

\def\bfa{\mathbf{a}}
\def\bfb{\mathbf{b}}
\def\bfc{\mathbf{c}}
\def\bfd{\mathbf{d}}
\def\bfe{\mathbf{e}}
\def\bff{\mathbf{f}}
\def\bfi{\mathbf{i}}
\def\bfj{\mathbf{j}}
\def\bfp{\mathbf{p}}
\def\bfq{\mathbf{q}}
\def\bfu{\mathbf{u}}
\def\bfs{\mathbf{s}}
\def\bfr{\mathbf{r}}
\def\bfv{\mathbf{v}}
\def\bfw{\mathbf{w}}
\def\bfx{\mathbf{x}}
\def\hbfx{\widehat{\mathbf{x}}}
\def\bfy{\mathbf{y}}
\def\bfX{\mathbf{X}}
\def\bfalpha{{\boldsymbol\alpha}}
\def\bfbeta{{\boldsymbol\beta}}
\def\bfgamma{{\boldsymbol\gamma}}
\def\bfdelta{{\boldsymbol\delta}}
\def\bfzero{{\mathbf{0}}}
\def\dsone{{\mathds{1}}}

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

\def\dotdot{\,.\,.\,}

\makeatletter
\renewcommand{\labelenumi}{\theenumi.}
\makeatother
\def\itemtrig{$\vartriangleright$}
\def\itemcirc{$\circ$}
\def\itemT{\item[\itemtrig]}
\def\itemC{\item[$\circ$]}
\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*}

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

\begin{document}
\title[MAC0338 Análise de Algoritmos]%
{Análise de Algoritmos\\
  \bigskip\bigskip{\bf\textit{2$^{\text{\tiny o.}}$ Semestre de 2026}}\\
  \bigskip\bigskip Exercícios
}  

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

\noindent\textbf{Entrega.}
Entregue suas soluções no e-Disciplinas.

\medskip

\noindent\textbf{Política de colaboração e uso de fontes.}
Todo trabalho entregue por você deve ser seu.  Você é encorajado a
discutir com seus colegas o material visto em sala e os enunciados dos
exercícios, mas tome cuidado para não compartilhar seu trabalho além
do permitido.  Todos os exercícios a serem entregues nesta disciplina
serão
\begin{center}
  \textbf{INDIVIDUAIS.}
\end{center}
Nestes exercícios individuais, você não deve compartilhar suas
soluções ou mesmo ideias de soluções com seus colegas.  Você não deve
procurar soluções de terceiros (como de amigos, LLMs, ou na Web).
Caso você acidentalmente encontre e leia a solução de algum exercício
em algum lugar, você deve citar esta fonte em sua solução.  Caso você
acidentalmente acabe colaborando com colegas na descoberta de uma
solução, você deve citar esta colaboração em sua solução.  Seu
desempenho nesta disciplina ficará prejudicado caso você viole essas
regras.

\medskip
\noindent\textbf{Fontes dos exercícios.}  Vários (maioria?) dos
exercícios virão de nossa bibliografia principal (CLRS, 3a.~edição).
Você é encorajado a fazer todos os exercícios e problemas do CLRS
relacionados ao material vista na disciplina.

\medskip
\noindent\textbf{Exercícios para entrega.}  Os exercícios para entrega
estão marcados com uma data de entrega.

\medskip
\noindent\textbf{Exercícios marcados (\textit{M}).}  Os exercícios
marcados~(\textit{M}) são para os mais matematicamente inclinados, e
não serão cobrados nesta disciplina.

\bigskip
\hfill* * * * *\hfill\null
\bigskip

\begin{enumerate}[label=\nlabelE]
  
\item Faça o Exercício~3.1-3 de \textbf{CLRS}.  

\item Faça o Problema~3-2 de \textbf{CLRS}.

\item Faça o Exercício M01 Mergesort com menos acessos à memória.  \datedue{1/9/2026}

\item Faça o Exercício M02 Partição de K\&R.  \datedue{1/9/2026}

\item\textbf{(\textit{M})}\label{e:KR} Considere o algoritmo de
  partição de K\&R, como dado em \textsc{Particione($A,p,r$)}.
  Suponha que $A[1\dotdot N]$ seja uma permutação de
  $[N]=\{1,\dots,N\}$, escolhida uniformemente ao acaso.  Ao executar
  \textsc{Particione($A,1,N+1$)}, obtemos duas permutações: uma em
  $A[1\dotdot q)$ e outra em $A[q+1\dotdot N]$.  Prove que a
  permutação em $A[1\dotdot q)$ é uma permutação de $[q-1]$ sem viés,
  isto é, todas as permutações de $[q-1]$ ocorrem com a mesma
  probabilidade em $A[1\dotdot q)$.  Analogamente, prove que a
  permutação em $A[q+1\dotdot N]$ é uma permutação de
  $\{q+1,\dots,N\}$ sem viés.  Prove que as permutações em
  $A[1\dotdot q)$ e $A[q+1\dotdot N]$ são independentes uma da outra.

\item \textbf{(\textit{M})} Repita o Exercício~\ref{e:KR} considerando
  o algoritmo de partição de Sedgewick.

\item\label{e:comp_prob_QS} Considere o algoritmo de partição de K\&R,
  como dado em \textsc{Particione($A,p,r$)}.  Fixe $1\leq a<b\leq N$.
  \begin{enumerate}[label=\rmlabel]
  \item Suponha que $A[1\dotdot N]$ seja uma permutação de
    $[N]=\{1,\dots,N\}$, escolhida uniformemente ao acaso.  Ao
    executar \textsc{Particione($A,1,N+1$)}, uma comparação entre~$a$
    e~$b$ pode ou não ocorrer na Linha~4 de \textsc{Particione}.  Qual
    é a probabilidade de tal comparação acontecer?

  \item Suponha que $A[1\dotdot N]$ seja uma permutação de
    $[N]=\{1,\dots,N\}$.  Seja~$X_{ab}$ o número de comparações que
    são feitas entre~$a$ e~$b$ ao executarmos
    \textsc{Quicksort($A,1,N+1$)}.  Prove que $X_{ab}\in\{0,1\}$.

  \item Suponha que $A[1\dotdot N]$ seja uma permutação de
    $[N]=\{1,\dots,N\}$, escolhida uniformemente ao acaso.  Prove que
    $\PP(X_{ab}=1)=2/(b-a+1)$, onde~$X_{ab}$ é como definido acima.
    \hint{Considere a \textit{primeira} chamada de \textsc{Particione}
      em que \textit{algum} elemento de $\{a,a+1,\dots,b\}$ é o pivô
      da partição.  Note que, se essa chamada for
      \textsc{Particione$(A,p,r)$}, então todos os elementos de
      $\{a,\dots,b\}$ ocorrem em~$A[p,r)$.  O que você sabe sobre a
      ordem dos elementos em~$A[p,r)$?  Por quê?  Basta agora
      usar~(\textit{i}) acima.}
  \end{enumerate}
  
% \item Repita o Exercício~\ref{e:comp_prob_QS} considerando o algoritmo
%   de partição de Sedgewick.

\item Descreva um algoritmo determinístico $O(N\log k)$ para
  determinar um $k$-ésimo menor elemento de uma lista de~$N$ valores.
  \NB{Em exercícios como este, espera-se que você dê um pseudocódigo
    para seu algoritmo, prove sua correção e prove que seu consumo de
    tempo é como exigido.}

\item Temos uma coleção de~$N$ parafusos e~$N$ porcas de tamanhos
  variados.  Sabemos que existe um pareamento entre os~$N$ parafusos e
  as~$N$ porcas de forma que os elementos pareados encaixam-se
  perfeitamente.  Isto é, se um parafuso~$p$ está pareado com uma
  porca~$p'$, então~$p$ e~$p'$ encaixam-se perfeitamente.  Podemos
  chamar tal pareamento de “pareamento completo” ou “pareamento
  perfeito”, pois todos os~$N$ parafusos e todas as~$N$ porcas estão
  pareados.

  Para encontrar um tal pareamento, a única operação que podemos fazer
  é escolher um parafuso~$p$ e uma porca~$p'$ e experimentar.  Há três
  possíveis resultados para esse experimento: (1)~$p$ e~$p'$
  encaixam-se perfeitamente, (2)~$p$ é muito grande para~$p'$, (3)~$p$
  é muito pequeno para~$p'$.  Queremos encontrar um pareamento
  perfeito fazendo “poucos” experimentos como esse.  É fácil ver que
  podemos encontrar um pareamento perfeito executando no máximo~$N^2$
  experimentos.  Queremos algo bem melhor: \textit{sua tarefa é
    encontrar um algoritmo linearítmico $($isto é, $O(N\log N)${}$)$
    para este problema.}  Neste exercício, permitimos algoritmos
  aleatorizados.  Ademais, você pode supor que todos os parafusos têm
  dimensões diferentes e, assim, todas as porcas também têm dimensões
  diferentes (lembre que estamos supondo que há um pareamento
  perfeito). 
  \begin{enumerate}[label=\rmlabel]
  \item Descreva seu algoritmo de forma precisa, fornecendo
    pseudocódigos e quaisquer outros detalhes que tornem sua
    implementação uma tarefa simples.
  \item Prove que seu algoritmo consome tempo~$O(N\log N)$.  Se você
    produzir um algoritmo aleatorizado, basta provar que o consumo de
    tempo \textit{esperado} é~$O(N\log N)$.
  \end{enumerate}
  \datedue{15/9/2026}
  
\item\label{E:10} A análise de complexidade do algoritmo
  \textsc{Select-MoM} visto em sala supõe algo sobre a entrada: sem
  essa hipótese, não é verdade que ele consome tempo~$O(N)$ no pior
  caso.  Descreva um vetor $A[1\dotdot N]$ tal que
  $\textsc{Select-MoM}(A,1,N+1,\lceil N/2\rceil)$ consome
  tempo~$\Omega(N^2)$.  Por que a prova de linearidade falha para essa
  entrada?

\item (Continuação de~\ref{E:10}) Descreva, em linhas gerais, como
  alterar \textsc{Select-MoM} para que ele seja linear para qualquer
  instância~$(A,k)$.  Dê duas soluções.  Justifique suas soluções.
  \hint{Para uma de suas soluções, estude o \textit{$3$-way
      partitioning} de Dijkstra (veja a aula de~18/8/2026).}
  \datedue{15/9/2026}

\item Ao descrevermos o algoritmo de Strassen para multiplicação de
  matrizes em sala, supusemos que estávamos multiplicando duas
  matrizes $n\times n$ com~$n$ potência de~$2$.  Podemos remover esta
  hipótese, simplesmente considerando blocos formados
  por~$\lceil n/2\rceil$ ou~$\lfloor n/2\rfloor$ linhas
  e~$\lceil n/2\rceil$ ou~$\lfloor n/2\rfloor$ colunas?  \NB{Em
    questões dessa forma (com respostas ``sim'' ou ``não''), você
    deve, naturalmente, justificar sua resposta.}

\item Considere o algoritmo de Strassen, como visto em sala, que serve
  para multiplicar matrizes $n\times n$ com~$n$ potência de~$2$.  Como
  podemos usar este algoritmo para implementar um outro algoritmo que
  multiplica matrizes $n\times n$ para qualquer $n\geq1$ com consumo
  de tempo~$O(n^{\lg7})$?

\item \textbf{(PC\footnote{Programming Challenges (Skiena \& Revilla)}
    111105 Cortes de tora)}\enspace Você deve cortar uma tora de
  madeira em vários pedaços.  Você solicitará o serviço à
  \textit{Analog Cutting Machinery} (ACM), que cobra, por corte, um
  valor igual ao comprimento da tora a ser cortada.  A máquina de
  corte dela permite que apenas um corte seja feito por vez.  Se
  quisermos fazer vários cortes, é fácil ver que ordens diferentes
  desses cortes podem levar a preços diferentes.  Por exemplo,
  considere uma tora com~$10$ metros de comprimento, que tem de ser
  cortada a~$2$, $4$ e~$7$ metros de uma mesma extremidade.  Há várias
  possibilidades.  Podemos primeiro fazer o corte dos~$2$ metros,
  depois dos~$4$ e depois dos~$7$.  Tal ordem custa $10+8+6 = 24$,
  porque a primeira tora tinha comprimento~$10$, o pedaço cortado em
  seguida tinha comprimento~$8$ e o último pedaço cortado tinha
  comprimento~$6$.  Se cortássemos na ordem~$4$, depois~$2$,
  depois~$7$, pagaríamos $10 + 4 + 6 = 20$, que é o custo mínimo neste
  exemplo.  Descreva um algoritmo que, dado o comprimento~$L$ da tora
  e~$N$ pontos de corte $0<p_1<\dots<p_N<L$, encontre o custo mínimo
  para executar esses cortes na ACM.  Seu algoritmo deve também
  devolver uma ordem de corte que atinja esse custo.  Quais são os
  consumos de tempo e de espaço de seu algoritmo?  (Espera-se que seu
  algoritmo consuma tempo~$O(N^3)$ e espaço~$O(N^2)$.)
  \datedue{22/9/2026}
  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% Exercícios acrescentados em 2026-10-09 (aulas 6 a 18)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%% Aula 6
\item\label{e:arv-decisao-media} \textbf{(Limite inferior no caso
    médio)}\enspace Considere uma árvore de decisão para
  ordenar~$A[1\dotdot n]$, como vista em sala: cada nó interno é
  rotulado por uma comparação ``$A[i]\leq A[j]$?'' e tem dois filhos,
  correspondentes às respostas ``sim'' e ``não''; cada folha (ou ``nó externo'') é
  rotulada por uma ordem dos elementos de~$A[1\dotdot n]$; e a árvore
  está correta, isto é, para toda entrada com elementos distintos, a
  folha atingida dá a ordem crescente dessa entrada.  Para cada
  entrada~$A$, seja~$X(A)$ o número de comparações feitas com a
  entrada~$A$, isto é, a profundidade da folha atingida por~$A$.
  Suponha que $A[1\dotdot n]$ seja uma permutação de
  $[n]=\{1,\dots,n\}$ escolhida uniformemente ao acaso (cada uma
  das~$n!$ permutações ocorre com probabilidade~$1/n!$), e seja
  $\EE[X]$ o valor esperado de~$X(A)$.
  \begin{enumerate}[label=\rmlabel]
  \item Prove que permutações diferentes atingem folhas diferentes.
  \item Prove que, em qualquer árvore binária, a soma das
    profundidades de quaisquer~$L\geq1$ folhas distintas é pelo
    menos~$L\lg L$.  \hint{A função $f(x)=x\lg x$ é convexa
      em $(0,\infty)$, isto é,
      $f\bigl(\lambda x+(1-\lambda)y\bigr)\leq\lambda f(x)+(1-\lambda)f(y)$
      para quaisquer $x,y>0$ e $0\leq\lambda\leq1$: o gráfico de~$f$
      entre~$x$ e~$y$ fica abaixo do segmento que liga $(x,f(x))$ a
      $(y,f(y))$.  Em particular, $f(x)+f(y)\geq2f\bigl((x+y)/2\bigr)$.}
  \item Conclua que $\EE[X]\geq\lg n!$ e que $\EE[X]=\Omega(n\lg n)$.
  \end{enumerate}
  \NB{Isso mostra que todo algoritmo de ordenação baseado em
    comparações consome tempo~$\Omega(n\lg n)$ não só no pior caso,
    mas também no caso médio.}

%%%% Aula 9
\item\label{e:karatsuba-poli} \textbf{(Karatsuba para
    polinômios)}\enspace Um polinômio de grau menor que~$n$ é dado
  pelo vetor $P[0\dotdot n-1]$ de seus coeficientes:
  $P(x)=\sum_{i=0}^{n-1}P[i]\,x^i$.  O produto de dois tais
  polinômios~$P$ e~$Q$ é o polinômio $R=PQ$ dado pelo vetor
  $R[0\dotdot 2n-2]$, onde $R[k]=\sum_{i+j=k}P[i]\,Q[j]$.  Suponha que
  os coeficientes sejam números (inteiros, reais ou complexos) e que
  cada operação aritmética entre coeficientes consome tempo constante.
  O algoritmo direto faz~$n^2$ multiplicações de coeficientes.
  \begin{enumerate}[label=\rmlabel]
  \item Inspirando-se no algoritmo \textsc{Karatsuba}$(X,Y,n)$ visto
    em sala, escreva um algoritmo
    \textsc{Karatsuba-Poli}$(P,Q,n)$ que devolve~$PQ$.  Prove
    que seu algoritmo está correto.
  \item Seja~$M(n)$ o número de multiplicações de coeficientes que
    \textsc{Karatsuba-Poli}$(P,Q,n)$ faz.  Dê uma recorrência
    para~$M(n)$ e prove que $M(n)=n^{\lg3}$ quando~$n$ é potência
    de~$2$.  Compare~$M(n)$ com~$n^2$ para $n=2^{10}$.
  \item Prove que \textsc{Karatsuba-Poli} pode ser implementado de
    forma a consumir tempo~$O(n^{\lg3})$ para todo~$n\geq1$.
  \item Na linha~7 de \textsc{Karatsuba}, a chamada recursiva é feita
    com $\lceil n/2\rceil+1$ algarismos.  Por que isso é necessário
    para inteiros, mas não para polinômios?
  \end{enumerate}

%%%% Aula 10
\item\label{e:chapas} \textbf{(Corte de chapas)}\enspace Chapas
  retangulares de aço são vendidas em tamanhos inteiros: uma chapa
  $a\times b$ (largura~$a$, altura~$b$) é vendida por~$p[a,b]\geq0$
  reais, onde a tabela~$p[1\dotdot A,1\dotdot B]$ é dada.  Temos uma
  chapa $A\times B$ e podemos cortá-la antes de vender os pedaços.  Um
  \emph{corte de guilhotina} divide uma chapa $a\times b$ em duas
  chapas por meio de um corte reto, de um lado ao outro da chapa,
  paralelo a um dos lados e em posição inteira: obtemos as chapas
  $i\times b$ e $(a-i)\times b$ (corte vertical, $1\leq i<a$), ou as
  chapas $a\times j$ e $a\times(b-j)$ (corte horizontal,
  $1\leq j<b$).  Os pedaços obtidos podem ser cortados novamente da
  mesma forma, e não podem ser girados (as chapas $a\times b$ e
  $b\times a$ podem ter preços diferentes).
  \begin{enumerate}[label=\rmlabel]
  \item Seja~$q[a,b]$ o maior valor de venda que se pode obter de uma
    chapa $a\times b$.  Dê uma recorrência para~$q[a,b]$, análoga à
    recorrência do corte de hastes, e prove que ela está correta.
  \item Escreva um algoritmo de programação dinâmica que calcula
    $q[A,B]$ e que permite listar os cortes de um plano de cortes
    ótimo (como em \textsc{Corta-Haste-Bottom-Up-Completo} e
    \textsc{Lista-Cortes}).  Quais são os consumos de tempo e de
    espaço de seu algoritmo?  (Espera-se tempo~$O(AB(A+B))$ e
    espaço~$O(AB)$.)
  \end{enumerate}

%%%% Aula 11
\item\label{e:parentizacao-geral} \textbf{(Parentização com custo
    geral)}\enspace Suponha que tenhamos uma operação~$*$ entre matrizes
  tal que, se~$X$ é $a\times b$ e~$Y$ é $b\times c$, então~$X*Y$ é uma
  matriz $a\times c$, e calcular~$X*Y$ custa~$f(a,b,c)$, onde~$f$ é
  uma função dada, com valores não negativos, que pode ser calculada
  em tempo constante.  Suponha que~$*$ seja associativa:
  $X*(Y*Z)=(X*Y)*Z$.  Considere uma cadeia $A_1,\dots,A_n$ de
  matrizes em que~$A_i$ é $p_{i-1}\times p_i$, como no problema da
  multiplicação iterada de matrizes.  O custo de uma parentização de
  $A_1*\cdots*A_n$ é a soma dos custos das~$n-1$ operações~$*$ que ela
  executa.
  \begin{enumerate}[label=\rmlabel]
  \item Seja~$m[i,j]$ o custo mínimo de uma parentização de
    $A_i*\cdots*A_j$.  Dê uma recorrência para~$m[i,j]$, prove que ela
    está correta e escreva um algoritmo que consome tempo~$O(n^3)$,
    análogo a \textsc{Matrix-Chain-Order}, que determina~$m[1,n]$ e
    uma parentização ótima.
  \item Suponha que $f(a,b,c)=b^2$.  Prove que todas as parentizações
    de $A_1*\cdots*A_n$ têm o mesmo custo e determine esse custo.
  \item Generalize o item~(\textit{ii}) para $f(a,b,c)=g(b)$, onde~$g$
    é uma função qualquer.
  \end{enumerate}

%%%% Aula 12
\item\label{e:todas-lcs} \textbf{(Todas as sscos máximas)}\enspace
  Sejam $X[1\dotdot m]$ e $Y[1\dotdot n]$ sequências de símbolos de
  um alfabeto~$A$, e seja~$c[i,j]$ o comprimento de uma ssco máxima
  de $X[1\dotdot i]$ e $Y[1\dotdot j]$, como em \textsc{LCS-Length}.
  Vimos em sala como obter \emph{uma} ssco máxima de~$X$ e~$Y$
  (\textsc{Get-LCS}).  Agora queremos listar \emph{todas} as sscos
  máximas de~$X$ e~$Y$, cada uma exatamente uma vez.  Duas sscos são
  consideradas iguais se forem iguais como sequências de símbolos,
  mesmo que ocorram em posições diferentes de~$X$ ou de~$Y$; por
  exemplo, se $X=\mathrm{A\,A}$ e $Y=\mathrm{A}$, há uma única ssco
  máxima, a saber, $\mathrm{A}$.  Sejam~$N$ o número de sscos máximas
  de~$X$ e~$Y$ e $L=c[m,n]$ o comprimento delas.  Suponha que os
  símbolos de~$A$ possam ser usados como índices de vetores (por
  exemplo, $A=\{1,\dots,|A|\}$).
  \begin{enumerate}[label=\rmlabel]
  \item Para $0\leq i\leq m$ e $a\in A$, seja $\mathrm{ult}_X[i,a]$ o
    maior $i'\leq i$ tal que $X[i']=a$ (ou~$0$, se não houver
    tal~$i'$), e defina $\mathrm{ult}_Y[j,a]$ analogamente.  Sejam
    $i$ e~$j$ tais que $k=c[i,j]\geq1$, e sejam $a\in A$,
    $i'=\mathrm{ult}_X[i,a]$ e $j'=\mathrm{ult}_Y[j,a]$.  Prove que,
    se $i'\geq1$, $j'\geq1$ e $c[i'-1,j'-1]=k-1$, então as sscos
    máximas de $X[1\dotdot i]$ e $Y[1\dotdot j]$ que terminam
    em~$a$ são exatamente as sequências~$Wa$, onde~$W$ é uma ssco
    máxima de $X[1\dotdot i'-1]$ e $Y[1\dotdot j'-1]$; caso
    contrário, nenhuma ssco máxima de $X[1\dotdot i]$ e
    $Y[1\dotdot j]$ termina em~$a$.
  \item Escreva um algoritmo que lista todas as sscos máximas de~$X$
    e~$Y$, cada uma exatamente uma vez, e prove que ele está
    correto.  Qual é o consumo de tempo de seu algoritmo?  (Espera-se
    tempo $O(mn+|A|(m+n+NL))$; em particular, $O(mn+NL)$ se~$|A|$ é
    constante.  Note que~$NL$ é o tamanho da saída.)
  \item Mostre que, para todo~$n$ par, existem sequências~$X$ e~$Y$,
    ambas de comprimento~$n$, com~$2^{n/2}$ sscos máximas.  (Assim,
    listar todas as sscos máximas pode consumir tempo exponencial
    em~$n$.)  \NB{O alfabeto~$A$ pode depender de~$n$.}
  \end{enumerate}

\item\label{e:palindromo} \textbf{(Subsequência palindrômica
    máxima)}\enspace Uma sequência~$Z[1\dotdot k]$ é um
  \emph{palíndromo} se $Z[t]=Z[k+1-t]$ para $t=1,\dots,k$.  Dada uma
  sequência~$X[1\dotdot n]$, queremos encontrar uma subsequência
  de~$X$ que seja um palíndromo e tenha comprimento máximo.
  \begin{enumerate}[label=\rmlabel]
  \item Para $1\leq i\leq j\leq n$, seja~$c[i,j]$ o comprimento de uma
    subsequência palindrômica máxima de~$X[i\dotdot j]$, e
    convencione $c[i,i-1]=0$.  Prove que $c[i,i]=1$ e que, para
    $i<j$,
    \[
      c[i,j]=
      \begin{cases}
        c[i+1,j-1]+2 & \text{se $X[i]=X[j]$},\\
        \max\{c[i+1,j],\,c[i,j-1]\} & \text{se $X[i]\neq X[j]$}.
      \end{cases}
    \]
  \item Escreva um algoritmo que consome tempo~$O(n^2)$, calcula
    $c[1,n]$ e devolve uma subsequência palindrômica máxima de~$X$
    (como em \textsc{Get-LCS}).
  \item Seja~$X^R$ a sequência~$X$ invertida, isto é,
    $X^R[t]=X[n+1-t]$.  Prove que o comprimento de uma ssco máxima
    de~$X$ e~$X^R$ é igual a~$c[1,n]$.  Mostre que uma ssco máxima
    de~$X$ e~$X^R$ pode não ser um palíndromo, e explique como obter,
    a partir de uma ssco máxima de~$X$ e~$X^R$, uma subsequência
    palindrômica de~$X$ de mesmo comprimento.
  \end{enumerate}

%%%% Aula 13
\item\label{e:abb-otima-q} \textbf{(ABB ótima com buscas sem
    sucesso)}\enspace Sejam $x_1<\dots<x_n$ as chaves a serem
  armazenadas numa ABB, e convencione $x_0=-\infty$ e
  $x_{n+1}=+\infty$.  Uma ABB para essas chaves tem~$n$ nós internos,
  que contêm as chaves, e~$n+1$ nós externos (os ponteiros nulos); da
  esquerda para a direita, os nós externos são numerados
  $0,1,\dots,n$, e o nó externo~$j$ é onde terminam as buscas sem
  sucesso por valores~$y$ com $x_j<y<x_{j+1}$.  Como em sala, uma
  busca por~$x_i$ faz~$h_i$ comparações, onde~$h_i$ é o número de nós
  no caminho da raiz até~$x_i$; uma busca sem sucesso que termina no
  nó externo~$j$ faz~$h'_j$ comparações, onde~$h'_j$ é o número de
  nós internos no caminho da raiz até o nó externo~$j$.  Suponha que,
  em cada busca, o valor procurado seja~$x_i$ com
  probabilidade~$p_i$ ($1\leq i\leq n$), ou um valor~$y$ com
  $x_j<y<x_{j+1}$ com probabilidade~$q_j$ ($0\leq j\leq n$), onde
  $\sum_{i=1}^np_i+\sum_{j=0}^nq_j=1$.  O custo esperado de uma ABB é
  \[
    \sum_{i=1}^np_ih_i+\sum_{j=0}^nq_jh'_j.
  \]
  \begin{enumerate}[label=\rmlabel]
  \item Para $1\leq i\leq j+1\leq n+1$, seja~$c[i,j]$ o custo mínimo de uma
    ABB para as chaves $x_i,\dots,x_j$ (cujos nós externos são
    $i-1,\dots,j$), onde o custo é definido como acima, mas somando
    apenas sobre essas chaves e esses nós externos, e seja
    $s[i,j]=\sum_{k=i}^jp_k+\sum_{l=i-1}^jq_l$.  Prove que
    $c[i,i-1]=0$ e que, para $i\leq j$,
    \[
      c[i,j]=\min_{i\leq k\leq j}\bigl\{c[i,k-1]+c[k+1,j]\bigr\}+s[i,j].
    \]
  \item Escreva um algoritmo que consome tempo~$O(n^3)$ e devolve uma
    ABB ótima.
  \item Para $i\leq j$, seja $\mathrm{raiz}[i,j]$ o maior~$k$ que
    atinge o mínimo em~(\textit{i}).  Knuth provou que
    $\mathrm{raiz}[i,j-1]\leq\mathrm{raiz}[i,j]\leq\mathrm{raiz}[i+1,j]$
    sempre que $i<j$.  Usando esse fato (sem prová-lo), mostre como
    reduzir o consumo de tempo do seu algoritmo para~$O(n^2)$.
  \end{enumerate}

%%%% Aula 15
\item\label{e:subarvores} \textbf{(Subárvores disjuntas)}\enspace
  Seja~$T$ uma árvore, isto é, um grafo conexo acíclico, e sejam
  $T_1,\dots,T_n$ subárvores de~$T$ (subgrafos conexos de~$T$), cada
  uma dada pela lista de seus vértices.  Queremos encontrar índices
  $i_1<\dots<i_m$, com~$m$ máximo, tais que as subárvores
  $T_{i_1},\dots,T_{i_m}$ são disjuntas duas a duas nos vértices,
  isto é, $V(T_{i_a})\cap V(T_{i_b})=\emptyset$ sempre que $a\neq b$.
  \begin{enumerate}[label=\rmlabel]
  \item Dê um algoritmo para esse problema.
  \item Prove que seu algoritmo está correto.
  \item Qual é o consumo de tempo de seu algoritmo, em função
    de~$|V(T)|$, de~$n$ e de $\sum_i|V(T_i)|$?
  \end{enumerate}
  \hint{Os intervalos do problema dos intervalos disjuntos são as
    subárvores de um caminho.  Enraíze~$T$ em um vértice qualquer.}
  \datedue{23/10/2026}

%%%% Aula 16
\item\label{e:huffman-entropia} \textbf{(Huffman e entropia)}\enspace
  Seja~$A$ um alfabeto com $n\geq2$ símbolos, com ``frequências''
  $f[c]>0$ ($c\in A$) tais que $\sum_{c\in A}f[c]=1$.  Seja
  $w\in A^*$ um texto com~$N$ símbolos, no qual cada símbolo~$c$
  ocorre exatamente $f[c]\,N$ vezes.  Como em sala, para uma árvore de
  código~$T$ para~$A$, escrevemos $d_T(c)$ para a profundidade de~$c$ em~$T$
  (o comprimento do código de~$c$), e $B(T)=\sum_{c\in A}f[c]\,d_T(c)$;
  assim, $w$ codificado com o código dado por~$T$ tem $N\,B(T)$
  bits.  Seja
  \[
    H(f)=\sum_{c\in A}f[c]\lg\frac1{f[c]}
  \]
  a entropia da distribuição~$f$.
  \begin{enumerate}[label=\rmlabel]
  \item Prove que $\sum_{c\in A}2^{-d_T(c)}=1$ para toda árvore de
    código~$T$ para~$A$.
  \item Prove que, se $\ell_c$ ($c\in A$) são inteiros positivos
    com $\sum_{c\in A}2^{-\ell_c}\leq1$, então existe um código
    livre de prefixo cujas palavras têm comprimentos~$\ell_c$
    ($c\in A$).  Conclua que existe uma árvore de código~$T$
    para~$A$ com $d_T(c)\leq\ell_c$ para todo~$c$.
  \item Prove que~$w$ codificado com o código de Huffman para~$f$ tem
    menos que $N(H(f)+1)$ bits.  \hint{Considere
      $\ell_c=\lceil\lg(1/f[c])\rceil$.}
  \item Prove que $B(T)\geq H(f)$ para toda árvore de código~$T$
    para~$A$ e, portanto, que~$w$ codificado com qualquer código
    livre de prefixo tem pelo menos $N\,H(f)$ bits.
    \hint{Estime $H(f)-B(T)$ por cima, escrevendo-a como uma única
      soma, e use que $\ln x\leq x-1$ para todo $x>0$.}
  \item Conclua que o número~$b$ de bits de~$w$ codificado com o código
    de Huffman para~$f$ satisfaz $N\,H(f)\leq b<N(H(f)+1)$.
  \end{enumerate}

%%%% Aula 17
\item\label{e:tarefas-unitarias} \textbf{(Tarefas unitárias com
    prazos)}\enspace Temos~$n$ tarefas, todas com tempo de
  processamento $t_i=1$, e com prazos~$d_i$ inteiros positivos
  ($1\leq i\leq n$).  Como em sala, um escalonamento é uma
  permutação~$\pi$ de $1,\dots,n$, e a tarefa~$\pi[k]$ é executada no
  intervalo de tempo $[k-1,k)$; assim, $f_{\pi[k]}=k$.  Dizemos que a
  tarefa~$i$ é \emph{pontual} em~$\pi$ se $f_i\leq d_i$.  Queremos um
  escalonamento com o maior número possível de tarefas pontuais.
  \begin{enumerate}[label=\rmlabel]
  \item Dê um algoritmo guloso que resolve esse problema em
    tempo~$O(n\lg n)$, e prove que ele está correto.
  \item Mostre que podemos supor que $d_i\leq n$ para todo~$i$, e
    obtenha um algoritmo que consome tempo~$O(n)$.
  \end{enumerate}

%%%% Aula 18
\item\label{e:fila-baldes} \textbf{(Fila de prioridade com chaves
    pequenas)}\enspace Seja $C\geq2$ um inteiro.  Queremos uma fila
  de prioridade~$Q$ cujos elementos são inteiros em $\{1,\dots,n\}$,
  cada elemento~$x$ com uma chave $\mathrm{key}[x]\in\{1,\dots,C\}$,
  com as operações
  \begin{itemize}
  \item \textsc{Insert}$(Q,x,k)$: insere em~$Q$ o elemento~$x$ (que
    não está em~$Q$) com chave~$k$;
  \item \textsc{Extract-Min}$(Q)$: remove de~$Q$ e devolve um elemento
    de chave mínima;
  \item \textsc{Decrease-Key}$(Q,x,k)$: muda a chave do elemento~$x$
    de~$Q$ para $k\leq\mathrm{key}[x]$.
  \end{itemize}
  Mostre como implementar~$Q$ de modo que cada uma dessas operações
  consuma tempo~$O(\lg C)$ e que a criação de uma fila vazia consuma
  tempo~$O(n+C)$.  \hint{Use um vetor de~$C$ listas (``baldes''), uma
    para cada valor de chave, e uma árvore binária completa cujas
    folhas são os baldes.}

\item\label{e:prim-baldes} \textbf{(Prim com custos pequenos)}\enspace
  Seja~$G$ um grafo conexo com~$n$ vértices e~$m$ arestas, com custos
  inteiros $c(uv)\in\{1,\dots,C\}$ nas arestas, onde $C\geq2$.
  Mostre como implementar \textsc{Prim}$(G,c)$ usando a fila do
  Exercício~\ref{e:fila-baldes} de modo que o consumo de tempo seja
  $O(m\lg C+n+C)$.  Note que, em \textsc{Prim}, os valores iniciais
  $\mathrm{key}[v]=\infty$ não estão em $\{1,\dots,C\}$; explique como
  contornar isso.

\item\label{e:todas-lis} \textbf{(Todas as subsequências crescentes
    máximas)}\enspace Seja $c_1,\dots,c_n$ uma sequência de números
  distintos.  Considere o algoritmo \textsc{Patience} visto em sala:
  cada~$c_i$ é empilhado na pilha~$S_j$ mais à esquerda cujo topo é
  maior que~$c_i$ (ou numa nova pilha, se não há tal~$S_j$).  Uma LIS
  de $c_1,\dots,c_n$ é uma subsequência crescente de comprimento
  máximo.
  \begin{enumerate}[label=\rmlabel]
  \item Mostre que, para todo~$n$ par, existe uma sequência de~$n$
    números distintos com~$2^{n/2}$ LISs.  (Assim, listar todas as
    LISs pode consumir tempo exponencial em~$n$.)
  \item Suponha que, ao empilharmos~$c_i$ em~$S_j$, com $j\geq2$,
    guardemos referências para \emph{todos} os elementos que estão
    em~$S_{j-1}$ naquele momento e que são menores que~$c_i$.  Prove
    que esses elementos formam um segmento não vazio no topo
    de~$S_{j-1}$, de modo que basta guardar dois índices, e que isso
    pode ser feito sem alterar o consumo de tempo~$O(n\lg n)$ de
    \textsc{Patience}.
  \item Prove que as LISs de $c_1,\dots,c_n$ são exatamente as
    sequências obtidas começando em um elemento da última pilha não
    vazia e seguindo referências como em~(\textit{ii}) até chegar
    a~$S_1$, e que cada LIS é obtida exatamente uma vez.
    \hint{Prove que~$c_i$ está em~$S_j$ se e somente se~$j$ é o
      comprimento de uma subsequência crescente máxima que termina
      em~$c_i$.}
  \item Dê um algoritmo que conta as LISs de $c_1,\dots,c_n$
    com~$O(n\lg n)$ operações (supondo que operações aritméticas
    consumam tempo constante).
  \item Dê um algoritmo que lista todas as LISs de $c_1,\dots,c_n$ em
    tempo $O(n\lg n+NL)$, onde~$N$ é o número de LISs e~$L$ é o
    comprimento delas.
  \end{enumerate}
  \datedue{23/10/2026}
  
\end{enumerate}
\endgroup
\end{document}

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