Oi Wander,

Haverá uma lista de exercicios recomendados para a prova, ?

Sim.
Estou preparando uma.

Ainda preciso corrigir a P1...

Sugestões de exercícios

Atenção Esta lista está em construção

Última atualização: 10/05, 11h45m

O website do livro tem implementações completas e uma vasta quantidade de exercícios muito bacanas, inclusive com respostas.

Não deixem de ler as seções Q+A do algs4 e Perguntas e respostas do PF.

Alguns dos exercícios listados a seguir não são pensados para a prova, mas sim para o conhecimento de vocês: non scholæ sed vitæ discimus.

Bia, Lais e Coelho

BSTs

Em 3.2 Binary Search Trees vejam os exercícios listados abaixo:

Não deixem de ver a animação que está na página 3.2 Binary Search Trees.

• Exercises: 3, 6, 10, 13
• Creative Problems: 25, 31 (EP09), 32 (EP09), 33 (EP09)
• Web Exercises: 1 (dá hora!), 2 (vejam notas de aula e writeTrie() e `readTrie() do algoritmo de Huffman), 3, 4, 6, 7, 8

Em Árvores binárias de busca (PF) exercícios 2.1, 2.2, 3.3, 4.1 (= Creative Problem 25), 5.3

Em BSTs: operações adicionais (PF) exercícios 1.2 (EP09), 3.4 e 3.5 (= Web Exercises 2).

STs 2-3 e rubro-negras

Em 3.3 Balanced Search Trees vejam os exercícios listados abaixo.

Não deixem de ver as animações que estão na página.

• Exercises: 9, 14 (vejam ainimação), 15 (vejam animação)*,
• Creative Problems: 33, 38 (teórico, interessante), 39 (EP09), 40 (EP09), 41 (EP09)
• Web Exercises: 4, 5, 6 (put() parece bem legal)

Em Árvores 2-3 (PF) exercícios 1.1, 2.1, 2.2, 2.3

Em BSTs rubro-negras (PF) exercícios 1.6, 3.1, 3.2, 3.3, 4.1, 6.5, 7.1

Hashing

Em 3.4 Hash Tables vejam os exercícios listados abaixo.

Não deixem de ler a seção Q+A

• Exercises: 5, 24
• Creative Problems: 32, 33,
• Web Exercises: 1 (baita ideia, acho que essa é a essência do algoritmo de Ranbin-Karp para busca de padrões), 2, 3 (implementação de equals()), 4 (imprime null, null, null; decisão de projeto; key não é clonada; em Python key deve ser imutável), 5, 6, 7 (MD5, SHA-xxx, Dropbox; ver exercício 13), 10, 11 (gperf - generate a perfect hash function from a key set),

Em Hashing (PF) exercícios 2.1, 2.3 (em hash perfeito a ST deve ser estática: pares key-vals são armazenados de uma só vez na ST e a ST não pode ser alterada), 3.4, 4.1, 4.2, 4.4, 5.2, 5.3, 6.2

(R-way) Tries e tries ternárias

Em 5.2 Tries

• Exercises: 1, 4 (document similarity), 5 (spell checking), 8 (inverted index of web), 15 (substring matches), 20 (entropy), 21 (longest prefix)
• Creative Problems:
• Web Exercises:

Em Tries (árvores digitais) (PF) exercícios 1.3, 1.8, 3.1, 3.2, 4.1, 4.2, 4.3, 5.2, 6.3 (operações que envolvem ordem), 6.4 (contagem de substrings de comprimento L), 6.5, 6.6

Aplicações de STs

Em 3.5 Searching Applications vejam

• Exercises:
• Creative Problems: 20 (concordance), 23 (sparse matrices)
• Web Exercises: 2 (set intersection and union), 10 (LRU cache), 15 (Mutable string), 19 (Unix kernels for managing a set of virtual memory areas), 20 (internet peer cache). 22 (arithmetic expression interpreter).

Em Aplicações de TSs (PF) exercícios 1.1 (implementação de SET), 1.2 (implementação de SET), 1.3 (implementação de SET), 2.1 (Verificador ortográfico), 2.1 (Filtro de repetidos)

Compressão de dados

Em 5.5 Data Compression

• Exercises: 1, 2, 3, 4, 9, 10, 12 (interessante), 16, 17, 18, 36, 38
• Creative Problems:
• Web Exercises:

Em Compressão de dados (PF) exercícios 1.1

Em Algoritmo de Huffman para compressão de dados (PF) exercícios 1.1, 1.2, 2.1, 3.1, 3.4 (o Wander perguntou isso na aula), 3.5, 3.6 (= Exercises 16), 3.9 (= Exercises 9), 3.12, 3.14, 5.1, 5.3