Algo2 pt1

Flashcards per Algo2 con Gualà.

Descrivi il problema dell’Interval Scheduling.

Definisci l’approccio greedy per l’Interval Scheduling. Elenca tutti i possibili ordinamenti. Fornisci un controesempio per gli errati.

Scrivi l’algoritmo Earliest-finish-time-first per l’Interval Scheduling. Analizzane la complessità temporale.

Determina come opererà l’algoritmo Earliest-Finish-Time per l’Interval Scheduling su questa demo.

Enuncia e analizza il lemma per l’Interval Scheduling.

Dimostra che l’algoritmo Earliest-finish-time-first per l’Interval Scheduling è ottimale.

Definisci il problema dell’Interval Partitioning.

Delinea l’approccio greedy per l’Interval Partitioning e tutti gli ordinamenti possibili. Fornisci un controesempio per quelli errati.

Definisci l’algoritmo Earliest-Start-Time-First per l’Interval Partitioning.

Mostra come opera l’algoritmo Earliest-Start-Time-First per l’Interval Partitioning su questa demo.

Analizza e dimostra la complessità dell’algoritmo Earliest-Start-Time-First.

Definisci la depth per l’Interval Partitioning. Come è correlata al numero di classi necessarie?

Dimostra l’ottimalità dell’algoritmo Earliest-Start-Time-First per l’interval partitioning.

Descrivi il problema UnionFind.

Descrivi come funziona l’approccio QuickFind per UnionFind.

Descrivi la realizzazione dell’approccio QuickFind.

Descrivi la sequenza di operazioni e il risultato per questo esempio, usando l'approccio QuickFind.

Descrivi la debolezza principale dell’approccio QuickFind.

Descrivi l’idea dietro l’euristica UnionSize per QuickFind.

Descrivi la sequenza di operazioni e il risultato per questo esempio, usando l'approccio QuickFind con UnionSize.

Descrivi la realizzazione dell’approccio QuickFind con UnionSize.

Fornisci e dimostra l’analisi ammortizzata per QuickFind con UnionSize.

Descrivi l’approccio QuickUnion per il problema UnionFind.

Descrivi la realizzazione delle operazioni per l’approccio QuickUnion.

Descrivi la sequenza delle operazioni e il risultato per questa demo usando l’approccio QuickUnion.

Descrivi il problema principale dell’approccio QuickUnion.

Descrivi l’euristica Union by size per QuickUnion.

Descrivi la sequenza delle operazioni e il risultato per questa demo usando l’approccio QuickUnion con euristica Union by size.

Fornisci l’analisi ammortizzata per l’approccio QuickUnion con euristica Union by Size.

Descrivi l’euristica di compressione dei cammini per UnionFind.

Fornisci la complessità ammortizzata di QuickUni+Unionbysize+Compressione cammini in relazione alla funzione di Ackermann inversa.

Fornisci la definizione di MST.

Fornisci il problema dell’MST.

L’MST è sempre unico?

Definisci un ciclo, un cut e un cutset.

Descrivi il rapporto tra ciclo e cutset.

Esponi e dimostra la Cut Property.

Esponi e dimostra la Cycle Property.

Fornisci l’idea generale dietro l’algo di Kruskal.

Fornisci lo pseudocodice di Kruskal.

Dimostra la correttezza di Kruscal.

Analizza la complessità di Kruscal.

Simula l’esecuzione di Kruscal su questa demo.

Esponi l’idea dietro l’algoritmo di Prim. Dimostrane la correttezza.

Fornisci un’implementazione efficiente per l’algoritmo di Prim.

Fornisci lo pseudocodice per l’algoritmo di Prim. Analizzane il costo.

Simula l’esecuzione di Prim su questa demo.

Introduci il problema del clustering e del k-clustering a massimo spacing.

Fornisci un algoritmo per la risoluzione del k-clustering a massimo spacing.

Dimostra questa proprietà.

Introduci il problema dell’Independent Set di peso massimo.

Ragiona sulla struttura della soluzione per Independent Set di peso massimo, concentrandoti in particolare all’appartenenza del nodo v_n alla soluzione S.

Fornisci un algoritmo per la risoluzione dell’Independent Set di peso massimo, e analizzane il costo.

Fornisci un algoritmo per la ricostruzione della soluzione dell’Independent Set di peso massimo, e analizzane il costo.