Algoritmos e Estruturas de Dados
LEEC
2004/05

Informações gerais

• Página da disciplina no SIFEUP (inclui a ficha da disciplina)
• Docentes:
  • João Canas Ferreira
  • Ana Paula Rocha
  • Diogo Ribeiro Ferreira
  • André Restivo
• Planeamento: aulas teóricas, aulas práticas
• Edição de 2003/04
• Atenção: Os alunos que obtiveram nota mínima nos trabalhos práticos e nos questionários no ano lectivo de 2003/04 não necessitam de repetir estas componentes de avaliação em 2004/05.
• Informações gerais sobre C++
• Informação sobre os minitestes:
  1. Data: 20/Abril/2005 às 17:00H
     Local: B215, B227, B338, B116.
  2. Data: 9/Junho/2005 às 8:30H
     Local: B215, B221, B227.

  Os minitestes são com consulta.

  Duração: 1:30H para alunos com frequência regular, 2:00H para os restantes (incluindo os alunos com nota de frequência do ano anterior que não frequentam as aulas práticas).

Aulas teóricas

1. Introdução ao C++: Extensões ao C
2. Vectores em C++ (actualizado em 2005-03-08)
3. Vectores: Algoritmos de Pesquisa
4. Vectores: Algoritmos de Ordenação (actualizado em 2005-03-08)
5. Análise de Complexidade de Algoritmos
6. Introdução à Programação com Classes em C++
7. Programação com Classes em C++ (cont.)
8. Sobrecarga e Operadores
9. Templates em C++
10. Tratamento de Excepções
11. Herança em C++
12. Listas
    • Acetatos
    • Tópicos sobre apontadores
    • Classe VList: Vlist.h testVList.cpp, exceptions.h
    • Classe LList: LList.h, testLList.cpp
    • Exemplos:
      • Polinómios esparsos: Polinomio.h, Polinomio.cpp, Termo.h, Termo.cpp, testPolinomio.cpp
      • Números naturais: NumNatural.h, NumNatural.cpp, sissa.cpp
13. Pilhas e filas
    • Acetatos
    • Excepções: xceptions.h
    • Classe LStack: Lstack.h, testLStack.cpp, implementação de uma fila ligada
    • Classe VStack: Vstack.h, testVStack.h
    • Classe LQueue: LQueue.h, testLQueue.cpp
    • Classe CQueue: CQueue.h, testCQueue.cpp
    • Exemplos: Aplicações de pilhas e filas
      • Utilidades: ioutil.h, ioutil.cpp
      • RPN: rpneval.h, rpneval.cpp, postfix.cpp
      • Notação infixa -> RPN: infixtorpn.h, infixtorpn.cpp, i2r.cpp
      • Algoritmo de Lee: Ponto.h, Ponto.cpp, percurso.cpp, labirinto1, labirinto2
14. Árvores binárias
    • Acetatos
    • Implementação e uso de árvores binárias
    • Excepções: xceptions.h (diferente do anterior)
    • Classe BinaryTree: BinaryTree.h, testBinaryTree.cpp
    • Classe BST: BST.H, testBST.cpp
    • Exemplos:
      • Utilidades: ioutil.h, ioutil.cpp
      • Expressões aritméticas: ExprElem.h, ExprElem.cpp, exprarit.h, exprarit.cpp, aa.cpp
      • Contar palavras: algoritmo, palnum.cpp, On Liberty (279 KB) de John S. Mill (dos arquivos do projecto Gutenberg).
15. Tabelas de dispersão
    • Acetatos
    • Classe HashTable: versão com listas, versão com sondagem quadrática, hash.h, hash.cpp
    • Número de palavras distintas: algoritmo, paldiff.cpp ioutil.cpp, ioutil.h, dados (1,5 MB).

Aulas práticas

Enunciados dos trabalhos práticos

• Semana 1: Não há aulas práticas.
• Semana 2: P1A
• Semana 3:
  • P1B
  • ficheiros auxiliares: tabsen.txt, tabexp.txt, tabexp2.txt
• Semana 4: P2A
• Semana 5:
  • P2B
  • ficheiros auxiliares: medidas.txt, medidas1.txt, medidas2.txt
• Semana 6: P3A
• Semana 7: P3B.
  Ficheiros de teste: testAssocList.cpp, testGrafo.cpp
• Semana 8: P4A.
  Versão alterada de VList.h, xceptions.h
• Semana 9: P4B
  LList.h, xceptions.h
  Ficheiros de teste: testEstacao.cpp, testMaquina.cpp, testRoda.cpp
• Semana 10: P5A
  Ficheiros de teste: testExpressao.cpp, testBiblioteca.cpp, testComboio.cpp
• Semana 11: P5B
  Ficheiros de teste: testJogo.cpp, testTransporte.cpp, testTexto.cpp

Exercícios de programação

1. Funções, parâmetros, entrada/saída de dados
2. Funções e vectores
3. Algoritmos de ordenação e complexidade
4. Definição e utilização de classes
5. Classes genéricas e excepções
6. Listas baseadas em vectores
7. Listas ligadas
8. Pilhas e filas
9. Árvores
10. Tabelas de dispersão

Classificações

• Turma 1
• Turma 2
• Turma 3
• Turma 4
• Turma 5
• Turma 6
• Turma 8
• Turma 9
• Turma 10
• Turma 11
• Turma 12
• Turma 13

• Classificações do 1º miniteste
  Consulta: Dia 2005-05-18, 16:00H-17:00H, sala I125.
  Tópicos de resolução

• Avaliação distribuída (aulas práticas e questionários).

• Classificações do 2º miniteste e finais
  Consulta: dia 2005-07-6, 14:30H-15:00H, sala I125.