Curso de Algoritmos e Estrutura de Dados

Aula 1 • Introdução à Organização de Dados

Aborda tipos de dados primitivos versus compostos e conceitos de layout de memória. Estabelece o vocabulário utilizado ao longo do curso.

Aula 2 • Arrays e Strings

Examina o armazenamento contíguo em memória por meio de arrays e sequências de caracteres. Conecta a mecânica de indexação a algoritmos posteriores de busca e ordenação.

Aula 3 • Fundamentos de Análise de Complexidade

Apresenta as notações Big-O, Big-Theta e Big-Omega para avaliar a eficiência. Permite que os alunos comparem operações de estruturas de dados quantitativamente.

Aula 4 • Pilhas e Filas

Define padrões de acesso LIFO e FIFO e suas implementações. Demonstra casos de uso do mundo real, como análise de expressões e escalonamento.

Aula 1 • Algoritmos Recursivos Clássicos

Aplica recursão a funções fatorial, Fibonacci e potência. Reforça o reconhecimento de padrões para resolução recursiva de problemas.

Aula 2 • Fundamentos do Pensamento Recursivo

Estabelece casos base, casos recursivos e comportamento da pilha de chamadas. Constrói a intuição necessária antes de abordar algoritmos de árvores e grafos.

Aula 3 • Estratégia de Dividir e Conquistar

Formaliza a divisão de problemas em metades independentes e a combinação dos resultados. Prepara os alunos para o merge sort e o quick sort no próximo capítulo.

Aula 1 • Ordenações Eficientes Baseadas em Comparação

Implementa merge sort e quick sort usando dividir e conquistar. Analisa as diferenças de desempenho entre os casos médio e pior.

Aula 2 • Algoritmos de Ordenação Elementares

Abrange bubble sort, selection sort e insertion sort com rastreamentos passo a passo. Estabelece benchmarks de complexidade de base para comparação com ordenações avançadas.

Aula 3 • Métodos de Ordenação sem Comparação

Apresenta counting sort, radix sort e bucket sort para ordenação em tempo linear. Mostra quando dados de inteiros ou de intervalo limitado permitem garantias subquadráticas.

Aula 4 • Seleção de Algoritmo de Ordenação

Orienta a tomada de decisão com base no tamanho, tipo e restrições de memória dos dados. Sintetiza o conteúdo do capítulo em um framework prático de seleção.

Aula 1 • Travessias em Árvores Binárias

Implementa travessias em ordem, pré-ordem, pós-ordem e em nível. Conecta a escolha da travessia a requisitos específicos de saída, como saída ordenada.

Aula 2 • Árvores Binárias de Busca

Aborda inserção, remoção e busca em BST com análise de complexidade. Demonstra como invariantes de ordenação permitem buscas eficientes.

Aula 3 • Heaps e Filas de Prioridade

Constrói min-heaps e max-heaps usando representação em array e operações de heap. Conecta a estrutura do heap ao heap sort e ao escalonamento baseado em prioridade.

Aula 4 • BSTs Balanceadas e Árvores AVL

Apresenta o balanceamento por altura via rotações AVL para manter garantias O(log n). Prepara os alunos para árvores rubro-negras e B-árvores em tópicos avançados.

Aula 1 • Operações e Análise de Tabelas Hash

Implementa inserção, remoção e busca com análise de complexidade amortizada. Conecta garantias teóricas a decisões práticas de implementação.

Aula 2 • Aplicações Avançadas de Hashing

Explora hashing consistente, filtros Bloom e casos de uso de hash criptográfico. Estende o conhecimento de tabelas hash para sistemas distribuídos e probabilísticos.

Aula 3 • Estratégias de Resolução de Colisão

Compara técnicas de encadeamento e endereçamento aberto para lidar com colisões. Analisa o impacto do fator de carga no desempenho de cada estratégia.

Aula 1 • Tópicos Avançados em Grafos

Apresenta ordenação topológica, componentes fortemente conectados e conceitos básicos de fluxo em rede. Prepara os alunos para problemas de projeto de algoritmos em contextos competitivos e aplicados.

Aula 2 • Representação e Terminologia de Grafos

Define grafos direcionados, não direcionados, ponderados e cíclicos com estruturas de adjacência. Estabelece as escolhas de representação que afetam a eficiência do algoritmo.

Aula 3 • Árvores Geradoras Mínimas

Implementa os algoritmos de Kruskal e Prim usando union-find e filas de prioridade. Conecta conceitos de MST a aplicações de projeto de redes e agrupamento.

Aula 4 • Algoritmos de Travessia em Grafos

Implementa BFS e DFS com gerenciamento explícito de fila e pilha. Aplica travessias à detecção de conectividade e identificação de ciclos.

Aula 1 • DP em Árvores e Grafos

Estende DP para estruturas de árvore e problemas baseados em DAG. Conecta o conhecimento de travessia de grafos a formulações de DP baseadas em espaço de estados.

Aula 2 • DP em Sequências e Intervalos

Aplica DP a problemas de subsequência crescente máxima e escalonamento de intervalos. Estende o reconhecimento de padrões a otimizações com dois ponteiros e busca binária.

Aula 3 • Princípios de DP e Memorização

Define subproblemas sobrepostos e subestrutura ótima como pré-requisitos para DP. Apresenta a memorização top-down como a primeira estratégia de implementação.

Aula 4 • Tabulação Bottom-Up

Converte soluções memorizadas em abordagens iterativas de preenchimento de tabela. Demonstra otimização de espaço reduzindo as dimensões da tabela.

Aula 1 • Estruturas Trie e de Sufixo

Implementa árvores de prefixo para busca rápida de strings e autocomplete. Apresenta arrays de sufixos para correspondência de padrões em grandes corpora de texto.

Aula 2 • Árvores de Segmentos e Árvores de Fenwick

Constrói estruturas de consulta de intervalo e atualização de ponto para operações eficientes em intervalos. Compara árvores de segmentos e árvores de Fenwick por complexidade de implementação e caso de uso.

Aula 3 • Análise Amortizada e Tópicos Avançados

Aplica métodos agregado, contábil e de potencial para analisar sequências de estruturas de dados. Apresenta skip lists e estruturas autoajustáveis como alternativas avançadas.

Aula 4 • Union-Find e Conjuntos Disjuntos

Implementa união por classificação e compressão de caminho para operações de tempo quase constante. Aplica union-find a conectividade dinâmica e MST de Kruskal.