Estas notas referem-se à matéria leccionada nas aulas teóricas de Introdução aos Algoritmos e Estruturas de Dados, no primeiro semestre de 2013/14, e têm por base os slides e as notas preparados ao longo dos últimos anos pelo corpo docente.
Aula 01: Apresentação. Programa. Ambiente de desenvolvimento. Introdução ao C. C vs Python. (19/09/2013)
Aula 02: Linguagem C. Elementos da linguagem e controlo de execução. Leitura do stdin e escrita no stdout. Exemplos. (20/09/2013)
Aula 03: Text streams. Funções getchar e putchar. Caracteres e inteiros em C. Caracter EOF e caracteres de final de linha. Exemplos. Introdução às tabelas unidimensionais. (26/09/2013)
Aula 04: Tabelas e funções em C. Tabelas unidimensionais e bidimensionais. Funções em C, protótipos e implementação. Passagem por valor e por referência. Exemplos. (27/09/2013)
Aula 05: Elementos da linguagem C. Tipos de dados e conversão de tipos. Tipos enumerados. Declaração de variáveis automáticas (locais), globais e estáticas. Operadores e tabela de precedências. Expressões condicionais. Atribuições. Controlo de execução. (03/10/2013)
Aula 06: Introdução às estruturas. Estruturas e funções. Vectores de estruturas. Typedef. Exemplos. (04/10/2013)
Aula 07: Problemas, instâncias e algoritmos. Complexidade computacional. Análise de algoritmos. Crescimento de funções e notação assimptótica. Exemplos. Master theorem. (10/10/2013)
Aula 08: Problema da ordenação. Algoritmos elementares de ordenação. Selection sort. Insertion sort. Bubble sort. Implementação, análise e complexidade. Exemplos. (11/10/2013)
Aula 09: Algoritmos de ordenação. Shell sort. Quick sort. Merge sort. Implementação, análise e complexidade. Exemplos. (17/10/2013)
Aula 10: Algoritmos de ordenação e amontoados binários. Heap sort. Filas com prioridade. Implementação, análise e complexidade. Exemplos. (18/10/2013)
Aula 11: Algoritmos de ordenação não baseados em comparações. Counting sort. Algoritmos da família Radix sort, nomeadamente Radix LSD, Radix MSD, e Binary radix. Implementação, análise e complexidade. Exemplos. (24/10/2013)
Aula 12: Ponteiros em C. Utilização de ponteiros e os operadores * e &. Ponteiro nulo. Ponteiros e tabelas. Argumentos da linha de comandos. Ponteiros para funções. Alocação dinâmica de memória. (25/10/2013)
Aula 13: Ponteiros para estruturas e estruturas auto-referenciadas. Estruturas e funções, passagem por valor e por referência. Conversão de tipos e estruturas. Exemplos, listas simplesmente ligadas e duplamente ligadas. (31/10/2013)
Aula 14: Listas ligadas. Inserção e remoção em listas simplesmente ligadas e duplamente ligadas. Implementação de uma pilha de inteiros e de uma lista simplesmente ligada de strings. (01/11/2013)
Aula 15: Estruturação de programas. Documentação, testes, e asserções. Operações sobre ficheiros. Leitura e escrita de ficheiros. (07/11/2013)
Aula 16: Tipos de dados abstractos (ADT). Listas simplesmente e duplamente ligadas revisitadas. Filas, pilhas e ring buffer. Análise comparativa da complexidade das operações sobre listas ligadas e sobre vectores. Funções lsearch, bsearch e qsort. (08/11/2013)
Aula 17: Tabelas de dispersão com resolução por encadeamento externo. Funções de dispersão e propriedades. Função hsearch. (14/11/2013)
Aula 18: Tabelas de dispersão com resolução por encadeamento interno. Linear probing. Double hashing. Complexidade e exemplos. (15/11/2013)
Aula 19: Árvores binárias de pesquisa. Operações de inserção, pesquisa, remoção e travessia. Análise, complexidade e exemplos. Função tsearch. (21/11/2013)
Aula 20: Revisões para o primeiro teste (testes de anos anteriores). (22/11/2013)
Aula 21: Altura e profundidade em árvores. Árvores binárias equilibradas e perfeitamente equilibradas. Operações de rotação, inserção na raiz, selecção, partição e balanceamento. Inserção aleatória na raiz. (28/11/2013)
Aula 22: Árvores AVL (Adelson-Velskii e Landis). Operações de inserção, rotação, e remoção. Análise, complexidade e exemplos. (29/11/2013)
Aula 23: Problemas e aplicações com grafos. Representação de grafos com matrizes de adjacências e com listas de adjacências. Representação versus complexidade algorítmica. Exemplos. (05/12/2013)
Aula 24: Algoritmos elementares em grafos: procura em profundidade primeiro (DFS); procura em largura primeiro (BFS). Análise e complexidade dos algoritmos procura. (06/12/2013)
Aula 25: Árvores abrangentes e caminhos mais curtos em grafos não pesados. Ordenação topológica de grafos. Componentes conexos e componentes fortemente conexos em grafos. (12/12/2013)
Aula 26: Filas com prioridade. Conjuntos disjuntos. ADTs, complexidade e exemplos. (13/12/2013)
Aula 27: Revisões e exercícios (testes de anos anteriores). (19/12/2013)
Aula 28: Revisões e exercícios (testes de anos anteriores). (20/12/2013)
Proposta de implementação para o primeiro projecto
Exercícios e sugestões para o segundo projecto (disponibilizadas pelo Professor Francisco Santos).
Proposta de implementação para o segundo projecto (implementação alternativa, gerador de testes).