Familiarizar estudantes com estruturas de dados amplamente utilizadas no cotidiano que não são estudadas em disciplinas usuais. Produzir uma biblioteca com implementações da maioria das estruturas de dados estudadas.
LCA, estruturas de dados temporais, cinéticas, sucintas, árvores de segmentos, otimalidade dinâmica, árvores splay, grafos dinâmicos.
Serão escolhidos tópicos da seguinte lista: 1. Ancestral comum mais próximo, ancestral de nível, árvores de segmentos. 2. Estruturas de dados temporais: persistência e retroatividade. 3. Estruturas de dados cinéticas. 4. Conjectura da otimalidade dinâmica. 5. Conexidade em grafos dinâmicos. 6. Busca de padrão em textos gigantes. 7. Estruturas de dados sucintas. 8. Hierarquia de memória.
Bibliografia Básica: 1. Yan S. Couto, Algoritmos em Sequências, Trabalho de Conclusão de Curso, IME-USP, 2016. 2. Yan S. Couto, Estrutura de Dados Persistentes, Dissertação de Mestrado, IME-USP, 2019. 3. Erik D. Demaine, John Iacono, and Stefan Langerman. Retroactive Data Structures, Transactions on Algorithms, Volume 3, Issue 2, May 2007, Article No. 13. 4. Dan Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. EBLSchweitzer. Cambridge University Press, 1997. 5. Gabriel de Russo e Carmo, O Problema da Conectividade Dinâmica em Grafos, Trabalho de Conclusão de Curso, IME-USP, 2018. Bibliografia Complementar: 1. Peter Brass. Advanced Data Structures, Cambridge University Press, 2008. 2. James R. Driscoll, Neil Sarnak, Daniel D. Sleator, and Robert E. Tarjan. Making data structures persistent. Journal of Computer and System Sciences, 38(1):86–124, 1989. 3. Donald Knuth, The Art of Computer Programming, Sorting and Searching, Vol. 3, Third Edition, Reading, Massachusetts: AddisonWesley, 2011. 4. Dinesh P. Mehta and Sartaj Sahni (Editors). Handbook on Data Structures and Applications, Chapman & Hall/CRC, 2004. 5. Pat Morin, Open Data Structures: An Introduction, UBC Press; 31st ed. edition (September 19, 2013).