MAC323 Algoritmos e estruturas de dados II

• Você deve inicialmente recordar o Creative exercise 4.4.8 (IP lookup by country) de IntroCS, que você já fez.
• Dessa vez, você deve usar o arquivo dbip-city-2015-05h.csv (que tem 4920676 linhas), de https://db-ip.com/db/ ("IP address to city (low resolution)").
• Seu programa deve receber o nome de arquivo dbip-city-2015-05h.csv na linha de comando. Se houver apenas esse argumento, seu programa deve receber uma lista de endereços IP na entrada padrão. Para cada entrada padrão, seu programa deve imprimir as informações encontradas em dbip-city-2015-05h.csv, no formato do exemplo abaixo.
  • Exemplo:

$ cat IPs 
143.107.45.22
143.108.10.6
200.130.33.22
140.180.223.42
169.229.216.200
131.111.59.156
210.152.135.178
195.220.216.32
188.93.105.22
$ java-algs4 IPLookUpDeLuxe dbip-city-2015-05h.csv < IPs
Miami, Mato Grosso Do Sul, BR
Miami, Mato Grosso Do Sul, BR
Palmas, Tocantins, BR
Princeton, New Jersey, US
San Francisco, California, US
Cambridge, Cambridgeshire, GB
Minato, Tokyo, JP
Paris, Île-de-France, FR
Moscow, Moscow, RU

(Você pode notar que o banco de dados não é completamente sem erros.)

• Se o usuário executar seu programa com mais de um argumento na linha de comando, ele deve ler da entrada padrão um arquivo como este. Este arquivo foi extraído do arquivo system.log de um sistema que permite acesso remoto por ssh. Esse arquivo mostra tentativas de acesso ilícito de máquinas diversas. Seu programa deve extrair os números IPs de onde vêm essas tentativas de acesso ilícito e deve usar o arquivo dbip-city-2015-05h.csv para localizar a origem geográfica desses acessos. Cada local de origem deve ser impresso uma única vez, junto com o número de tentativas de acesso daquele local. Esta lista deve ser impressa ordenada pelo número de tentativas de acesso, em ordem decrescente.
  • Exemplo:

$ cat ssh.log
May 27 00:01:32 machine.ime.usp.br sshd[33205]: Invalid user adam from 175.126.111.86
May 27 00:09:00 machine.ime.usp.br sshd[33213]: Invalid user carol from 175.126.111.86
May 27 00:12:57 machine.ime.usp.br sshd[33218]: Invalid user chloe from 175.126.111.86
May 27 00:17:04 machine.ime.usp.br sshd[33223]: Invalid user chloe from 175.126.111.86
…
$ java-algs4 IPLookUpDeLuxe dbip-city-2015-05h.csv - < ssh.log
1672 Seoul, Seoul, KR
718 Phoenix, Arizona, US
316 Kiev, Kyiv city, UA
269 Tunis, Tunis, TN
178 Nanchang, Jiangxi, CN
…

• Você deve implementar sua solução com ST.java, RedBlackBST.java e BST.java (são portanto três implementações distintas). Compare o desempenho dessas três implementações.

---

Página principal de MAC323, 1o. semestre de 2015

---