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

\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 4} \\
% (Valor: 40 pontos)\footnote{Você só precisa entregar as questões
% que tem valor marcado, mac claro que deve fazer todos \risonho} \\
}
% \vspace{5mm}
% Devolução: 17 de março de 1999
\end{center}

% \vspace{5mm}
%\hrulefill

\begin{enumerate}

% Quicksort 

    \item Escreva uma função que recebe um vetor com $n$ letras A's e B's e,
  por meio de trocas, move todos os A's para o início do vetor.  Sua função
  deve consumir tempo~$\Oh(n)$.

    \item Escreva uma função que rearranje um vetor $v[p \tdots r]$ de
  inteiros de modo que tenhamos $v[p \tdots j-1] \leq 0$ e $v[j \ldots r] > 0$
  para algum $j$ em $p \tdots r+1$.  Faz sentido exigir que $j$ esteja em
  $p \tdots r$?  Procure fazer uma função rápida que não use vetor auxiliar.
  Repita o exercício depois de trocar $v[j \tdots r] > 0$ por
  $v[j \tdots r] \geq 0$.  Faz sentido exigir que $v[j]$ seja $0$?

% Medianas e k-ésimo mínimo

    \item Para esta questão, vamos dizer que a \emph{mediana} de um vetor
  $A[p \tdots r]$ com número inteiros é o valor que ficaria na posição
  $A[\floor{(p+r)/2}]$ depois que o vetor $A[p \tdots r]$ fosse ordenado.

  Sejam $X[1 \tdots n]$ e $Y[1 \tdots n]$ dois vetores, cada um
  contendo $n$ números ordenados. Escreva um algoritmo $\Oh(\lg n)$ para
  encontrar uma das medianas de todos os $2n$ elementos nos vetores $X$ e~$Y$,
  ou seja, o que seria a mediana da concatenação de  $X$ com $Y$.
  

\item Considere o seguinte algoritmo, que não faz nada de útil:
\begin{pascal}
\textsc{Algo} $(n)$

1\x se $n\leq1$ 

2\xx então devolva $1$

3\x para $i\leftarrow1$ até $8$ faça 

4\xx $z\leftarrow\textsc{Algo}(\lfloor n/2\rfloor)$

5\xx para $i\leftarrow1$ até $n^3$ faça 

6\xxx $z\leftarrow0$
\end{pascal}
\begin{itemize}
\item[(1)\ ] Seja $T(n)$ o número de vezes que a atribuição~``$z\leftarrow0$'' é executada.  Escreva uma recorrência que define~$T(n)$.
\item[(2)\ ] Mostre que $T(n)$ é $\Omega(n^3\log n)$.
\item[(3)\ ] Troque ``8'' por ``7'' no algoritmo e mostre diretamente que $T(n)$ é $O(n^3)$.
\end{itemize}

% Heapsort

    \item Suponha que $v[1 \tdots m]$ é um heap. Suponha que $i < j$ e
  $v[i] < v[j]$. Se os valores de $v[i]$ e $v[j]$ forem trocados,
  $v[1 \tdots m]$ continuará sendo um heap?  Repita o exercício sob a hipótese
  $v[i] > v[j]$.


% Consumo assintótico

    \item Nem mencionei busca binária em aula, porque suponho que todos
  conhecem.  Qual a diferença de consumo de tempo entre uma busca binária em
  um vetor com~$n$ elementos e uma busca binária em um vetor com $n^2$
  elementos?

    \item Descreva um algoritmo que, dado um vetor com \(n\) inteiros
  positivos, e a informação de que todos são menores que \(n^3\), ordena esse
  vetor em tempo linear em \(n\).
  
\end{enumerate}

\end{document}


%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:
