MAC323 - Estruturas de Dados

1o. Semestre de 2008

Sinopse das aulas

• Fevereiro
  1. (Aula 0) 26/2/2008 Discussão inicial sobre a disciplina. Veja informações gerais sobre esta edição [PS | PDF]. O problema da conexidade ("union-find"), RS 1.2 e 1.3 (isto é, Seções 1.2 e 1.3 do Sedgewick)

  2. (Aula 1) 28/2/2008 O problema da conexidade, continuação. Anúncio do EP1 [PDF]. Notação assintótica

• Março
  1. (Aula 2) 4/3/2008 A estrutura interface/implementação/cliente. Exemplos: média e desvio padrão de uma seqüência de números; distância entre pares de pontos aleatórios no quadrado unitário (RS 3.0, 3.1, e 3.2)

  2. (Aula 3) 6/3/2008 O problema da cobertura exata. Descrição formal e exemplos. O problema dos pentaminós de Scott

  3. (Aula 4) 11/3/2008 O problema da cobertura exata. Continuação. Aplicação: Sudoku. Você pode achar esta página útil. O problema da cobertura generalizada. O problema das N rainhas

  4. (Aula 5) 13/3/2008 O algoritmo X de Knuth e ponteiros dançantes. Veja o artigo original de Knuth

  5. 18/3/2008 Semana Santa: Recesso escolar

  6. 20/3/2008 Semana Santa: Recesso escolar

  7. (Aula 6) 25/3/2008 Discussão do EP2 (coloração de grafos através da cobertura exata generalizada---como obter todas as colorações próprias de um grafo com um dado número de cores através do algoritmo X?). O enunciado do EP2 será divulgado em breve. Tipos abstratos de dados. Pilhas (interface STACK.h (prog. 4.1) e um cliente: prog4.2.c). Implementações de pilhas: com vetores (prog.4.4.c) e com listas ligadas (prog4.5.c). Filas (interface QUEUE.h (prog. 4.9) e um cliente: q_client.c). Implementações de filas: com listas ligadas (prog.4.10.c) e com vetores (prog4.11.c).

  8. (Aula 7) 27/3/2008 Tipos de primeira classe. Fila como um tipo abstrato de primeira classe (interface: QUEUE1st.h e um cliente: prog4.19.c). Uma implementação: prog4.20.c. Tabelas de símbolos

• Abril
  1. (Aula 8) 1/4/2008 Tabelas de símbolos. Interface (ST.h). Implementações elementares: vetor indexado pelas chaves (prog12.3.c), vetor ordenado (prog12.4.c [busca seqüencial]), lista ligada não-ordenada (prog12.5.c). Implementações com vetores não-ordenados ou listas ordenadas: ficam como exercícios (rotineiros). Busca binária (prog12.6.c). Árvores binárias (ABs) e árvores binárias de busca (ABBs). Veja este diretório; em particular, veja este texto (Notes.pdf).

  2. (Aula 9) 3/4/2008 Tabelas de símbolos com ABBs. Implementação: prog12.7.c. Ordenação com uma ABB: prog12.8.c. Inserção em uma ABB sem recursão: prog12.9.c

  3. 8/3/2008 Professor no LATIN 2008: Não haverá aula ("break adiantado")

  4. 10/3/2008 Professor no LATIN 2008: Não haverá aula ("break adiantado")

  5. (Aula 10) 15/4/2008 Rotações de ABBs: prog12.11.c. Inserção de um elemento na raiz de uma ABB: prog12.12.c. Seleção em ABBs: prog12.13.c. Partição de uma ABB: prog12.14.c. Remoção de uma ABB: prog12.15.c. União de duas ABBs: prog12.16.c.

  6. 17/4/2008 (FISL)

  7. (Aula 11) 22/4/2008 Árvores balanceadas. Balanceamento explícito: prog13.1.c. ABBs Aleatorizadas (ABBAs). ABBs aleatorizadas (ABBAs) constituem talvez a forma mais simples de se obter ABBs balanceadas. Para se entender o fundamento dessas árvores, é importante entender árvores de busca aleatórias (veja o texto Notes.pdf; veja também este diretório). Inserção aleatória: prog13.2.c. União de ABBAs: prog13.3.c. Remoção de uma ABBA: basta alterarmos o algoritmo da remoção de uma ABB (prog12.15.c), colocando o código do prog13.4.c.

     Árvores 2-3-4. Seção 13.3 de RS

  8. (Aula 12) 24/4/2008 Revisão para a Prova 1

  9. (Aula 13) 29/4/2008 Prova 1

