Cobre busca, ordenação, travessias, caminhos mínimos e operações sobre strings. O aluno implementa, testa e compara algoritmos com diferentes entradas.
Percorra uma coleção até encontrar o valor procurado ou chegar ao fim. Implemente a busca linear e teste entradas em que o valor aparece no início, no fim ou não aparece.
Confira o que você entendeu com um quiz curto.
Use o que você aprendeu na aula anterior para resolver problemas do mundo real.
Use a ordem dos elementos para descartar metade do intervalo a cada comparação. Implemente a busca binária e verifique como os limites mudam quando o valor está ausente.
Adapte a busca binária para localizar a primeira posição em que um valor poderia ser inserido, inclusive quando há elementos repetidos. Teste os limites inferior e superior em casos de borda.
Construa uma região ordenada inserindo nela um elemento por vez. Implemente a ordenação por inserção e observe seu comportamento em entradas quase ordenadas.
Encontre o menor elemento da parte ainda não ordenada e coloque-o na próxima posição. Implemente a ordenação por seleção e compare suas trocas com as da ordenação por inserção.
Compare pares vizinhos e troque os que estão fora de ordem até completar uma passagem sem trocas. Implemente a ordenação por bolha e reconheça por que ela costuma ser uma escolha pouco eficiente.
Divida uma sequência, ordene as partes e intercale-as sem perder a ordem. Implemente a etapa de intercalação da ordenação por mesclagem e teste elementos repetidos.
Escolha um pivô e reorganize os elementos para deixar valores menores e maiores em lados opostos. Implemente a partição da ordenação rápida e compare o efeito de diferentes escolhas de pivô.
Mantenha o maior elemento acessível em um heap e retire-o sucessivamente para ordenar um array. Trace os ajustes do heap e teste a ordenação por heap com entradas distintas.
Conte quantas vezes cada valor inteiro aparece em um intervalo conhecido e use as contagens para produzir a saída ordenada. Implemente a ordenação por contagem e reconheça quando o intervalo de valores a torna impraticável.
Ordene números ou strings por posições sucessivas, preservando a ordem estabelecida nas passagens anteriores. Implemente uma ordenação radix usando uma passagem estável por contagem.
Verifique se elementos com a mesma chave mantêm sua ordem original após a ordenação. Compare esse requisito com o uso de memória extra ao escolher um algoritmo para registros reais.
Visite uma árvore em pré-ordem, em ordem e em pós-ordem, mudando o momento de processar cada nó. Trace as três sequências na mesma árvore e identifique usos de cada ordem.
Explore um caminho de um grafo até não poder avançar e então volte para explorar alternativas. Implemente busca em profundidade com controle de vértices visitados e teste grafos com ciclos.
Visite os vértices de um grafo por camadas a partir de uma origem. Implemente busca em largura com uma fila e controle de visitados, incluindo um grafo desconexo nos testes.
Registre o predecessor de cada vértice descoberto pela busca em largura para recuperar um caminho com o menor número de arestas. Reconstrua o caminho e reconheça por que esse resultado exige arestas sem pesos.
Retire repetidamente um vértice sem dependências pendentes para ordenar as tarefas de um grafo dirigido acíclico. Implemente o algoritmo de Kahn e detecte quando um ciclo impede a ordenação.
Expanda primeiro o vértice ainda não resolvido com a menor distância conhecida. Implemente o algoritmo de Dijkstra, atualize distâncias por relaxamento e identifique por que pesos negativos invalidam essa escolha.
Relaxe todas as arestas repetidas vezes para encontrar distâncias mesmo quando há pesos negativos. Implemente Bellman–Ford e use uma passagem adicional para detectar ciclos negativos alcançáveis.
Calcule caminhos mínimos entre todos os pares de vértices, permitindo um novo vértice intermediário a cada etapa. Trace a atualização da matriz de distâncias no algoritmo de Floyd–Warshall.
Compare strings caractere a caractere até encontrar uma diferença ou terminar uma delas. Implemente comparação lexicográfica e teste prefixos, strings iguais e diferenças entre maiúsculas e minúsculas.
Alinhe um padrão a posições sucessivas de um texto e compare seus caracteres até encontrar uma ocorrência. Implemente a busca ingênua de substring e teste padrões ausentes, repetidos e sobrepostos.
Use os prefixos que também são sufixos do padrão para evitar comparações repetidas após uma falha. Construa a tabela de prefixos e trace uma busca com Knuth–Morris–Pratt (KMP).
Atualize o hash de uma janela do texto ao avançar um caractere, em vez de recalculá-lo inteiro. Implemente Rabin–Karp e confirme por comparação direta as possíveis ocorrências, já que hashes podem colidir.
Calcule o número mínimo de inserções, remoções e substituições necessário para transformar uma string em outra. Preencha a tabela da distância de Levenshtein e confira o resultado em exemplos curtos.
Revise este capítulo com prática baseada nos seus erros.
