Schema tipologie esercizi, Algoritmi & Strutture Dati, prof. Emilio Di Giacomo

Nota sui possibili casi

1 NOTA: 3 possibili casi

Ricorrenze

Teorema dell’esperto

• Tipo 1
• Tipo 2
• Tipo 3
• Tipo 4

Metodo di sostituzione

Nota: può accadere che:

• Il caso base NON verificato
• Tipo 1 > caso induttivo NON verificato
• Può capitare che Θ al posto di O(lg n) ci mette oppure “theta” tipo 2

NOTA: si usa l’albero di ricorsione, poi si verificano le soluzioni con il metodo di sostituzione in generale.

Notazioni asintotiche

• Tipo 1

Domande teoriche random

2 Domanda teorica random

Alberi binari

• Tipo 1
• Tipo 2
• Tipo 3
• Tipo 4
• Tipo 5

Alberi rosso-nero

• Tipo 1
• Tipo 2

Tabelle hash

(indirizzamento aperto - liste trabocco)

• Tipo 1
• Tipo 2

Heap-sort

• Tipo 1
• Tipo 2

Algoritmi di ordinamento per confronti

• Tipo 1

Alberi binomiali

• Tipo 1

Heap-binomiali e heap-binari

• Tipo 1
• Tipo 2
• Tipo 3
• Tipo 4

Algoritmo di Dijkstra

• Tipo 1
• Tipo 2

Algoritmo di Kruskal e Prim (Minimum Spanning Tree)

• Tipo 1
• Tipo 2

Programmazione dinamica e algoritmi golosi

3 Progr. dinamica – Alg.Golosi

Alberi (abr) o m-ari - Grafi

4 Alberi (abr) o M-ari - Grafi