\input acentos
\hyphenpenalty=500
\tolerance=500
\overfullrule=0pt
\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{MAC324\hfill\bf EXERCÍCIOS\hfill\sl19/6/99}
\bigskip

\medskip
\noindent{\bf Obs.}\enspace 
Nos exercícios com AB, vamos assumir que temos
\begintt
typedef struct STnode* link;
struct STnode { Item item; link l, r; int N; };  /* nó da AB */
static link head, z;        /* pointeiro para raiz e `cauda' */
\endtt

\medskip
\noindent{\bf Outra obs.}\enspace 
Os exercícios abaixo são principalmente conceituais e não envolvem
programação.  Na prova, acho que pedirei uma ou outra codificação, mas
tentarei me concentrar em questões como as desta lista.

\medskip
\noindent{\bf 1.}\enspace Considere o seguinte código: 
\begintt
void sortR(link h)
{ if (h == z) return;
  sortR(h->l); <imprima h->item>; sortR(h->r);
}

void STsort() { sortR(head); } 
\endtt
O que faz uma chamada de {\tt STsort()} em uma AB genérica?  Ilustre
sua resposta em um exemplo também. 

\medskip
\noindent{\bf 2.}\enspace Considere o seguinte código: 
\begintt
link rotR(link h)
  { link x = h->l; h->l = x->r; x->r = h; return x; }

link rotL(link h)
  { link x = h->r; h->r = x->l; x->l = h; return x; }
\endtt
O que fazem as chamadas {\tt rotR(h)} e {\tt rotL(h)} genericamente?
Ilustre sua resposta em exemplos específicos também.

\medskip
\noindent{\bf 3. }[12.72 de Sedgewick]\enspace Lembre que o campo {\tt
N} de um nó {\tt h} é usado para manter o número de nós na subárvore
de raiz~{\tt h}.  Considere as funções {\tt rotR()} e {\tt rotL()}
acima e note que elas não estão atualizando este campo
apropriadamente.  Altere-as de forma que isto seja feito.

\medskip
\noindent{\bf 4.}\enspace Considere o seguinte código: 
\begintt
Item selectR(link h, int k)
  { int t = h->l->N;
    if (h == z) return NULLitem;
    if (t > k) return selectR(h->l, k);
    if (t < k) return selectR(h->r, k-t-1);
    return h->item;
  }

Item STselect(int k) { return selectR(head, k); } 
\endtt
O que faz a chamada {\tt STselect(k)}? 

\medskip
\noindent{\bf 5.}\enspace Considere agora o seguinte código: 
\begintt
link partR(link h, int k)
  { int t = h->l->N; 
    if (t > k) { h->l = partR(h->l, k); h = rotR(h); }
    if (t < k) { h->r = partR(h->r, k-t-1); h = rotL(h); }
    return h;
  }
\endtt
O que faz a chamada {\tt partR(head, k)}?  

\medskip
\noindent{\bf 6.}\enspace Continuando com a questão anterior,
considere a seguinte função:
\begintt
link balanceR(link h)
  { if (h->N < 2) return h;
    h = partR(h, h->N/2);
    h->l = balanceR(h->l); 
    h->r = balanceR(h->r);
    return h;
  }
\endtt
O que faz a chamada {\tt partR(head)}?  

\medskip
\noindent{\bf 7.} [13.8 de Sedgewick]\enspace
Suponha que inserimos, nesta ordem, as chaves 
\begintt
E A S Y Q U T I O N
\endtt
em uma ABB incialmente vazia.  Suponha que usamos inserção aleatória
({\tt prog13.2}).  Suponha também que a função aleatória que é usada é
um tanto estrenha, de modo que a rotina de inserção acaba executando
inserção na raiz toda vez que um item é inserido em uma árvore com um
número ímpar de elementos.  Desenhe as ABBs resultantes após cada
inserção. 

\medskip
\noindent{\bf 8.} [13.25 de Sedgewick]\enspace
Suponha que inserimos, nesta ordem, as chaves 
\begintt
E A S Y Q U T I O N
\endtt
em uma árvore inicialmente vazia, usando inserção splay.  Desenhe a
árvore após cada inserção.  

\medskip
\noindent{\bf 9.} [13.27 de Sedgewick]\enspace
Implemente {\tt STsearch()} com splaying.

\medskip
\noindent{\bf 10.} [13.39 de Sedgewick]\enspace
Suponha que inserimos, nesta ordem, as chaves 
\begintt
E A S Y Q U T I O N
\endtt
em uma árvore 2-3-4 inicialmente vazia.  Desenhe a árvore após cada
inserção.   

\medskip
\noindent{\bf 11.}\enspace
Suponha que usamos árvores rubro-negras para implementar árvores
2-3-4.  Qual é a altura máxima de uma árvore rubro-negra que contém
{\tt N} ítens?  Justifique sua resposta.

\medskip
\noindent{\bf 12.} [13.48 de Sedgewick]\enspace
Suponha que usamos árvores rubro-negras para implementar árvores
2-3-4.  Suponha que inserimos, nesta ordem, as chaves
\begintt
E A S Y Q U T I O N
\endtt
em nossa árvore.  Desenhe a árvore após cada inserção.

\medskip
\noindent{\bf 13.}\enspace Considere a seguinte função de hashing: 
\begintt
int hash(char *v, int M)
  { int h = 0, a = 128;
    for (; *v != '\0'; v++) h = (a*h + *v) % M;
    return h;
  }
\endtt
Suponha que o tamanho~{\tt M} da tabela que está sendo usada é {\tt
1024}.  O usuário percebe que muitas colisões ocorrem quando esta
função de hashing é utilizada para processar as palavras que ocorrem
em um dado texto (isto é, o espalhamento esperado não ocorre).  Você
teria uma explicação para este fenômeno?  Em particular, quando ocorre
desta função devolver o mesmo valor para chaves distintas?  

