Sumários
Treaps e tabelas de dispersão
14 abril 2014, 09:30 • Alexandre Francisco
Análise de treaps randomizados (continuação): valor esperado para a profundidade; número esperado de rotações; custo esperado para as operações de inserção, pesquisa, e remoção. Tabelas e funções de dispersão: motivação; revisões; exemplos.
Estruturas de dados
11 abril 2014, 12:30 • Alexandre Francisco
Estruturas de dados, treaps aleatórios, e Mulmuley games. Exercícios 8.4, 8.6 e 8.7, problema 8.12, do livro "Randomized Algorithms".
Treaps
11 abril 2014, 11:00 • Alexandre Francisco
Treaps randomizados. Exemplos. Análise de treaps randomizados: Mulmuley games.
Estruturas de dados
7 abril 2014, 09:30 • Alexandre Francisco
Fundamentos das estruturas de dados. Revisões e exemplos: árvores binárias de pesquisa; amontoados. Treaps e treaps randomizados: unicidade e propriedades.
Técnicas probabilísticas e apoio ao projecto
4 abril 2014, 12:30 • Alexandre Francisco
Problema dos aniversários. Chernoff bounds, exemplos e exercícios de aplicação. Apoio ao projecto: métodos para determinar cortes mínimos; técnicas de implementação.