Algoritmos clássicos e estruturas de dados — de Sedgewick e Cormen, explicados a fundo.
Recursão é uma função definida em termos de si mesma via um caso base e um passo recursivo; o formato da recorrência resultante — subtrair uma constante de n versus dividir n — é o que decide se o tempo de execução é linear, exponencial ou logarítmico, como concretamente mostrado por fatorial, Fibonacci ingênuo, Torres de Hanói e busca binária. Este é o pré-requisito que os concepts irmãos algorithm-analysis-order-of-growth e dynamic-programming-fundamentals usam sem rederivar.
Como avaliar um algoritmo que precisa se comprometer com uma decisão antes de ver o resto da entrada — a razão competitiva, definida contra um algoritmo que conhece o futuro, aplicada à decisão elevador-versus-escada, à heurística de lista MOVE-TO-FRONT 4-competitiva, e ao caching online, onde LRU e FIFO são Θ(k), LIFO e LFU não têm limite, toda política determinística está presa a Ω(k), e RANDOMIZED-MARKING alcança O(lg k) contra um adversário oblivious.
O framework formal de análise de custo por trás do paralelismo fork-join: modele um cálculo como um DAG de strands, meça seu work (T1) e span (T∞), e use a lei do work e a lei do span para derivar o teto comprovado TP >= max(T1/P, T∞) sobre quanto speedup adicionar processadores pode comprar.
Aprenda a provar um limite rigoroso de pior caso para o custo médio de uma operação ao longo de qualquer sequência de operações, mesmo quando uma única operação é cara — os métodos agregado, contábil e potencial usados para justificar afirmações como ArrayList.add ser O(1) amortizado, e por que amortizado é uma garantia mais forte e diferente de caso médio.
Como descrever o tempo de execução de um algoritmo independentemente do hardware e do tamanho da entrada, usando a notação til/ordem-de-crescimento de Sedgewick e os limites formais O/Ω/Θ de Cormen.
Uma ordenação sem comparação que espalha n chaves — assumidas uniformemente distribuídas sobre um intervalo conhecido [0, K) — em n buckets de largura igual, ordena cada bucket individualmente e os concatena; sob uniformidade cada bucket guarda O(1) elementos em média, dando tempo esperado O(n), uma suposição estrutural diferente do counting-sort irmão (faixa de inteiros limitada) e do radix-sort (chaves de largura fixa).
Counting sort assume que cada elemento de entrada é um inteiro não negativo em um intervalo limitado de 0 a k, e ordena em tempo Theta(n + k) — Theta(n) quando k = O(n) — contando e fazendo soma de prefixos em vez de comparar, que é exatamente como ele supera o limite Omega(n lg n) que só se aplica a comparison sorts.
Como encontrar o k-ésimo menor elemento de um array não ordenado em tempo linear esperado, reaproveitando o próprio passo de partition do quicksort e recursando apenas no lado que contém o rank alvo, mais o algoritmo median-of-medians de Cormen, que garante O(N) mesmo no pior caso.
Compara os três sorts elementares de array que fundamentam o restante deste módulo: selection sort (movimentação mínima de dados, mas cego à ordem da entrada), insertion sort (adaptativo a entradas quase ordenadas, e o próprio exemplo recorrente de CLRS para provas de corretude por invariante de laço), e shellsort (insertion sort estendido com uma sequência de gaps decrescente, com uma complexidade de pior caso que ainda é um problema em aberto para muitas sequências de gap práticas).
Como o mergesort divide e funde recursivamente para garantir O(n log n) em todos os casos (diferente do pior caso O(n²) do quicksort), a fusão baseada em array auxiliar de Sedgewick vs. a fusão baseada em sentinela de Cormen, e por que o TimSort do Java é o descendente real do mergesort.
Como o quicksort ordena in-place particionando em torno de um pivô, por que o caso médio é O(n log n) mas o pior caso é O(n²), e como o particionamento de dois ponteiros de Sedgewick difere do esquema Lomuto de Cormen.
Manter uma janela contígua sobre um array ou string com dois ponteiros que só avançam — expandindo pra absorver novos elementos, contraindo pra descartar os inválidos — transforma uma varredura que recalcula toda janela em uma única passada O(n) amortizada, pelo mesmo argumento de análise agregada que torna ArrayList.add O(1) amortizado.
Dois índices percorrendo uma estrutura em vez de um só — convergindo a partir das extremidades opostas em dados ordenados, ou se movendo em velocidades diferentes para detectar ciclos e encontrar pontos médios — transformando uma varredura aninhada O(n²) em uma única passada O(n), provada correta por um argumento de troca específico para cada problema.
Por que multiplicar polinômios em forma de coeficientes custa Θ(n²) mas só Θ(n) em forma ponto-valor, e como a divisão-e-conquista par/ímpar da FFT sobre as raízes complexas da unidade torna a conversão entre as duas representações — e portanto a multiplicação inteira — Θ(n lg n).
O algoritmo de Euclides para o GCD e sua forma estendida para calcular coeficientes de Bezout e inversos multiplicativos modulares, as propriedades de congruência que mantêm a aritmética modular limitada, e exponenciação modular via quadrados sucessivos — a recursão O(β), contra um O(2^β) ingênuo, que tanto RSA quanto Diffie-Hellman usam para elevar números grandes a potências grandes mod um primo grande.
Como reduzir repetidamente pela metade o intervalo de busca de um array ordenado encontra um alvo em O(log n) comparações, a fórmula de ponto médio à prova de overflow de Sedgewick, e o argumento de corretude por invariante de laço do CLRS.
Uma pilha mantida estritamente crescente ou decrescente, removendo elementos que violariam a ordem antes de cada inserção — transforma 'maior/menor elemento próximo' de uma varredura O(n²) por elemento em O(n) total, usando o mesmo argumento de análise agregada que o CLRS prova pra uma pilha com operação MULTIPOP.
Um Bloom filter responde \"esta chave poderia estar no conjunto?\" usando um array de bits de tamanho fixo e k funções de hash independentes em vez de armazenar qualquer chave, garantindo zero falsos negativos ao aceitar uma taxa de falso positivo pequena e precisamente ajustável — trocando exatidão por buscas O(k) e espaço O(m) que nunca depende do tamanho ou tipo da chave.
Uma lista encadeada ordenada aumentada com níveis de \"pista expressa\" randomizados, onde cada elemento é independentemente promovido ao nível i+1 com probabilidade 1/d; diferente de AVL/red-black trees, que garantem altura O(log n) via rotações/recoloração determinísticas, uma skip list obtém tempo esperado O(log n) só a partir da aleatoriedade, sem nenhuma lógica de rebalanceamento.
AVL trees são a primeira árvore de busca binária autobalanceada já publicada (1962), corrigindo a maior fraqueza de uma BST simples — a altura, e o custo de toda operação, dependerem da ordem de inserção e degradarem para O(n) — ao limitar o fator de balanceamento de todo nó a {-1, 0, 1} e restaurá-lo via rotações simples ou duplas após cada inserção/remoção, garantindo altura O(log n) incondicionalmente.
B-trees são árvores de busca projetadas especificamente para armazenamento em disco: nós gordos e ordenados, e uma inserção que divide proativamente no caminho para baixo, mantendo a altura da árvore minúscula em relação a uma árvore de busca binária, minimizando o número de acessos caros a disco por operação.
A teoria algorítmica por trás das hash tables: como uma função de hash mapeia chaves para índices de array, por que colisões são matematicamente inevitáveis, e como separate chaining e open addressing/linear probing as resolvem sob um fator de carga limitado — mais o design de funções de hash (método da divisão, universal hashing) e por que deletar é complicado em open addressing.
Como um binary heap empacota uma árvore binária completa em um array simples, sem ponteiros, usando swim/sink para manter a ordem de heap em O(log n), e como esse mesmo heap baseado em array move o heapsort — uma ordenação in-place com pior caso garantido de O(n log n).
Percorre a estrutura de dados union-find por quick-find, quick-union, weighted quick-union e path compression — o clássico problema de conectividade dinâmica resolvido com florestas baseadas em array progressivamente mais rápidas, terminando em O(α(n)) amortizado, na prática efetivamente constante.
As cinco propriedades rubro-negras, os casos de insert-fixup do CLRS (recoloração e rotação) traçados manualmente e verificados, e por que TreeMap/TreeSet usam isso em vez de uma BST comum.
A propriedade de árvore binária de busca, o get/put recursivo dos dois livros, por que toda operação custa O(altura) em vez de automaticamente O(log n), e por que TreeMap/TreeSet usam árvores rubro-negras auto-balanceadas em vez de uma BST comum.
Como Sedgewick e Wayne transformam uma expressão regular em um autômato finito não determinístico e o simulam rastreando o conjunto inteiro de estados alcançáveis em vez de fazer backtracking, garantindo tempo de matching O(NM) no pior caso — uma garantia mais forte que a abordagem de backtracking que o java.util.regex.Pattern de fato usa.
Uma busca de substring baseada em hashing: gera o fingerprint do padrão uma vez, depois desliza uma janela pelo texto atualizando seu hash em O(1) por passo via uma recorrência de hash rolante, recorrendo à comparação de caracteres apenas em caso de match de hash — cobre a sutileza da colisão, o trade-off de corretude Las Vegas/Monte Carlo, e o caso de uso de detecção de plágio multi-padrão que KMP e Boyer-Moore não generalizam tão naturalmente.
Como varrer o padrão da direita para a esquerda e pré-computar uma tabela de salto por caractere de discordância permite que Boyer-Moore deslize o padrão para além de vários caracteres do texto em uma única discordância — muitas vezes sublinear na prática (~N/M comparações, pela Propriedade O de Sedgewick e Wayne) — ao custo da garantia incondicional de pior caso O(N+M) do KMP.
Como o pior caso O(NM) da busca de substring por força bruta em entrada auto-repetitiva motiva a ideia-chave do Knuth-Morris-Pratt: um mismatch já te diz o suficiente sobre o texto para construir um pequeno autômato a partir do padrão e varrer o texto uma vez, sem retroceder, em O(N).
Uma trie armazena chaves de string implicitamente como o caminho da raiz até o nó, dando custo de busca/inserção proporcional ao comprimento da chave em vez do número de chaves (diferente de uma BST, cujo custo depende de N via altura da árvore); a ternary search trie (TST) reduz o custo de espaço da trie R-way usando 3 links por nó em vez de um array de R slots, e ambas as estruturas suportam de forma única consultas de prefixo como autocomplete e correspondência de prefixo mais longo.
Explica LSD e MSD radix sort, dois métodos de ordenação de strings indexados por caractere e construídos sobre contagem indexada por chave que alcançam tempo linear evitando comparações por completo, além do corte para insertion sort e do 3-way radix quicksort como alternativa para alfabetos grandes.
Entenda componentes fortemente conexos (SCCs) -- a generalização para grafos direcionados do concept irmão de DFS sobre componentes conexos em uma única passada em grafos não direcionados, necessária porque a alcançabilidade direcionada é assimétrica. Cobre a transposta do grafo e por que ela preserva os SCCs, o algoritmo de Kosaraju (DFS no grafo reverso para obter a pós-ordem reversa, depois DFS no grafo original nessa ordem, com cada árvore de DFS resultante sendo exatamente um SCC), um exemplo de dois ciclos verificado à mão e traçado com o motor de visualização de grafos, por que o algoritmo é correto, e seu tempo de execução O(V+E).
Ordene os vértices de um directed acyclic graph (DAG) de forma que toda aresta aponte para frente, executando DFS e lendo os vértices na ordem reversa do tempo de término — a mesma travessia O(V+E) que o concept irmão de DFS já constrói, com um push por vértice adicionado.
Como os algoritmos de Prim e Kruskal exploram a propriedade do corte para construir greedily uma minimum spanning tree — Prim crescendo uma única árvore via priority queue, Kruskal ordenando todas as arestas e usando union-find para pular as que fechariam ciclo — traçado em um exemplo de 6 vértices verificado à mão e contrastado para grafos densos vs. esparsos.
Entenda depth-first search (DFS): uma travessia de grafo que avança o mais fundo possível por um ramo antes de retroceder, tipicamente usando a própria pilha de chamadas recursivas em vez da fila explícita do BFS. Cobre a formulação recursiva, a busca de componentes conectados via DFS repetido, a marcação de tempos de descoberta/término e a estrutura de parênteses, e a classificação de arestas (tree, back, forward, cross) — incluindo como back edges revelam ciclos e como a ordem reversa de tempo de término fundamenta o topological sort.
Como a BFS visita vértices em ordem de distância a partir de uma origem usando uma fila em vez da pilha da DFS, garantindo caminhos mais curtos num grafo não ponderado, traçada contra o próprio grafo de exemplo de Sedgewick.
Resolve caminhos mínimos entre todos os pares em tempo O(V² lg V + VE), reponderando cada aresta para ficar não negativa com uma única execução auxiliar de Bellman-Ford e depois rodando Dijkstra uma vez a partir de cada vértice — uma composição que supera o O(V³) de Floyd-Warshall em grafos esparsos.
Aprenda o problema de caminhos mínimos entre todos os pares e o algoritmo de programação dinâmica de Floyd-Warshall que o resolve em tempo Θ(V³) restringindo os vértices intermediários de cada caminho mínimo a um conjunto crescente {1, ..., k}, em vez de repetir um algoritmo de origem única uma vez por vértice.
Bellman-Ford resolve o problema de caminho mínimo de origem única no caso totalmente geral — qualquer grafo, qualquer mistura de pesos de aresta positivos e negativos — relaxando todas as arestas V-1 vezes em vez de depender da ordenação por fila de prioridade do Dijkstra, e ganha detecção de ciclo negativo de graça com uma passada extra de relaxamento.
Em um directed acyclic graph, relaxar as arestas de saída de cada vértice uma única vez em ordem topológica encontra os caminhos mais curtos em O(V + E) — mais rápido que a priority queue de Dijkstra e correto mesmo com pesos de aresta negativos, já que um DAG nunca pode conter o ciclo negativo que tornaria os caminhos mais curtos mal definidos.
O algoritmo de Dijkstra encontra os caminhos mais curtos em um grafo ponderado com arestas não negativas substituindo a fila FIFO do BFS por uma priority queue ordenada pela distância acumulada, finalizando repetidamente o vértice não processado mais próximo via relaxamento de arestas.
Como caminhos M-aumentantes e diferença simétrica resolvem maximum bipartite matching diretamente — sem redução a max-flow — com Hopcroft-Karp alcançando O(√V·E), e como adicionar pesos de aresta transforma isso no assignment problem, que o algoritmo húngaro resolve reetiquetando repetidamente vértices até que algum matching perfeito apareça dentro de um equality subgraph.
Dado um grafo bipartido completo em que todo vértice ranqueia os vértices do outro lado, o algoritmo de Gale-Shapley sempre encontra um matching sem par bloqueador — e provadamente dá a cada proponente seu melhor parceiro alcançável entre todos os matchings estáveis, ao custo de dar a cada vértice proposto seu pior.
Como Ford-Fulkerson encontra o fluxo máximo através de uma rede com capacidades, empurrando repetidamente fluxo ao longo de caminhos de aumento em um grafo residual, e por que o teorema do fluxo máximo e corte mínimo garante que o ponto de parada do algoritmo é comprovadamente ótimo.
Uma técnica geral de busca recursiva para enumerar toda solução válida de um problema combinatório — escolha uma opção, recurse, desfaça a escolha — com poda que abandona um ramo no instante em que ele se prova inválido, em vez de construí-lo até o fim e checar depois.
Branch and Bound resolve problemas de otimização inteira e combinatória de forma exata organizando o espaço de busca como uma árvore de subproblemas, usando o valor da relaxação LP de cada subproblema como limite superior para podar ramos inteiros que não podem superar a melhor solução inteira já encontrada. Traçado à mão num programa inteiro real de 2 variáveis (relaxação da raiz, um ramo inviável, uma solução inteira podada por limite, e o ramo que vira o incumbente final) para tornar a poda concreta em vez de abstrata.
O algoritmo guloso que constrói um código binário livre de prefixo ótimo mesclando repetidamente os dois símbolos menos frequentes numa trie, provado ótimo via um argumento de troca e subestrutura ótima.
O segundo exemplo trabalhado de programação dinâmica do CLRS: encontrar a parentetização de uma cadeia de matrizes que minimiza o total de multiplicações escalares, preenchendo uma tabela Theta(n^2) de subproblemas indexados por intervalo de matrizes em tempo O(n^3), em vez de enumerar as exponencialmente muitas parentetizações possíveis.
Calcule o número mínimo de operações de inserção, remoção e substituição para transformar uma string em outra usando uma tabela de PD 2D que estende a técnica de preenchimento de tabela de LCS com uma terceira célula predecessora para substituição, depois faça o backtrack pela tabela para recuperar a sequência de edição real.
Contrasta o problema da mochila fracionária, que tem a propriedade da escolha gulosa e é resolvido por uma única passada gulosa de ordenar-e-pegar em O(n log n), com o problema da mochila 0-1, onde a mesma regra gulosa, aparentemente idêntica, falha comprovadamente (reproduzindo o próprio contraexemplo de $220-vs-$160 de CLRS) apesar de os dois problemas compartilharem subestrutura ótima — então desenvolve a recorrência de PD do 0-1, uma tabela verificada à mão, e o tempo de execução pseudo-polinomial O(nW) que CLRS deixa como exercício em vez de resolver no texto principal.
Resolve o problema de seleção de atividades (agendar o maior número possível de atividades sem sobreposição em um recurso compartilhado) com a regra greedy do menor tempo de término, prova por que essa regra específica é ótima, e mostra um contraexemplo verificado onde uma regra alternativa plausível (menor duração primeiro) falha — contrastado com a formulação em programação dinâmica do mesmo problema.
Como derivar a recorrência c[i][j] do LCS comparando os últimos caracteres de duas sequências, preencher a tabela 2D resultante bottom-up em tempo O(mn), e percorrer um caminho de volta pela tabela pronta para reconstruir a subsequência de fato, não só seu tamanho.
Veja por que programação dinâmica supera a recursão simples só quando os subproblemas se sobrepõem, usando o problema do corte de hastes do CLRS: a recursão ingênua e exponencial CUT-ROD, o cache de memoização que garante que cada tamanho de subproblema seja computado exatamente uma vez, o preenchimento bottom-up da tabela que constrói a mesma resposta iterativamente, e as duas marcas registradas — subestrutura ótima e subproblemas sobrepostos — que determinam se DP se aplica ou não.
O algoritmo exato para subset sum constrói a lista de toda soma de subconjunto alcançável e é exponencial porque essa lista pode dobrar a cada iteração; recortá-la — descartando qualquer valor que outro valor sobrevivente já aproxime dentro de um fator de 1 + ε/2n — a reduz para comprimento polinomial e transforma o algoritmo num esquema de aproximação totalmente polinomial cujo tempo de execução é polinomial tanto no tamanho da entrada quanto em 1/ε.
GREEDY-SET-COVER escolhe repetidamente o conjunto que cobre mais elementos ainda descobertos, dando uma razão de aproximação logarítmica em vez de constante; a Seção 35.4 então acrescenta mais duas técnicas — uma 8/7-aproximação randomizada para MAX-3-CNF que é puro cara-ou-coroa, e uma 2-aproximação para vertex cover ponderado obtida relaxando um programa inteiro 0-1 para um programa linear e arredondando a resposta fracionária em 1/2.
Como novos problemas são de fato provados NP-completos: a receita de quatro passos do Lema 34.8 para reduzir a partir de uma única linguagem NP-completa conhecida em vez de todo NP, depois o catálogo resolvido de reduções construindo de CIRCUIT-SAT até SAT, 3-CNF-SAT, CLIQUE, VERTEX-COVER, HAM-CYCLE, TSP e SUBSET-SUM — mais a técnica de gadget e as estratégias e armadilhas de redução que se generalizam.
Cobre APPROX-VERTEX-COVER, uma 2-aproximação em tempo polinomial para o problema NP-completo de vertex cover, e APPROX-TSP-TOUR, uma 2-aproximação para o problema do caixeiro-viajante sob a desigualdade triangular, além de por que não existe aproximação de razão constante sem ela.
O que P, NP e NP-completude significam com precisão — a assimetria entre verificar e resolver, por que um algoritmo rápido para um problema NP-completo resolveria todo o NP, e como reconhecer um problema NP-difícil disfarçado para então recorrer a aproximação, heurísticas, ou um caso especial tratável em vez de insistir na solução exata.
O método simplex tabular — transformando restrições de desigualdade num dicionário inicial via variáveis de folga/excesso/artificiais, lendo soluções diretamente de um tableau, e pivoteando via eliminação de Gauss-Jordan até o ótimo — retomando exatamente onde o concept irmão linear-programming-formulation-and-duality parou deliberadamente antes do algoritmo em si; também cobre formas não padrão (minimização, restrições >=/= via o método de duas fases) e as variantes dual-simplex/simplex generalizado construídas sobre a mesma maquinaria de tableau.
Como modelar um problema como um programa linear em forma padrão — caminhos mínimos, max-flow, fluxo de custo mínimo e fluxo multicommodity — por que uma solução ótima sempre fica num vértice da região viável, e como duality transforma um LP de maximização num LP de minimização cujo valor objetivo casado certifica otimalidade.
Um método iterativo geral para encontrar um mínimo local de uma função contínua repetidamente dando passos na direção oposta ao gradiente, com um limite de convergência provado em funções convexas que troca respostas exatas (como o Θ(n^3) da eliminação gaussiana) por uma resposta aproximada mais rápida.
K-means clustering é NP-hard, então o procedimento de Lloyd se contenta com uma heurística de busca local com terminação provada — atribuindo pontos alternadamente ao centro mais próximo e recalculando cada centro como o centroide do seu cluster — até que a atribuição pare de mudar.