%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo TeX para                                                   %
%                                                                    %
% Prova 2 de MAC338 Análise de Algoritmos                            %
% BCC, 1o. semestre de 2000                                          %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Wednesday 21 Jun 2000 08:23:54am BRT yoshi@rebutosa>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\input acentos
\hyphenpenalty=500
\tolerance=500
\overfullrule=0pt
\nopagenumbers
\font\sc=cmcsc10

\catcode`@=11 % borrow the private macros of PLAIN (with care)
% (now Appendix E resumes again)
% macros for verbatim scanning
\chardef\other=12
\def\ttverbatim{\begingroup
  \catcode`\\=\other
  \catcode`\{=\other
  \catcode`\}=\other
  \catcode`\$=\other
  \catcode`\&=\other
  \catcode`\#=\other
  \catcode`\%=\other
  \catcode`\~=\other
  \catcode`\_=\other
  \catcode`\^=\other
  \obeyspaces \obeylines \tt}

\outer\def\begintt{$$\let\par=\endgraf \ttverbatim \parskip=\z@
  \catcode`\|=0 \rightskip-5pc \ttfinish}
{\catcode`\|=0 |catcode`|\=\other % | is temporary escape character
  |obeylines % end of line is active
  |obeyspaces|global|let =| % spaces are active
  |gdef|ttfinish#1^^M#2\endtt{#1|vbox{#2}|endgroup$$}}

\centerline{MAC338\hfill\bf PROVA 2\hfill\sl20/6/2000}
\bigskip

\medskip
\noindent{{\sl Duração da prova\/}: 2 horas}

% \medskip
% \noindent{\bf Obs.}\enspace 
% Nos exercícios com listas ligadas, vamos assumir que temos
% \begintt
%   typedef struct node *link;
%   struct node { Item item; link next; };
% \endtt
% Ademais, nos exercícios com árvores binárias, vamos assumir que temos
% \begintt
%   typedef struct Tnode *link;
%   struct Tnode { Item item; link l, r; };
% \endtt
% O tipo {\tt Item} depende de cada questão.
% Fortemente sugiro que você faça de 3 a 4 questões.

\medskip
\noindent{\bf 1.} [3 pontos]\enspace
Considere a seguinte implementação do algoritmo de ordenação por inserçao.
\begintt
void insertion(Item a[], int l, int r)
  { int i;
    for (i = l+1; i <= r; i++) compexch(a[l], a[i]); 
    for (i = l+2; i <= r; i++)
      { int j = i; Item v = a[i]; 
        while (less(v, a[j-1]))
          { a[j] = a[j-1]; j--; }
        a[j] = v; 
      } 
  }
\endtt
\itemitem{({\it i\/})} O primeiro {\tt for} coloca um elemento mínimo do vetor
dado na posição {\tt a[l]}.  Suponha que omitimos este {\tt for} na
implementação acima e que incializamos {\tt i} no segundo {\tt for} com {\tt
l+1}.  Esta nova implementação funciona?  Justifique.

\itemitem{({\it ii\/})} Explique a vantagem de se colocar um elemento mínimo
do vetor dado em {\tt a[l]}.

\itemitem{({\it iii\/})} A partir deste item, você deve supor que {\tt a[]}
contém os elementos~$\{0,\dots,n-1\}$, em alguma ordem.  Uma {\it inversão\/}
no vetor {\tt a[]} é um par~$(i,j)$ com $i<j$ e ${\tt a[{\it i}]}>{\tt
a[{\it j}]}$.  Suponha que $n=7$ e que ${\tt a[{\it i\/}]}=3i\bmod 7$.
Determine o número de inversões neste vetor {\tt a[]}.

\itemitem{({\it iv\/})} Dizemos que um elemento ${\tt a[{\it i\/}]}$ está
{\it envolvido\/} em~$q$ inversões se o numero de pares~$(j,i)$ que são inversões
em~{\tt a[]} é~$q$.  Se~${\tt a[{\it i\/}]}$ está envolvido em~$q$
inversões, quantas vezes a atribuição {\tt a[j] = a[j-1]} é executada no
procedimento acima?  Quantas vezes a comparação {\tt less(v, a[j-1])} é feita?  

\itemitem{({\it v\/})} O {\it deslocamento\/} de um elemento~$i$ ($0\leq i<n$)
em {\tt a[]} é a quantidade $|j-i|$, onde~$j$ é tal que~${\tt a[{\it
j\/}]}=i$.  Isto é, o deslocamento de um elemento é a diferença entre a
posição em que ele se encontra e a posição em que ele ficará ao ordenarmos o
vetor.  Suponha que o deslocamento de todo elemento~$i$ ($0\leq i<n$) é de no
máximo~$m$ em uma dada instância {\tt a[]}.  Mostre que o número de inversões
em que pode estar envolvido um elemento ${\tt a[{\it i\/}]}$ é de no
máximo~$2m-1$.

\itemitem{({\it vi\/})} Prove que o tempo de execução da chamada {\tt
insertion(a,0,n-1)} em uma instância {\tt a[]} como descrito em~({\it v\/})
é~$O(mn)$.  Em particular, se~$m$ é uma constante, ordenamos {\tt a[]} em
tempo linear em~$n$.

\medskip
\noindent{\bf 2.} [3 pontos]\enspace
Considere a seguinte versão iterativa (não-recursiva) do quicksort.
\begintt
#define push2(A, B)  push(B); push(A);
void quicksort(Item a[], int l, int r)
  { int i;
    stackinit(); push2(l, r);
    while (!stackempty())
      { l = pop(); r = pop(); 
        if (r <= l) continue;
        i = partition(a, l, r);
        if (i-l > r-i) { push2(l, i-1); push2(i+1, r); }
        else { push2(i+1, r); push2(l, i-1); }
      }
  }
\endtt
\itemitem{({\it i\/})} Ao particionarmos um vetor dado em duas partes para as
chamadas recursivas, qual das partes é ordenado primeiro na implementação
acima? 

\let\:=\colon
\itemitem{({\it ii\/})} Seja~$t(n)$ o número máximo de pares de
elementos~{\tt(l,r)} que a pilha conterá quando executamos {\tt
quicksort(a,0,n-1)}.  Mostre que~$t(0)=t(1)=1$ e que
$$
t(n)\leq\max\big\{\max\{t(a)+1,\,t(b)\}\:\;
                  a+b=n-1\hbox{ e }0\leq a\leq b\big\}
$$
para todo~$n\geq2$.

\itemitem{({\it iii\/})} Considere a seqüência de números~$s_n$ ($n\geq0$)
dada pela recorrência~$s_0=s_1=1$ e~$s_n=s_{\lfloor n/2\rfloor}+1$
para~$n\geq2$.  Faça uma tabela com os valores de~$s_n$ para valores pequenos
de~$n$.

\itemitem{({\it iv\/})} Baseado na tabela em~({\it iii\/}), intua uma fórmula
fechada para~$s_n$.  Prove esta fórmula por indução em~$n$.

\itemitem{({\it v\/})} Prove por indução em~$n$ que~$t(n)\leq s_n$ para
todo~$n\geq0$. 

\itemitem{({{\it vi\/}})} Suponha agora que trocamos {\tt i-l > r-i} por {\tt
i-l <= r-i} no procedimento acima.  Dê, para cada~$n$, uma instância de
tamanho~$n$ para esta variante do procedimento acima que força o uso de mais
que uma quantidade logarítmica de espaço para a pilha.  Quanto espaço é
necessário para a pilha em suas instâncias?

\medskip
\noindent{\bf 3.} [3 pontos]\enspace
Suponha que temos~$k$ listas de inteiros, cada uma delas ordenadas em ordem
crescente.  Suponha que o número total de inteiros que temos é~$n$; isto é, a
soma dos números de elementos nas lista é~$n$.  Suponha agora que queremos
obter uma {\it única lista\/} com estes~$n$ inteiros em ordem crescente.
Descreva uma estrutura de dados que permita obter esta nova lista em
tempo~$O(k+n\log k)$.  [Não dê os detalhes de implementação; diga, em detalhe,
quais estruturas usar e como elas devem ser usadas---uma boa forma de
responder esta questão é dar uma descrição de sua solução em palavras e então
dar um pseudocódigo.]

\medskip
\noindent{\bf 4.} [3 pontos]\enspace
Considere a seguinte função de partição de Kernighan e Pike, dado no livro
{\it The Practice of Programming}. 
\begintt
int partition(Item a[], int l, int r)
  { int i, last; Item v = a[r];
    last = r;
    for (i=r-1; i>=l; i--) {
      if (less(v, a[i]))
        { --last; exch(a[i], a[last]); }
    }
    exch(a[last], a[r]);
    return last;
  }
\endtt

Nesta questão, você deve supor que {\tt a[]} contém os
elementos~$\{0,\dots,n-1\}$, em alguma ordem.

\itemitem{({\it i\/})} Quantas vezes a troca {\tt exch(a[i], a[last])} é
executada quando~${\tt a[r]}=k$?

\itemitem{({\it ii\/})} Suponha agora que a entrada {\tt a[]} contém uma
permutação de $\{0,\dots,n-1\}$, com todas as permutações equiprováveis.
Mostre que o número esperado de trocas {\tt exch(a[i], a[last])} que serão
executadas é~$(n-1)/2$.

Considere agora a função de partição de Sedgewick abaixo.
\begintt
int partition(Item a[], int l, int r)
  { int i = l-1, j = r; Item v = a[r];
    for (;;)
      { while (less(a[++i], v)) ;
        while (less(v, a[--j])) if (j == l) break;
        if (i >= j) break;
        exch(a[i], a[j]);
      }
    exch(a[i], a[r]);
    return i;
  }
\endtt

\itemitem{({\it i\/})} Qual é o número total de comparaçãos que fazemos dos
elementos de {\tt a[]} com {\tt v}?  (Isto é, número de comparações {\tt
less(a[++i], v)} mais o número de comparações {\tt less(v, a[--j])}.)

\itemitem{({\it ii\/})} Suponha agora que ${\tt a[r]}=k$.  Seja~$q$ o
número índices~$i$ ($0\leq i<k$) para os quais temos ${\tt a[{\it i\/}]}\geq
k$.  Quantas vezes executamos a troca {\tt exch(a[i], a[j])}?

\itemitem{({\it iii\/})} Suponha agora que a entrada {\tt a[]} contém uma
permutação de $\{0,\dots,n-1\}$, com todas as permutações equiprováveis.  Qual
é o valor esperado de~$q$ do item~({\it ii\/}), {\it supondo que ${\tt
a[r]}=k$\/}? 

\itemitem{({\it iv\/})} Determine o número esperado de execuções da troca {\tt
exch(a[i], a[j])}, supondo novamente que a entrada {\tt a[]} contém uma
permutação de $\{0,\dots,n-1\}$, com todas as permutações equiprováveis.
[Este valor é por volta de $n/6$.]

\bye



