PAA Exercícios Práticos

Prévia do material em texto

QXD0041 Exercício Prático 2014.1
UNIVERSIDADE FEDERAL DO CEARÁ
E1Campus de Quixadá
Prof. Arthur Araruna
QXD0041- Projeto e Análise de Algoritmos 2014.1
Nome: Matrícula:
1. Suponha que lhe são dados dois vetores ordenados A e B com n elementos cada um, e um inteiro
positivo k. Tente desenvolver um algoritmo que determina o k-ésimo menor elemento dentre todos os
elementos de A e B juntos.
Qual a complexidade do seu algoritmo?
Você consegue desenvolver um programa para resolver esse problema cujo algoritmo tenha complexi-
dade O(lg n)?
2. Vamos desenvolver um algoritmo de divisão e conquista para calcular o perfil do horizonte de um
conjunto de n edifícios.
Imagine que todos os edifícios de uma cidade tenham formado retangular e perpendicular ao chão.
Vamos representar um edifício i por três informações: suas coordenadas x inicial e final, Ei e Di res-
pectivamente, e sua altura, Hi .
O perfil de horizonte de um conjunto de n edifícios é uma sequência de coordenadas x e alturas
conectando-as em ordem, da esquerda para a direita.
Por exemplo: o perfil dos edifícios
{(3,9,13); (1,5,11); (12,16,7); (14,25,3); (19,22,18); (2,7,6); (23,29,13); (23,28,4)}
é a sequência
{1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,29,0}
(note que as coordenadas x do perfil, com destaque em negrito, são exibidas em ordem).
Figura 1: Visualização do conjunto de edifícios e de seu respectivo perfil de horizonte.
Escreva um programa que receba a quantidade de edifícios e a representação de cada edifício e calcule
o perfil de horizonte deles.
3. Você está numa convenção política com n delegados, cada um membro de exatamente um partido polí-
tico. É impossível dizer a que partido cada delegado pertence; em particular, você seria sumariamente
expulso da convenção se perguntasse a alguém. Entretanto, você pode determinar caso dois delegados
pertencem a um mesmo partido ou não apresentando-os um ao outro – membros de um mesmo partido
sempre se cumprimentam com sorrisos e apertos de mão amigáveis; membros de partidos diferentes
sempre se cumprimentam com olhares tensos e insultos.
QXD0041 Exercício Prático 2014.1
Suponha que a maioria dos delegados (mais da metade) dos delegados pertencem a um mesmo partido
político. Tente desenvolver um programa que identifica se um dado membro pertence a esse partido
(qualquer que seja esse membro).
Qual é a complexidade do seu algoritmo?