Entendendo Algoritmos: Um guia ilustrado para programadores e outros curiosos

Prefácio
Agradecimentos
Sobre este livro
1
Introdução a algoritmos
	Introdução
		O que você aprenderá sobre desempenho
		O que você aprenderá sobre a solução de problemas
	Pesquisa binária
		Uma maneira melhor de buscar
		Tempo de execução
	Notação Big O
		Tempo de execução dos algoritmos cresce a taxas diferentes
		Vendo diferentes tempos de execução Big O
		A notação Big O estabelece o tempo de execução para a pior hipótese
		Alguns exemplos comuns de tempo de execução Big O
		O caixeiro-viajante
	Recapitulando
2
Ordenação por seleção
	Como funciona a memória
	Arrays e listas encadeadas
		Listas encadeadas
		Arrays
		Terminologia
		Inserindo algo no meio da lista
		Deleções
	Ordenação por seleção
	Recapitulando
3
Recursão
	Recursão
	Caso-base e caso recursivo
	A pilha
		A pilha de chamada
		A pilha de chamada com recursão
	Recapitulando
4
Quicksort
	Dividir para conquistar
	Quicksort
	Notação Big O revisada
		Merge sort versus quicksort
		Caso médio versus pior caso
	Recapitulando
5
Tabelas hash
	Funções hash
	Utilização
		Usando tabelas hash para pesquisas
		Evitando entradas duplicadas
		Utilizando tabelas hash como cache
		Recapitulando
	Colisões
	Desempenho
		Fator de carga
		Uma boa função hash
	Recapitulando
6
Pesquisa em largura
	Introdução a grafos
	O que é um grafo?
	Pesquisa em largura
		Encontrando o caminho mínimo
		Filas
	Implementando o grafo
	Implementando o algoritmo
		Tempo de execução
	Recapitulando
7
Algoritmo de Dijkstra
	Trabalhando com o algoritmo de Dijkstra
	Terminologia
	Adquirindo um piano
	Arestas com pesos negativos
	Implementação
	Recapitulando
8
Algoritmos gulosos
	O problema do cronograma da sala de aula
	O problema da mochila
	O problema da cobertura de conjuntos
		Algoritmos de aproximação
	Problemas NP-completos
		Caixeiro-viajante, passo a passo
		Como faço para saber se um problema é NP-completo?
	Recapitulando
9
Programação dinâmica
	O problema da mochila
		A solução simples
		Programação dinâmica
	Perguntas frequentes sobre o problema da mochila
		O que acontece se você adicionar um item?
		O que acontece se você modificar a ordem das linhas?
		É possível preencher a tabela a partir das colunas, em vez de a partir das linhas?
		O que acontece se você adicionar um item menor?
		Você consegue roubar frações de um item?
		Otimizando o seu itinerário de viagem
		Lidando com itens com interdependência
		É possível que a solução requeira mais de dois subproblemas?
		É possível que a melhor solução não utilize a capacidade total da mochila?
	Maior substring comum
		Criando a tabela
		Preenchendo a tabela
		A solução
		Maior subsequência comum
		Maior subsequência comum – solução
	Recapitulando
10
K-vizinhos mais próximos
	Classificando laranja versus toranjas
	Criando um sistema de recomendações
		Extração de características
		Regressão
		Escolhendo boas características
	Introdução ao aprendizado de máquina
		OCR
		Criando um filtro de spam
		Prevendo a bolsa de valores
	Recapitulando
11
Próximos passos
	Árvores
	Índices invertidos
	A transformada de Fourier
	Algoritmos paralelos
	MapReduce
		Por que os algoritmos distribuídos são úteis?
		Função map
		Função reduce
	Filtro de Bloom e HyperLogLog
		Filtros de Bloom
		HyperLogLog
	Algoritmos SHA
		Comparando arquivos
		Verificando senhas
	Hash sensitivo local
	Troca de chaves de Diffie-Hellman
	Programação linear
	Epílogo
Respostas dos exercícios