CCM0128 - Computação II (2022i)

Neste exercício, você resolverá o Web Exercise 2.6.29 (Bandwidth) de S&W; veja

https://algs4.cs.princeton.edu/25applications/

Você deve escrever uma classe chamada Bandwidth.java que contém um método estático de assinatura

public static int compute(Interval1D[] interval)

Esse método deve devolver o bandwidth dos intervalos dados no array interval. Seu método será testado executando-se o programa BandwidthDriver.java, dado abaixo. Outros testes poderão também ser feitos.

Bandwidth.  Considere os seguintes 10 intervalos de números reais:

0: [1.3564800366308147, 2.904559863168301]
1: [2.376320375308487, 3.460925753154503]
2: [2.6127841259343287, 3.0645131257612372]
3: [3.0210369881609087, 5.7289852771115335]
4: [3.2117082930801595, 4.4990131983008625]
5: [4.207982564845575, 4.522280417642641]
6: [4.525866477912476, 4.893267510590301]
7: [5.683085805892479, 8.80639445330453]
8: [5.696203157819235, 7.432541180202275]
9: [6.570510841210109, 7.158344183216937]

Um diagrama representando esses intervalos é dado no arquivo 10.png dado abaixo (os intervalos são dados em três grupos, devido às interseções entre os intervalos).

Imagine que cada um dos 10 intervalos acima corresponde a uma ligação telefônica de uma cidade A para uma cidade B (cada intervalo corresponde ao intervalo de tempo da ligação, isto é, o intervalo \([a, b]\) corresponde a uma ligação que começou no instante $a$ e terminou no instante $b$).  Suponha que cada ligação "ocupa uma unidade de banda" (ou "ocupa um canal").  A companhia telefônica que administra as ligações de A para B consegue lidar com o conjunto de 10 ligações (10 intervalos) no exemplo acima desde que a companhia tenha largura de banda maior ou igual a 3 entre A e B: as ligações 0, 3 e 9 podem ser roteados por um canal, 1, 5 e 8 por um segundo canal, e 2, 4, 6 e 7 por um terceiro canal.  É fácil ver que dois canais não seriam suficientes (veja 10.png).

Dado um conjunto de intervalos $S$, a largura de banda de $S$ é o número mínimo de canais para "rotear" o conjunto $S$.

Interval1D.java.  S&W disponibilizam uma classe para trabalhar com intervalos de números reais, chamada Interval1D.java. Veja Creative Problem 2.5.27 (Interval 1D data type) em

https://algs4.cs.princeton.edu/25applications/

Seu método compute() deve receber um array de Interval1D.

Observação.  Observe que MinPQ.java admite a possibilidade de se dar um Comparator como parâmetro: nesse caso, a ordem das chaves é aquela definida pelo comparator dado.

Instâncias geradas em BandwidthDriver.java.  BandwidthDriver.java gera instâncias aleatórias para o problema de cálculo de largura de banda. O começo de cada intervalo é gerado usando-se uma distribuição exponencial:

https://en.wikipedia.org/wiki/Exponential_distribution?msclkid=f47b084fc31911ec9925ff37e9c8daa4

Como usamos uma exponencial de parâmetro $1$ entre os começos dos intervalos, em média temos um novo intervalo a cada unidade de tempo. Para decidir o comprimento de cada intervalo, usamos uma exponencial de parâmetro $L$, dado pelo usuário (assim, o comprimento esperado de cada intervalo é $1/L$).

Exemplos de execução.  Uma vez que você tenha escrito seu programa Bandwidth.java, ao executar BandwidthDriver.java, você obterá uma saída semelhante à seguinte saída:

$ java-algs4 BandwidthDriver 10 .5 128
Time to generate instance: 0.003s
Bandwidth: 3
Time to compute bandwidth: 0.003s
$

Sua função compute() não deve ser muito mais demorada do que o gerador de instâncias em BandwidthDriver.java:

$ java-algs4 BandwidthDriver 1000000 .5 128
Time to generate instance: 0.119s
Bandwidth: 13
Time to compute bandwidth: 0.11s
$ java-algs4 BandwidthDriver 10000000 .5 128
Time to generate instance: 0.67s
Bandwidth: 15
Time to compute bandwidth: 0.52s
$

Quando os intervalos são mais longos, o bandwidth será maior, e compute() pode também ser levemente mais demorado:

$ java-algs4 BandwidthDriver 10000000 .01 128
Time to generate instance: 0.646s
Bandwidth: 152
Time to compute bandwidth: 1.203s
$ java-algs4 BandwidthDriver 10000000 .001 128
Time to generate instance: 0.666s
Bandwidth: 1139
Time to compute bandwidth: 1.619s
$ java-algs4 BandwidthDriver 10000000 .0001 128
Time to generate instance: 0.662s
Bandwidth: 10405
Time to compute bandwidth: 2.241s
$

Mais alguns exemplos de execução são dados nos arquivos experiments.txt e experimentsGNU.txt.

Entrega.  Neste exercício, entregue apenas sua classe Bandwidth.java.