\medskip
\noindent{\bf 14.} [14.16 de Sedgewick]\enspace
Suponha que usamos uma tabela de hashing com resolução de colisões por
encadeamento.  Suponha que inserimos {\tt N} ítens em nossa tabela,
que está inicialmente vazia.  No pior caso (isto é, tendo muito azar
com a função de hashing), quanto tempo pode demorar este processo?
Suponha agora que resolvemos manter as nossas listas em ordem
crescente de chaves; quanto tempo pode demorar este processo?  (Nesta
questão, estamos interessados em saber se o tempo é proporcional a
{\tt N}, proporcional a ${\tt N}^2$, proporcional a ${\tt N}\log {\tt
N}$, etc).

\medskip
\noindent{\bf 15.} [14.17 de Sedgewick]\enspace
Suponha que estamos utilizando uma tabela de hashing com {\tt M}
entradas, com resolução de colisões por encadeamento (as {\tt M}
listas não são mantidas em ordem).  Suponha que usamos a função de
hashing que devolve $11k\bmod {\tt M}$ quando a entrada é a $k$-ésima
letra do alfabeto (por exemplo, {\tt C} corresponde a $k=3$).  Suponha
que inserimos em uma tabela iniclamente vazia, nesta ordem, as chaves
\begintt
E A S Y Q U T I O N
\endtt
onde ${\tt M}=5$.  Desenhe diagramas que ilustram este processo de
inserção.  

\medskip
\noindent{\bf 16.} [14.18 de Sedgewick]\enspace
Continuando com a questão anterior, desenhe a configuração final da
tabela agora supondo que mantemos as nossas listas em ordem crescente
das chaves.  A sua resposta depende da ordem de inserção das chaves?

\medskip
\noindent{\bf 17.}\enspace Considere o seguinte código: 
\begintt
void STdelete(Item item)
  { int j, i = hash(key(item), M); Item v;
    while (!null(i))
      if eq(key(item), key(st[i])) break; 
      else i = (i+1) % M;
    if (null(i)) return;
    st[i] = NULLitem; N--;
    for (j = i+1; !null(j); j = (j+1) % M, N--)
      { v = st[j]; st[j] = NULLitem; STinsert(v); }
  }
\endtt
A função acima implementa a remoção de um item de uma tabela de
hashing, onde usamos probing linear para a resolução de colisões.
O que ocorreria se omitíssemos o {\tt for} desta função?  Por que a
nossa tabela deixaria de funcionar?  

\medskip
\noindent{\bf 18.} [14.24 de Sedgewick]\enspace
Quanto tempo pode demorar, no pior caso, a inserção de {\tt N} ítens
em uma tabela de hashing incialmente vazia, se usamos resolução de
colisões por probing linear?

\medskip
\noindent{\bf 19.} [14.25 de Sedgewick]\enspace
Suponha que estamos utilizando uma tabela de hashing com {\tt M}
entradas, com resolução de colisões por probing linear.  Suponha que
usamos a função de hashing que devolve $11k\bmod {\tt M}$ quando a
entrada é a $k$-ésima letra do alfabeto (por exemplo, {\tt C}
corresponde a $k=3$).  Suponha que inserimos, nesta ordem, as chaves 
\begintt
E A S Y Q U T I O N
\endtt
em uma tabela inicialmente vazia, onde ${\tt M}=16$.  Desenhe
diagramas que ilustram este processo de inserção. 

\medskip
\noindent{\bf 20.} [14.26 de Sedgewick]\enspace
Faça a questão anterior com ${\tt M}=10$.

\medskip
\noindent{\bf 21.} [9.1 de Sedgewick]\enspace
Este é um exercício sobre filas de prioridade.  Na seqüência 
\begintt
P R I O * R * * I * T * Y * * * Q U E * * * U * E
\endtt
uma letra significa a inserção daquela letra em uma fila e um
asterisco significa a remoção do item de maior prioridade desta fila.
Qual é a seqüência de chaves devolvida pelas 12 operações de remoção
acima?

\medskip
\noindent{\bf 22.} [9.3 e 9.4 de Sedgewick]\enspace
Explique como usar uma fila de prioridades para implementar uma
pilha.  Explique como usar uma fila de prioridades para implementar
uma fila. 

\medskip
\noindent{\bf 23.} [9.22 de Sedgewick]\enspace
Suponha que a fila de prioridades da Questão~21 é implementada
usando-se heaps.  Desenhe os 25 heaps resultantes após cada uma das 25
operações daquela questão.

\medskip
\noindent{\bf 24.}\enspace
O algoritmo heapsort demora tempo $O(n\log n)$ para ordenar um vetor
de $n$ ítens.  Dê um argumento preciso para justificar esta asserção.

\medskip
\noindent{\bf 25.}\enspace Esta questão baseia-se na rotina de
partição do quicksort.  Considere o seguinte código: 
\begintt
select(Item a[], int l, int r, int k)
  { int i;
    if (r <= l) return;
    i = partition(a, l, r);
    if (i > k) select(a, l, i-1, k);
    if (i < k) select(a, i+1, r, k);
  }
\endtt
Qual é o efeito da chamada {\tt selection(a, 0, N-1, N/2)}?

\medskip
\noindent{\bf 26.}\enspace Considere o seguinte código: 
\begintt
select(Item a[], int l, int r, int k)
{ while (r > l) {
    int i = partition(a, l, r);
    if (i >= k) r = i-1;
    if (i <= k) l = i+1;
  } 
}
\endtt
Qual é o efeito da chamada {\tt selection(a, 0, N-1, N/2)}?

\bye