• Maio
  1. 1/5/2008 Dia do Trabalho: Recesso escolar

  2. (Aula 14) 6/5/2008 Revisão de árvores 2-3-4 e introdução às árvores rubro-negras (ARB). A versão de ARB que estudaremos é muito recente: veremos as árvores rubro-negras esquerdistas (ARBE) (left-leaning red-black trees (LLRB trees)). Veja as transparências de Sedgewick: versão apresentada no encontro AofA 2008, International Conference on the Analysis of Algorithms (abril de 2008, Maresias, SP) e versão apresentada no encontro Data Structures (fevereiro de 2008, Dagstuhl, Alemanha). [Versões locais: Maresias e Dagstuhl] Veremos a versão de Maresias, que é mais simples e melhor que a versão de Dagstuhl. Ademais, esta versão é melhor e mais simples que a versão de ARB no livro de Sedgewick (Seção 13.4).

  3. (Aula 15) 8/5/2008 Árvores rubro-negras esquerdistas (cont.)

  4. (Aula 16) 13/5/2008 Árvores rubro-negras esquerdistas (cont.)

  5. (Aula 17) 15/5/2008 Skip-lists. Busca (prog13.7.c), inicialização (prog13.8.c), inserção (prog13.9.c), remoção (prog13.10.c)

  6. (Aula 18) 20/5/2008 Skip-lists (cont.)

  7. 22/5/2008 Corpus Christi: Recesso escolar

  8. 27/5/2008 ("Congresso da USP")

  9. 29/5/2008 ("Congresso da USP")

• Junho
  1. (Aula 19) 3/6/2008 Tabelas de hashing. Funções de hashing (prog14.1.c, prog14.2.c). Resolução de colisões por encadeamento: prog14.3.c

  2. 5/6/2008 Não houve aula (professor no AMS-SBM Joint International Meeting, 4 a 7 de 2008, IMPA, Rio de Janeiro)

  3. (Aula 20) 10/6/2008 Tabelas de hashing. Resolução de colisões por probing linear (prog14.4.c, prog14.5.c) e hashing duplo (prog14.6.c). Tabelas de hashing dinâmicas (prog14.7.c)

  4. (Aula 21) 12/6/2008 Tries. Busca (prog15.2.c) e inserção (prog15.3.c) em tries

  5. 17/6/2008 (Não houve aula; prazo de entrega de EP3 próximo (20/6))

  6. (Aula 22) 19/6/2008 Tries R-ários e ternary search tries (TSTs). Busca e inserção em uma TST de existência (prog15.8.c). Lista de exercícios de preparação para a P2

  7. (Aula 23) 24/6/2008 Prova 2

  8. (Aula 24) 26/6/2008 B-árvores. Inicialização (prog16.1.c), busca (prog16.2.c), e inserção (prog16.3.c, prog16.4.c)

• Julho
  1. (Aula 25) 1/7/2008 Prova Sub (fechada)

  2. (Aula 26) 3/7/2008 Aula bônus (papo aleatório; Capítulo 3 de Kernighan e Pike): transparências

Calendário

        February 2008              March 2008               April 2008     
     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa 
                     1  2                        1            1  2  3  4  5 
      3  4  5  6  7  8  9      2  3  4  5  6  7  8      6  7  8  9 10 11 12 
     10 11 12 13 14 15 16      9 10 11 12 13 14 15     13 14 15 16 17 18 19 
     17 18 19 20 21 22 23     16 17 18 19 20 21 22     20 21 22 23 24 25 26 
     24 25 26 27 28 29        23 24 25 26 27 28 29     27 28 29 30 
                              30 31 

           May 2008                June 2008                July 2008      
     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa 
                  1  2  3      1  2  3  4  5  6  7            1  2  3  4  5 
      4  5  6  7  8  9 10      8  9 10 11 12 13 14      6  7  8  9 10 11 12 
     11 12 13 14 15 16 17     15 16 17 18 19 20 21     13 14 15 16 17 18 19 
     18 19 20 21 22 23 24     22 23 24 25 26 27 28     20 21 22 23 24 25 26 
     25 26 27 28 29 30 31     29 30                    27 28 29 30 31 

Last modified: Tue Mar 31 11:18:40 BRT 2009