\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{MAC122\hfill\bf EXERCÍCIOS\hfill\sl27/11/2003}
\bigskip

\medskip
\noindent{\bf Obs.}\enspace 
Nos exercícios com listas ligadas, vamos supor que temos
\begintt
  typedef struct node *link;
  struct node { Item item; link next; }
\endtt

\medskip
\noindent{\bf 1.} [3.36 do Sedgewick]\enspace
Escreva uma função que rearranja os elementos de uma lista dada, pondo
todos os elementos que ocorrem nas posições pares antes de todos os
elementos de ocorrem nas posições ímpares.  Você deve preservar a
ordem relativa dos elementos pares entre si, e a ordem relativa dos
elementos ímpares entre si.

\medskip
\noindent{\bf 2.} [4.6 do Sedgewick]\enspace
Este é um exercício sobre pilhas.  Na seqüência
\begintt
E A S * Y * Q U E * * * S T * * * I O * N * * *  
\endtt
uma letra significa {\it empilhe\/} e um asterisco {\it desempilhe}.
Qual é a seqüência de letras devolvida pelos {\it desempilhe\/}? 

\medskip
\noindent{\bf 3.} [4.7 do Sedgewick]\enspace
Continuemos usando a notação do exercício anterior.  Diga como devemos
inserir asteriscos na seqüência {\tt E A S Y} para que os {\it
desempilhe\/} devolva as seguintes seqüências: ({\it i\/}) {\tt E A S
Y}, ({\it ii\/}) {\tt Y S A E}, ({\it iii\/}) {\tt A S Y E}, ({\it
iv\/}) {\tt A Y S E}, ({\it v\/}) {\tt E Y A S}.  Note que nem sempre
podemos obter a saída desejada; nestes casos, argumente por que a dada
saída não pode ser obtida desta forma.

\medskip
\noindent{\bf 4.} [4.9 do Sedgewick]\enspace
Converta a expressão
\begintt
( 5 * ( ( 9 * 8 ) + ( 7 * ( 4 + 6 ) ) ) )
\endtt
para a notação pósfixa e para a notação infixa.

\medskip
\noindent{\bf 5.} [4.31 do Sedgewick]\enspace
Este é um exercício sobre filas.  Na seqüência
\begintt
E A S * Y * Q U E * * * S T * * * I O * N * * * 
\endtt
uma letra significa inserção no fim da fila e um asterisco significa
remoção do começo da fila.  Qual é a seqüência de letras devolvida
por esta seqüência de operações em nossa fila?

\medskip
\noindent{\bf 6.} [O problema das panquecas]\enspace
Suponha que temos, por exemplo, a seqüencia de números
\begintt
  8 2 3 5 1 4 9 7 6 0
\endtt
Imagine que esta seqüência indica uma pilha de panquecas de 10
tamanhos distintos, empilhadas de forma que a menor está no fundo da
pilha, a maior é a quarta panqueca a partir do fundo da pilha, a
segunda maior está no topo, etc.  As únicas operações permitidas são
inverter um segmento inicial desta seqüência.  Portanto, existem 9
operações não-triviais para a pilha acima; uma delas produz, por
exemplo,
\begintt
  5 3 2 8 1 4 9 7 6 0
\endtt
Podemos chamar esta operação deste exemplo de `operação número 4', já
que invertemos a ordem das 4 panquecas do topo.  O problema é o
seguinte: dados um inteiro positivo {\tt n} e uma permutação dos
inteiros não-negativos menores do que {\tt n}, determinar uma
seqüência de operações (permitidas) que resultam na seqüência
\begintt
  0 1 2 ... n - 1
\endtt
Isto é, com as panquecas em ordem crescente, do topo para o fundo.
Escreva uma função de protótipo 
\begintt
  void imprima_solucao(int n, int panq[]);
\endtt
para resolver este problema.

\medskip
\noindent{\bf 7.} [5.11 do Sedgewick]\enspace
Escreva um programa recursivo que converte uma expressão em notação
infixa em notação pósfixa.

\medskip
\noindent{\bf 8.} [5.14 do Sedgewick]\enspace
Escreva uma função recursiva que remove o último elemento de uma lista
ligada. 

\medskip
\noindent{\bf 9.} [5.17 do Sedgewick]\enspace
Escreva uma função recursiva de protótipo
\begintt
  Item max_el(link h);
\endtt
que recebe um ponteiro para o começo de uma lista ligada (sem cabeça e
sem cauda) e que devolve a maior chave (isto é, campo {\tt item})
presente na lista, onde assumimos que {\tt Item} é o tipo {\tt int}. 

\medskip
\noindent{\bf 10.}\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 11.} [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} itens 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 12.} [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 13.} [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 14.} [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 15.} [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 16.} [9.22 de Sedgewick]\enspace
Suponha que a fila de prioridades da Questão~14 é implementada
usando-se heaps.  Desenhe os 25 heaps resultantes após cada uma das 25
operações daquela questão.

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

\medskip
\noindent{\bf 18.}\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 19.}\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

