Sugestões de exercícios

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

Última atualização: 31/03, 14h24m

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

Bia, Lais e Coelho

Bag, Genéricos e iteradores

Há 4 exercícios em Sacos (PF)

Leiam a seção Perguntas e respostas.

Em Bags, Queues, and Stacks há uma vasta quantidade de exercícios. Vejam:

• Exercises: 2, 3, 13, 42, 45 e 46
• Web Exercises: 25, 28, 54, 57, 59

As seções Q + A (= Perguntas e respostas) de Bags, Queues, and Stacks são bem legais!

Análise amortizada e tabelas redimensionáveis

Há 7 exercícios em Pilhas (PF).

Leiam a seção Perguntas e respostas.

Em Bags, Queues, and Stacks há uma vasta quantidade de exercícios.

Coleção disjunta dinâmica (union-find)

Em Case Study: Union-Find há uma vasta quantidade de exercícios

Vejam:

• Exercises: 8, 10
• Web Exercises: 1, 2, 3, 4, (observação: 7 foi um EP do Yoshi para MAC0121, se a sua classe Percolation foi bem escrita, essa extensão não é difícil), (curiosidade, veja 12)
• Creative Problems: 14 (essa foi a pergunta (do Vitor?) na aula)

As seções Q + A (= Perguntas e respostas) de Case Study: Union-Find são bem legais!

Em particular, a Q+A a seguir está é relaciona ao TCC de Gabriel Russo.

Q. Is there an efficient data structure that supports both insertion and deletion of edges?

A. Yes. However, the best-known fully dynamic data structure for graph connectivity is substantially more complicated than the incremental version we consider. Moreover, it's not as efficient. See Near-optimal fully-dynamic graph connectivity by Mikkel Thorup.

Heaps, heapsort e filas priorizadas

Observação: muitos dos exercícios sugeridos aparecem em ambos, em Filas priorizadas (PF) e em Priority Queues.

Há muitos exercícios bacanas. Alguns sobre a estrutura de heaps, alguns sobre aplicação em vários campos, alguns sobre projeto de estrutura de dados, alguns mais teóricos,Isso tudo da uma pequena amostra de como qualquer ideai, por mais simples que seja, pode ser explorada e explorada e

Em Filas priorizadas (PF) exercícios 1.2, 2.1, 3.1, 3.2, 3.5, 3.6, 3.7, 3.8, 3.10, 3.11, 3.12.

Em Priority Queues há uma vasta quantidade de exercícios Leiam o que diz sobre Practical considerations.

Vejam:

• Exercises: 1, 2, 3, 4, 11, 12, 14, 15, 20, 27, 33
• Creative Problems: 25, 30, 32 (teórico)
• Web Exercises: 1 (análise, teorico), 2, 5 (aplicação), 9, 11 (aplicação em teoria computacional dos números), 14, 15, 17, 18, 19 (indução), 22, 29 (análise experimental), 30, 32

Mergeable heaps

Em construção.

É esperado que pelo menos vocês saibam a ideia como funcionam leftist heaps e que a (uma?) operação básica desse tipo de heaps é intercalação de listas ligadas (merge()).

Tabelas de símbolos

Em Tabelas de símbolos (PF) exercícios 1.1, 1.2, 1.5, 1.9, 1.10 (Depup.java), 4.2,

Leiam a seção Perguntas e respostas.

Em Elementary Symbol Tables há alguns poucos exercícios.

Vejam:

• Exercises: 1, 2, 5, 16, 17, 29 (exemplo de unit test)

Do livros Algorithms de S&W:

3.1.2 Develop a symbol-table implementation ArrayST that uses an (unordered) array as the underlying data structure to implement our basic symbol-table API. (API básica encontrada na seção 3.1)

Solução: ArrayST.java

3.1.3 Develop a symbol-table implementation OrderedSequentialSearchST that uses an ordered linked list as the underlying data structure to implement our ordered symbol-table API.

Solução: OrderedSequentialSearchST.java

3.1.10 Give a trace of the process of inserting the keys E A S Y Q U E S T I O N into an initially empty table using SequentialSearchST . How many compares are involved?

3.1.10+ Repita o exercício anterior usando a heurística move to front.

3.1.11 Give a trace of the process of inserting the keys E A S Y Q U E S T I O N into an initially empty table using BinarySearchST . How many compares are involved?

3.1.13 Which of the symbol-table implementations in this section would you use for an application that does 10^3 put() operations and 10^6 get() operations, randomly intermixed? Justify your answer.

3.1.40 Crossover to binary search. Find the values of N for which binary search in a symbol table of size N becomes 10, 100, and 1,000 times faster than sequential search. Predict the values with analysis and verify them experimentally.

Aleatorização: skip lists

Em construção.

É esperado que pelo menos vocês saibam a ideia e como funcionam skip lists e que a operação básica é busca em listas (rank()).

Árvores binárias

Há alguns exercícios em Árvores binárias de busca (PF). Vejam os exercícios 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.9 (conceito relacionado ao consumo de tempo médio em buscas),
1.10 (solução nos slides). 3.1 (implementação preguiçosa (= lazy) versus ansiosa (= eager).

Análise de desempenho

Em Analysis of Algorithms há vários exercícios

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

• Exercises: 6,
• Creative Problems: 18, 20 (busca binária),
• Web Exercises: 10 (sort()), 22, 29 (Euclides), 32