joaoarthurbm / eda Goto Github PK

No material de análise assintótica.

1, log, n, n log n, n2...

me parece mais uma técnica de visualização do que aproximação propriamente dita.

• Mais blockquote destacando aspectos importantes
• M para tamanho da tabela, N para número de elementos
• fazer slide

No material de "Filas (FIFO) baseadas em Arrays" no método de "addLast", ao checar se a fila está cheia ele acrescenta +1 % (tamanho do array). Onde na verdade deveria ser reatribuído o valor à variável: this.head = (this.head + 1) % this.fila.length, para evitar o indexOutOfBounds.

Percebi esse errinho nos nomes das variáveis no material de quicksort, o v era pra ser values que é o array que está sendo ordenado

if deve ser minúsculo.

If (ini < fim) {

Ω: g(n) é um limite inferior para g(n).
ω: g(n) é um limite inferior (não incluso) para g(n).

Deveria ser f(n).

Os nós 47 e 54 estão nos índices 3 e 4, respectivamente. Portanto, o nó pai está no índice 1, pois $int((3-1)/2)) = 1$ e $int((4-1)/2)) = 1$.

Já tem o vídeo: https://www.youtube.com/watch?v=D3tBsXpcnpI

No parágrafo após a simplificação da primeira equação tá escrito "Agora sim, é muito mais direto olhar para n2 ter uma ideia clara do crescimento do tempo de execução do algoritmo,".

Parece que o certo seria "é muito mais direto olhar para n2 e ter uma ideia [...]"

No material sobre Análise de Algoritmos Recursivos, mais precisamente no exemplo de busca binária (método indexOf), o caso base está desconsiderando algumas possibilidades, o que causará falhas em algumas situações. Por exemplo, quando o array possui apenas 1 elemento e desejamos realizar a busca binária desse elemento específico, a falha ocorrerá devido à falta de consideração do caso em que leftIndex é igual a rightIndex e o valor esperado está exatamente nessa igualdade.

No texto do quiz os últimos 2 arrays tem seus elementos separados por vírgula, transformando cada um em uma alternativa:
{{< item question="Qual o estado final do array [7, 8, 1, 2, 90, 4, 65, 32] após o particionamento hoare escolhendo 7 como pivot?" answers="5" choices=" [4 - 2 - 1 - 7 - 90 - 8 - 65 - 32], [4 - 1 - 2 - 7 - 8 - 90 - 65 - 32] , [4 - 2 - 1 - 7 - 90 - 8 - 65 - 32], [2, 1, 4, 7, 90, 8, 65, 32], [2, 4, 1, 7, 90, 8, 65, 32]">}}

Substituir por:
{{< item question="Qual o estado final do array [7, 8, 1, 2, 90, 4, 65, 32] após o particionamento hoare escolhendo 7 como pivot?" answers="5" choices=" [4 - 2 - 1 - 7 - 90 - 8 - 65 - 32], [4 - 1 - 2 - 7 - 8 - 90 - 65 - 32] , [4 - 2 - 1 - 7 - 90 - 8 - 65 - 32], [2 - 1 - 4 - 7 - 90 - 8 - 65 - 32], [2 - 4 - 1 - 7 - 90 - 8 - 65 - 32]">}}

https://joaoarthurbm.github.io/eda/posts/introducao-a-analise/

No exemplo com loops aninhados, está escrito:

Como c7 é executada uma vez a menos que c6, então temos que o primeiro termo da PA é a1=1 e an=n−1. Assim, temos que c7 é executada n2/2.

No meu entendimento a PA de c7 teria a1 = 0, pois quando o último valor de i seria n-1, resultando em j = n e não ocorreria a operação c7 = j++ nesse caso. Nesse caso, pela fórmula da soma da PA, teríamos: S=n/2∗(0+n-1) = (n^2-n)/2.
Outro forma de pensar seria que c7 ocorre uma vez a menos que c6 em cada iteração do for, de modo que seriam n ocorrências a menos e portanto c7 = c6 - n = (n^2+n)/2 - n = (n^2 - n)/2.

Se tiver algum erro em meu raciocínio, gostaria de saber.
Obrigado!

Implementação aqui: https://github.com/joaoarthurbm/eda-implementacoes/blob/master/python/src/sorting/radix.py

No material de algoritmos recursivos as funções não estão bem formatadas.

Se f(n) < n ** logba, então T(n) = \Theta(n ** logba).

Se f(n) = n ** logba, então T(n) = \Theta(f(n) * logbn).

Se f(n) > n ** logba, então T(n) = \Theta(f(n)).

Ou seja, do ponto de vista da ordem de crescimento, para grandes valores de n, as constantes e os expoentes de maior magnitude são insignificantes, nos permitindo simplificar a expressão do tempo de execução ...

Na aula sobre Quick Sort é mencionado sobre o particionamento de Hoare e há um link para um material sobre o assunto, porém o link está quebrado.

https://joaoarthurbm.github.io/eda/posts/linkedlist/

size -= 1;

Na teoria e na prática

Na comparação: "if (index < 0 || index > size)", na verdade deveria ser "index >= size" como discutimos em sala de aula hoje

No material sobre ArrayList, a classe ArrayList tem como atributo uma lista de elementos do tipo inteiro, mas fazemos operações com elementos da classe Aluno. Além disso, os dois métodos de Remoção de elementos são listados sem especificar seu retorno, só é possível saber disso olhando os trechos de código que se seguem.

No material sobre QuickSort há referências para outros materiais, como Heap Sort e o particionamento de Hoare. Contudo, como estes materiais ainda não foram escritos por sua autoria, acredito que seria mais amigável caso os links redirecionassem, por enquanto, para algum site como o Wikipedia, que introduz o tema. Ou nas notas, no final do material, poderia citar em qual capítulo do livro pode ser estudado o assunto ou algum material referente.

No método add do material de LinkedList o seguinte trecho:
if (index == 0) {
this.addFirst(valor);

} else if (index == size - 1) {
    this.addLast(valor);

}
o parâmetro (valor) do this.addFirst e this.addLast deveria ser (aluno) ?

Explicar o porquê de se efetuar a soma cumulativa no array de frequência do counting sort. O que cada número quer dizer?