Histórico das Aulas

02 de janeiro: Aspectos burocráticos; Ponteiros; Operadores & e *; Relação entre vetores e ponteiros; Aritmética de ponteiros; Ponteiro para NULL; Alocação dinâmica de memória em C.
03 de janeiro: Conceito de estruturas de dados abstratas ("Abstract Data Structures"). Exemplo de estrutura de dados abstrata: dicionário. Interfaces e implementações. Documentação de funções. Aplicação de alocação dinâmica de memória: Manipulação de listas ligadas (simples, sem cabeça).
04 de janeiro: Recursividade: definição recursiva da soma dos n primeiros números naturais; estratégia básicas de resolução de problemas via recursão; escrita de programas recursivos; base de recursão e casos gerais.
05 de janeiro: Recursividade: continuação. Solução de problemas via recursividade; Números de Fibonacci: definição; programa recursivo para cálculo do n-ésimo número de Fibonacci; programas recursivos como "codificação de fatos ou objetos" definidos recursivamente; programa iterativo para computar o n-ésimo número de Fibonacci. Problema das Torres de Hanói: enunciado; estratégia básica; aplicação de recursividade para solução; pseudo-código de uma solução recursiva para o problema das Torres de Hanói.
09 de janeiro: Recursividade: continuação. Solução de problemas via recursividade; Números de Fibonacci: definição; programa recursivo para cálculo do n-ésimo número de Fibonacci; programas recursivos como "codificação de fatos ou objetos" definidos recursivamente; programa iterativo para computar o n-ésimo número de Fibonacci. Problema das Torres de Hanói: enunciado; estratégia básica; aplicação de recursividade para solução; pseudo-código de uma solução recursiva para o problema das Torres de Hanói.
10 de janeiro: Recursividade: continuação. Solução de problemas via recursividade; Números de Fibonacci: definição; programa recursivo para cálculo do n-ésimo número de Fibonacci; programas recursivos como "codificação de fatos ou objetos" definidos recursivamente; programa iterativo para computar o n-ésimo número de Fibonacci. Problema das Torres de Hanói: enunciado; estratégia básica; aplicação de recursividade para solução; pseudo-código de uma solução recursiva para o problema das Torres de Hanói.
11 de janeiro: Provas de corretudes de algoritmos por uso de invariantes. Eu me esqueci do que cobri neste dia.
12 de janeiro: Recursos de um algoritmo a serem mensurados: tempo, espaço, complexidade de Kolmogorov, custo de comunicação. Enfoque: tempo e espaço. Motivação para análises de pior caso. Motivação para estudo de crescimento de funções. Notação assintótica.
30 de janeiro: Paradigma de divisão-e-conquista (cont.). Algoritmo Mergesort e exemplificação do paradigma de divisão-e-conquista. Fases do Mergesort: divisão (trivial), conquista (uso de recursividade) e combinação (intercalação de vetores ordenados). Subproblema da intercalação. Código em C para resolvê-lo. Código em C para o Mergesort. Breve análise de complexidade de espaço. Descrição da complexidade de tempo via relação de recorrência.
31 de janeiro: Relação de recorrência para o Mergesort. Cuidados ao tratar uma relação de recorrência com notação assintótica. Simplificações possíveis para resolução de uma recorrência. Resolução de uma relação de recorrência com solução exata via método de substituição. Resolução de uma relação de recorrência que usa notação assintótica através de indução. Cuidados ao tratar a base da indução (Nota: tópico normalmente ignorado em livros!). Caso geral da recorrência. Conclusão de que o Mergesort leva tempo O(n lg n) para ordenar um vetor de tamanho n.
1 de fevereiro: Introdução a filas de prioridades. Heaps binários: definição de max-heap binário e propriedades básicas a respeito do número de nós, de sua altura e a respeito do valor associado à raiz. Operações elementares em um heap: remoção da raiz e restauração de estrutura de heap (com análise de complexidade de tempo e de espaço); inserção de um novo elemento em um heap (com análise de complexidade de tempo e de espaço). Forma de representação de um heap em um vetor. Pseudo-código para o Heapsort.