\documentclass[12pt]{article}

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

\pagestyle{empty}
\setlength{\textwidth}{15cm}
\setlength{\textheight}{24cm}
\setlength{\oddsidemargin}{0cm}
\setlength{\topmargin}{-1.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
\newcommand{\Oh}{\mathrm{O}}

\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 2} \\
% (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}

\begin{enumerate}
\item Resolva as recorrências abaixo. 
\begin{enumerate}
\item $T(n) = 2T(\floor{n/2})+\Theta(n^2)$
\item $T(n) = 8T(\floor{n/2})+\Theta(n^2)$
\item $T(n) = 2T(\floor{n/2})+\Theta(n^3)$
\item $T(n) = 7T(\floor{n/3})+\Theta(n^2)$
\item $T(n) = T(\floor{9n/10})+\Theta(n)$
\end{enumerate}

% Questão 13 do Neapolitan e Naimipour.
\item Escreva um algoritmo que ordena uma lista de $n$ itens dividindo-a em três sublistas de aproximadamente $n/3$ itens, ordenando cada sublista
  recursivamente e intercalando as três sublistas ordenadas. Analise seu algoritmo concluindo qual é o seu consumo de tempo.
  
\item Seja $X[1 \tdots n]$ um vetor de inteiros e $i$ e $j$ dois índices distintos de $X$, ou seja, $i$ e $j$ são inteiros entre $1$ e $n$. Dizemos
  que o par $(i,j)$ é uma \emph{inversão} de $X$ se $i<j$ e $X[i]>X[j]$. Escreva um algoritmo $\Oh(n \lg n)$ que devolva o número de inversões em um
  vetor $X$, onde $n$ é o número de elementos em $X$.
  
% \item Seja $X[1 \tdots n]$ um vetor de inteiros e $i$ e $j$ dois índices
%   distintos de $X$, ou seja, $i$ e $j$ são inteiros entre $1$ e $n$. Dizemos
%   que o par $(i,j)$ é uma \emph{grande inversão} de $X$ se $i<j$ e 
%   $X[i]>2X[j]$. Escreva um algoritmo $\Oh(n \lg n)$ que devolva o número de
%   grandes inversões em um vetor $X$, onde $n$ é o número de elementos em $X$.

\item Descreva um algoritmo que, dados inteiros \(n\) e \(k\), juntamente com \(k\) listas ordenadas que em conjunto tenham \(n\) registros, produza
  uma única lista ordenada contendo todos os registros dessas listas (isto é, faça uma \emph{intercalação}).  O seu algoritmo deve ter complexidade
  \(\Oh(n\lg k)\).  Note que isto se transforma em \(\Oh(n\lg n)\) no caso de \(n\) listas de \(1\) elemento, e em \(\Oh(n)\) se só houver duas listas
  (no total com \(n\) elementos).
  
\item Considere a seqüência de vetores $A_k[1\tdots 2^k], A_{k-1}[1\tdots 2^{k-1}],\ldots, A_1[1\tdots 2^1]$, e $A_0[1\tdots 2^0].$ Suponha que cada
  um dos vetores é crescente.  Queremos reunir, por meio de sucessivas operações de intercalação (=~\emph{merge}), o conteúdo dos vetores
  $A_0,\ldots,A_k$ em um único vetor crescente $B[1\tdots n]$, onde $n=2^{k+1}-1$.  Escreva um algoritmo que faça isso em $\Oh(n)$ unidades de
  tempo. Use como subrotina o \textsc{Intercale} visto em aula.

\end{enumerate}

\end{document}


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