\documentclass[pdf,colorBG,12pt]{article}

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

\newcommand{\ph}{\phantom}
\newcommand{\Particione}{\mbox{P{\small ARTICIONE}}}
\newcommand{\Quicksort}{\mbox{Q{\small UICKSORT}}}
\newcommand{\Mergesort}{\mbox{M{\small ERGESORT}}}

\newcommand{\Oh}{\mathrm{O}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Pseudocode
\newcommand{\larr}{\leftarrow}
\newcommand{\se}{\textbf{se}} 
\newcommand{\iif}{\textbf{if}} 
\newcommand{\entao}{\textbf{então}} 
\newcommand{\tthen}{\textbf{then}} 
\newcommand{\senao}{\textbf{senão}} 
\newcommand{\eelse}{\textbf{else}} 
\newcommand{\enquanto}{\textbf{enquanto}} 
\newcommand{\escolha}{\textbf{escolha}} 
\newcommand{\wwhile}{\textbf{while}} 
\newcommand{\para}{\textbf{para}}
\newcommand{\cada}{\textbf{cada}} 
\newcommand{\for}{\textbf{for}} 
\newcommand{\ate}{\textbf{até}} 
\newcommand{\tto}{\textbf{to}} 
\newcommand{\decrescendoate}{\textbf{decrescendo até}} 
\newcommand{\repita}{\textbf{repita}} 
\newcommand{\ateque}{\textbf{até que}} 
\newcommand{\faca}{\textbf{faça}} 
\newcommand{\leia}{\textbf{leia}} 
\newcommand{\ddo}{\textbf{do}} 
\newcommand{\e}{\textbf{e}} 
\newcommand{\aand}{\textbf{and}} 
\newcommand{\ou}{\textbf{ou}} 
\newcommand{\oor}{\textbf{or}} 
\newcommand{\pare}{\textbf{pare}} 
\newcommand{\devolva}{\textbf{devolva}} 
\newcommand{\return}{\textbf{return}} 

\newenvironment{pseudoc}
         {\begin{list}%
                {}%
                {%
                 \sffamily%
                 \setlength{\partopsep}{1ex}%
                 \setlength{\topsep}{1ex}%
                 \setlength{\leftmargin}{\parindent}%
                 \setlength{\parsep}{0.5ex}%
                }%
          \item}%
         {\end{list}%
         }
\newenvironment{pseudocode}%
         {\begin{pseudoc}%
          \textbf{\textrm{Algoritmo}}\hspace{0.7ex}\ignorespaces%
         }%
         {\end{pseudoc}}

%% Pascal %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newenvironment{pascal}%
         {\begin{list}%
                {}%
                {%
                 \setlength{\partopsep}{5mm}%
                 \setlength{\topsep}{0mm}%
                 \setlength{\parsep}{0mm}%
                 \setlength{\leftmargin}{8mm}% era 10mm
                }%
          \item}%
         {\end{list}}
\newenvironment{pascalsmall}% small, with more parsep
         {\small%
          \begin{list}%
                {}%
                {%
                 \setlength{\partopsep}{5mm}%
                 \setlength{\topsep}{0mm}%
                 \setlength{\parsep}{1.5mm}%
                 \setlength{\leftmargin}{8mm}% era 10mm
                }%
          \item}%
         {\end{list}%
          \normalsize}
\newenvironment{pascalnomargin}%
         {\begin{list}%
                {}%
                {%
                 \setlength{\partopsep}{5mm}%
                 \setlength{\topsep}{0mm}%
                 \setlength{\parsep}{0mm}%
                 \setlength{\leftmargin}{0mm}%
                }%
          \item}%
         {\end{list}}
\newenvironment{pascalnomarginsmall}% small, with more parsep
         {\small%
          \begin{list}%
                {}%
                {%
                 \setlength{\partopsep}{5mm}%
                 \setlength{\topsep}{0mm}%
                 \setlength{\parsep}{2mm}%
                 \setlength{\leftmargin}{0mm}%
                }%
          \item}%
         {\end{list}%
          \normalsize}
\newcommand{\x}{\hspace*{6mm}}
\newcommand{\xx}{\hspace*{15mm}}
\newcommand{\xxx}{\hspace*{24mm}}
\newcommand{\xxxx}{\hspace*{32mm}}
\newcommand{\xxxxx}{\hspace*{40mm}}
\newcommand{\xxxxxx}{\hspace*{48mm}}
\newcommand{\xxxxxxx}{\hspace*{56mm}}
\newcommand{\xxxxxxxx}{\hspace*{64mm}}

%\newcommand{\x}{\phantom{9}}
%\newcommand{\xx}{\phantom{99}}
\newlength{\digit}
\settowidth{\digit}{0}
\renewcommand{\d}{\hspace{2.5mm}}
\newlength{\smalldigit}
\settowidth{\smalldigit}{\small 9}
\newcommand{\sd}{\hspace{\smalldigit}}
\newlength{\tinydigit}
\settowidth{\tinydigit}{\tiny 9}
\newcommand{\td}{\hspace{\tinydigit}}

\pagestyle{empty}
\setlength{\textwidth}{16cm}
\setlength{\textheight}{24cm}
\setlength{\oddsidemargin}{0cm}
\setlength{\topmargin}{-.5cm}

\newcommand{\N}{\mbox{{\bf N}}}
\newcommand{\Z}{\mbox{{\bf Z}}}
\newcommand{\R}{\mbox{{\bf R}}}
\newcommand{\sse}{\Longleftrightarrow}
\newcommand{\floor}[1]{\lfloor{#1}\rfloor}
\newcommand{\ceil} [1]{\lceil{#1}\rceil}
\newcommand{\tdots}{\,.\,.\,} % in place of \ldots

\def\risonho{{$\bigcirc\!\!\!\!\!\lower.02cm\hbox{\vbox{\offinterlineskip\hbox{$\>\!..$}\vskip.07cm\hbox{$\scriptscriptstyle\smile$}}}$}}
\def\tristonho{{$\bigcirc\!\!\!\!\!\lower.02cm\hbox{\vbox{\offinterlineskip\hbox{$\>\!..$}\vskip.07cm\hbox{$\scriptscriptstyle\frown$}}}$}}

\sloppy

\begin{document}

\begin{center}
{\large
{\bf 
MAC 5711 - Análise de Algoritmos \\
}
}
{\em Departamento de Ciência da Computação} \\
Segundo semestre de 2018 \\

\vspace{5mm}
{\large
{\bf Lista 3} \\
}
\end{center}

\vspace{5mm}

\begin{enumerate}
%% \item Seja $T(n)$ definida pela recorrência
%% \begin{eqnarray*}
%% T(0) & = & 1 \\
%% T(1) & = & 1 \\
%% T(n) & = & \max_{0 \leq k \leq n-1} \{T(k) + T(n-k-1) \} +
%%          n \ \ \mbox{para   $n=2,3,4,\ldots$}
%% \end{eqnarray*}
%% Mostre que $T(n) \geq n^2/2$ para todo $n \geq 0$. 

\item Seja $M(n)$ definida pela recorrência
\begin{eqnarray*}
M(0) & = & 1 \\
M(1) & = & 1 \\
M(n) & = & \min_{0 \leq k \leq n-1} \{M(k) + M(n-k-1) \} +
         n \ \ \mbox{para   $n=2,3,4,\ldots$} 
\end{eqnarray*}
Mostre que $M(n) \geq \frac12(n+1)\lg(n+1)$ para todo $n \geq 0$. 

%\item Qual é o consumo de espaço do \Quicksort{} no pior caso? 

\item Quando um algoritmo recursivo tem como último comando executado,
  em algum de seus casos, uma chamada recursiva, tal chamada é
  denominada \emph{recursão de cauda} (\emph{tail recursion}). 
  Um exemplo de recursão de cauda acontece no \Quicksort{}. 

  Toda recursão de cauda pode ser substituída por uma repetição. 
  No caso do \Quicksort, obtemos o seguinte: 
\begin{pascal}
\Quicksort{}\,$(A, p, r)$
   
1\x \enquanto{} $p < r$

2\xx $q \larr \Particione{}\,(A,p,r)$

3\xx $\Quicksort{}\,(A, p, q-1)$

4\xx $p \larr q+1$
\end{pascal}

Mostre como essa idéia pode ser usada (de uma maneira mais esperta)
para melhorar significativamente o consumo de espaço no pior caso do
\Quicksort{}.

\newcommand{\phentao}{\phantom{\entao}} 
\newcommand{\phsenao}{\phantom{\senao}} 
\newcommand{\segmaior}{\mbox{\emph{segundo}\_\emph{maior}}}
\newlength{\tsts}
\settowidth{\tsts}{9}
\newcommand{\ts}{\hspace{\tsts}}

\item Considere o seguinte algoritmo que calcula o maior e o menor elemento
de um vetor $v[1 \tdots n]$ com elementos distintos. 

\newcommand{\maior}{\mbox{\emph{maior}}}
\newcommand{\menor}{\mbox{\emph{menor}}}

{\small 
\begin{pseudocode}{MaiorMenor $(v,n)$}

\ts1. $\maior \larr v[1]$ 

\ts2. $\menor \larr v[1]$

\ts3. \para{} $i \larr 2$ \ate{} $n$ \faca{}

\ts4. \x \se{} $v[i] > \maior$

\ts5. \xx \entao{} $\maior \larr v[i]$

\ts6. \xx \senao{} \se{} $v[i] < \menor$

\ts7. \xx \phsenao{} \x \entao{} $\menor \larr v[i]$

\ts8. \devolva{} \maior, \menor
\end{pseudocode}
}

Suponha que a entrada do algoritmo é uma permutação de 1 a $n$
escolhida uniformemente dentre todas as permutações de 1 a $n$. 

Qual é o número esperado de comparações executadas na linha 6 do
algoritmo? Qual é o número esperado de atribuições efetuadas na
linha~7 do algoritmo? 

\item Considere o seguinte algoritmo que determina o segundo maior
  elemento de um vetor $v[1 \tdots n]$ com $n \ge 2$ números positivos
  distintos.


{\small 
\begin{pseudocode}{Máximo $(v,n)$}

\ts1. $maior \larr 0$ 

\ts2. $\segmaior \larr 0$  

\ts3. \para{} $i \larr 1$ \ate{} $n$ \faca{} 

\ts4. \x \se{} $v[i] > maior$

\ts5. \xx \entao{} $\segmaior \larr maior$

\ts6. \xx \phentao{} $maior \larr v[i]$

\ts7. \xx \senao{} \se{} $v[i] > \segmaior$

\ts8. \xx \phsenao{} \x \entao{} $\segmaior \larr v[i]$
  
\ts9. \devolva{} $\segmaior$

\end{pseudocode}
}

Suponha que $v$ é uma permutação de $1$ a $n$ escolhida ao acaso
dentre todas as permutações de $1$ a $n$, de acordo com a distribuição
uniforme de probabilidade. Seja $X$ o número de vezes que a variável
\segmaior\ é alterada (ou seja, o número de execuções das linhas 5
e 8 do algoritmo) numa chamada de Máximo$(v,n)$. Note que $X$ é uma
variável aleatória. Calcule o valor esperado de~$X$. 


  \item {\bf (CLRS 8.4-3)} Seja $X$ uma variável aleatória que é igual ao
número de caras em duas jogadas de uma moeda justa. Quanto vale $E[X^2]$?
Quanto vale $E[X]^2$?

  \item Tanto \Mergesort quanto \Quicksort foram vistos para ordenar um
vetor. Considere agora o caso em que os dados estão montados numa lista
(simplesmente) ligada. É importante não piorar a complexidade dos algoritmos;
deveriam ser mais eficientes que criar um vetor de apontadores para as
células, ordenar esse vetor conforme o conteúdo das células, e usar esse vetor
para reordenar as células.  Cada algoritmo traz desafios diferentes:
\begin{itemize}
    \item \Mergesort: intercalar duas listas ordenadas é fácil.  Mas como
  dividir uma lista em duas do mesmo tamnho de forma eficiente?  Para vetores,
  essa divisão era trivial; é preciso tomar cuidado para não aumentar a
  complexidade do algoritmo.  O gasto de memória deve ser constante, a
  menos da pilha de recursão.

    \item \Quicksort: Aqui o desafio é fazer o particionamento de forma estável
  e concatenar sublistas rapidamente.  Tente fazer também a forma aleatorizada.
\end{itemize}
Em cada caso, justifique a complexidade.

Em princípio, uma célula da lista tem um campo \texttt{Info} do
\texttt{TipoOrd} e um campo \texttt{Next} usado para apontar outra célula. Mas
evite usar referências de baixo nível, onde der.  Assuma a existência de
métodos ``óbvios'', como pendurar uma célula em outra, percorrer a lista até
que algo aconteça, etc.
\end{enumerate}

\end{document}


%%% Local Variables:
%%% mode: latex
%%% TeX-master: "l3"
%%% End:
