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

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
\usepackage{xspace}
\usepackage{pifont}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{color}
\usepackage{fancybox}

\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
\newcommand{\conj}[2]{\ensuremath{\{#1\,|\;#2\}}}

\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 5}} \\
\vspace{4ex}
\textbf{Sempre que apresentar um algoritmo, justifique sua corretude e estime a complexidade.
}
\end{center}

% \vspace{5mm}
%\hrulefill

\begin{enumerate}
    \item (KT 3.4) Um grupo de lepidopterologistas conjectura que as
  borboletas numa certa região são todas de duas espécies, A e B.  Só que é
  difícil, olhando para uma, identificar a espécie.  O que eles fazem, com
  \(n\) borboletas, é considerar alguns (\(m\)) pares e marcar \textbf{mesma},
  \textbf{diferente} e \textbf{duvidosa}.  O problema é descobrir se os pares
  marcados são consistentes com a hipótese de existirem duas espécies.  Dê um
  algoritmo \(O(n+m)\) para isso; descreva no mais alto nível que puder, em
  termos de outros algoritmos conhecidos.
    \item (KT 3.8) (Também CLRS 22.2-7) Para um dado grafo, seu
  \emph{diâmetro} é a maior distância entre pares de vértices. Ou seja,
  \(\mathrm{diam}(G)=\max\conj{\delta(u,v)}{u,v\in G.V}\). Por outro lado, a
  \emph{distância média} \(\bar\delta(G)\) é, como diz o nome, a média das
  distâncias entre todos os pares de vértices distintos de \(G\).  Assim,
  \[
      \bar\delta(G)=\frac{\sum_{\{u,v\} \subseteq G.V}\delta(u,v)}{\binom{n}{2}}.
    \]
    \begin{enumerate}
        \item Descreva algoritmos para calcular esses dois parâmetros.
        \item Alguém apresentou a conjectura de que existe uma constante \(K\)
      tal que, para todo grafo \(G\) vale\[
          \frac{\mathrm{diam}(G)}{\bar\delta(G)}\leq K.
        \]
        Decida se essa conjectura é verdadeira ou falsa, e prove sua afirmativa.
    \end{enumerate}
      
      \item (KT 3.10) Dê um algoritmo eficiente que computa, dados vértices
    \(u,v\) em um grafo dirigido, o \textbf{número} de caminhos mínimos de
    \(u\) a \(v\).  Note que esse número pode ser exponencial, assim listar os
    caminhos está fora de questão.  Por outro lado, você pode supor que a sua
    linguagem de programação trabalha com números inteiros com número
    ilimitado de dígitos.
    
      \item (CLRS 22.2-6) Dê um exemplo de um grafo dirigido, e subgrafo que é
    uma árvore enraizada com a propriedade de para todo vértice, o caminho
    simples na árvore da raíz até ele é um caminho mínimo no grafo, mas, essa
    árvore não é devolvida por uma BFS, não importa qual seja o iterador pela
    estrela de cada vértice.  Em particular, se usar listas de adjacência, não
    existe ordenação nessas listas que faça essa árvore ser de BFS.

    
      \item A \emph{cintura} de um grafo (não orientado) é o tamanho do menor
    ciclo que ele contem.  Dê um algoritmo eficiente para determinar a
    cintura.
 \end{enumerate}

\end{document}


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