Perguntas de 16 pontos sobre design e análise de algoritmos (CS1201): 1. (a) O que é um algoritmo de dividir e conquistar? Explique a abordagem geral dos algoritmos de dividir e conquistar. (6 marcas)
(b) Use a abordagem dividir e conquistar para projetar um algoritmo para encontrar o elemento mínimo em uma matriz de n elementos. Analise a complexidade de tempo do seu algoritmo. (10 pontos)
2. (a) Explique o conceito de técnicas de hashing e resolução de colisão. (6 marcas)
(b) Considere uma tabela hash de tamanho m e um conjunto de n elementos a serem hashados. Suponha que os elementos estejam distribuídos uniformemente entre os m slots. Qual é a probabilidade de uma colisão quando n =m/2? Analise o número médio de comparações necessárias para inserir com êxito todos os elementos na tabela hash usando sondagem linear. (10 pontos)
3. (a) Descreva o conceito de programação dinâmica e explique como ele difere da abordagem de dividir para conquistar. (6 marcas)
(b) Use programação dinâmica para resolver o problema do corte de barras, onde uma barra de comprimento n pode ser cortada em barras menores e cada barra de comprimento i tem um preço p[i]. O objetivo é encontrar o rendimento máximo que pode ser obtido cortando a haste em pedaços menores. Analise a complexidade de tempo e espaço do seu algoritmo. (10 pontos)
4. (a) Explique o conceito de NP-completude e seu significado na análise de algoritmos. (6 marcas)
(b) Prove que o seguinte problema é NP-completo:Dado um conjunto de n itens com seus respectivos pesos e valores, determine se existe um subconjunto desses itens cujo peso total é menor ou igual a um determinado limite e cujo total o valor é maximizado. (10 pontos)
5. (a) Explique o conceito de análise amortizada de algoritmos. Por que é usado e quais são seus benefícios? (6 marcas)
(b) Realize uma análise amortizada da estrutura de dados da pilha, onde as operações push e pop são as únicas operações permitidas. Determine a complexidade média de tempo de cada operação. (10 pontos)
6. (a) Descreva o algoritmo de Kruskal para encontrar a árvore geradora mínima de um grafo não direcionado ponderado. (6 marcas)
(b) Aplique o algoritmo de Kruskal ao gráfico a seguir e encontre a árvore geradora mínima:
```
(1)---2---(3)
/ |
/ |
5/4
-----------
(4)---6---(5)
```
Calcule o peso total da árvore geradora mínima. (10 pontos)
7. (a) Explique o conceito de tipo topológico de grafo acíclico direcionado (DAG). (6 marcas)
(b) Execute uma classificação topológica no seguinte DAG:
```
(1) -> (2) -> (3)
\/
-> (4)
```
Forneça a ordem dos vértices na classificação topológica. (10 pontos)
8. (a) Descreva o conceito de árvores binárias de busca (BSTs). Explique como os BSTs são usados para operações eficientes de pesquisa e inserção. (6 marcas)
(b) Insira os seguintes elementos em um BST inicialmente vazio:20, 10, 30, 5, 15, 25, 35. Desenhe o BST resultante e analise a complexidade de tempo da busca por um elemento neste BST. (10 pontos)
Lembre-se de demonstrar uma compreensão clara dos conceitos, fornecer explicações corretas e analisar as complexidades de tempo e espaço dos algoritmos quando necessário.
