\documentclass[11pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}
\usepackage{pifont}
\setlength{\textheight}{8.5in}
\setlength{\textwidth}{6.5in}
\setlength{\evensidemargin}{0pt}
\setlength{\oddsidemargin}{0pt}
\setlength{\topmargin}{-30pt}


\begin{document}
\noindent
{\footnotesize {\sc MAC--IME--USP}} \hfill {\footnotesize {\sc Carlos Eduardo Ferreira}}

\vspace{-1mm}
\hfill {\footnotesize {\sc Sala 297A Tel.: 818 6140}}

\vspace{-1mm}
\hfill {\footnotesize {\sc e-mail} cef@ime.usp.br}

\vspace{1cm}

\begin{center}
{\large\bf MAC 5710 -- Estruturas de Dados}
\end{center}

\begin{center}
Segnuda Lista de Exerc\'\i cios -- Entrega: 19 de abril
\end{center}

\begin{enumerate}
\item 
Escreva um algoritmo que recebe uma lista linear duplamente ligada e inverte
essa lista, alterando somente os campos dos apontadores e sem usar estruturas
auxiliares.  

\item Considere a lista ligada dada pela declaração abaixo. 
\begin{verbatim}
public class LL
{ 
   Celula inicio; 
   .
   .
}

public class Celula
{
   Elemento info;
   Celula   prox;
   .
   .
}
\end{verbatim}
a. Escreva um método {\tt void OrdenaBubble()} da classe LL 
 que ordena a lista ligada usando o método Bubblesort com aviso de troca. \\
b. Faça uma análise do seu método, dizendo qual o número máximo de comparações
 e trocas feitas em função do número de elementos da lista ($n$). Diga também
 qual é a complexidade de uma operação de troca na sua implementação.

\item 
Faça um programa que utiliza uma pilha e reconhece se uma palavra sobre um
alfabeto $\Sigma = \{a,b,c\}$ pertence ao seguinte conjunto: 
\[ \{ w \in \Sigma^* : w = xc^+x^r, \mbox{ onde } x \in \{a,b\}^*\}\]
onde, 
\begin{itemize}
\item[] $A^*$ : conjunto de todas as palavras formadas com as letras de $A$;
\item[] $l^+ = \{l, ll, lll, llll, \dots\}$
\item[] $x^r$ é o reverso da palavra $x$, ou seja, $x$ lida de trás para a
frente. 
\end{itemize}

\item 
Simule a execução do algoritmo de Ordenação Topológica visto em sala de aula,
para construir a estrutura de dados e fazer uma ordenação topológica para a
seguinte relação: 

\[ 4<3 \; \; \; 2 < 5 \; \; \; 7 < 8 \; \; \; 5 < 7 \; \; \; 3 < 8 \; \; \; 4
< 2\]

\item 
Mostre que um heap com $n$ elementos tem altura $\lfloor \log n \rfloor$. 
Dica: use indução em $n$. 
\end{enumerate}
\end{document}