Problemi del corso Algoritmi

Nome	Descrizione	Codice
torre di Hanoi	Listare le mosse per spostare una torre di Hanoi di n dischi	hanoi.c
Enumerare piastrellature	Quanti sono i tiling di un array 1xn con piastrelle 1x1 oppure 1x2? Trovata la ricorrenza, scrivete un codice che listi le varie soluzioni.	enumPiastrellature.c
Calcolare efficacemente il numero di piastrellature avvalendosi della ricorrenza	Se scriviamo una funzione ricorsiva è un disastro, le fatine ricorsine crescono come i conigli. Sperimentiamo su questo semplice problema la tecnica della ricorsione con memoizzazione.	fibonacci_memoizzazione.c
Enumerare permutazioni	Lista tutte le permutazioni di un certo set di oggetti	listPermutations.cpp
Generare una permutazione random (con distribuzione uniforme)	Dato n, produrre una permutazione di {1, 2, ..., n} a caso, con distribuzione uniforme	randPerm.cpp. Come servirsene: usa redirezione su file per creare file input.txt
Ranking ed unranking di permutazioni.	Abbiamo visto come listare permutazioni (e lo stretto legame con la generazione di una permutazione random). Sapresti anche trovare la permutazione t-esima (unranking)? E, data una permutazione, sapresti trovarne il numero d'ordine t (ranking)? Si noti come l'unranking fornisca un metodo effettivo per produrre una permutazione random a partire da un numero random tra 1 e n!	rankPerm.pdf
Enumerare parentesizzazioni	Enumerare tutte le formule ben formate di n parentesi aperte "(" e n parentesi chiuse ")" Sapresti anche trovare la parentesizzazione t-esima (unranking)? E, data una parentesizzazione, sapresti trovarne il numero d'ordine t (ranking)?
Enumerare sottoinsiemi	Enumerare tutti i sottoinsiemi di cardinalità k di un insieme di cardinalità k. Sapresti anche trovare il k-sottoinsieme t-esimo (unranking)? E, dato un k-sottoinsieme, sapresti trovarne il numero d'ordine t (ranking)?
Enumerare scomposizioni di un naturale	Enumerare tutte le scomposizioni essenzialmente diverse di un numero naturale dato in input come somma di naturali positivi. Sapresti anche gestire il ranking e l'unranking?
integer random sequence	Genera una sequenza random di interi	randSeq.cpp. Come servirsene: usa redirezione su file per creare file input.txt
heapSort	Ordinamento basato su heap, utile anche per implementare code di priorità	heapSort.cpp
ricerca in database di numeri	in input n + m numeri, dire quali degli m numeri del secondo lotto apparivano anche nel primo lotto e dove.
Somme Rettangolo	È fornito un rettangolo di numeri e poi arriva una sfilza di queries del tipo: quanto vale la somma su questo o quello sottorettangolo?
Somme rapide con updates	come nel problema precedente, solo che ora le entries della matrice sono soggette a degli updates. Per semplificarlo, si affronti il caso particolare che il rettangolo (matrice) sia solo un intervallo (array).
cellulari	Tenere traccia delle connessioni su una griglia di telefonia cellulare.
Borse di Studio	Ripartire un dato budget in premi a calare.
Triangolo	Da ricorsione, a memoizzazione, a programmazione dinamica: In un triangolo di numeri, ricercare un cammino a somma massima discendente dal vertice.
massima sottosequenza crescente	Da ricorsione, a memoizzazione, a programmazione dinamica: data una sequenza di numeri S, trovare la più lunga sequenza crescente che sia sottosequenza di S	maxIncSubseq.c implementa una soluzione quadratica. Riesci a trovare una soluzione O(n log n) ?
La dieta di Poldo	L'importante è andare crescendo.
Poldo su DAG	Ai nodi di un DAG, osterie di una città, sono associati dei numeri (tassi alcolici). Vogliamo trovare il percorso con più soste, sempre rigorosamente ligi alla solita dieta.
massima sottosequenza comune	date in input due stringhe, trovare la più lunga stringa che sia sottosequenza di entrambe. Una stringa è sottosequenza di un'altra se la si ottiene da essa saltando delle posizioni.	confronto di 3 metodi: programmazione dinamica, ricorsione semplice, ricorsione con memoizzazione
matching approssimato di stringhe	computo dell'edit distance tra due stringhe	un codice in C, e un codice rivisto in C++,
il problema dello zaino e sue varianti (solo pesi, pesi e valori, oggetti ripetuti).
Parentesizzazione ottima	Computa una parentesizzazione ottima per il prodotto di una sequenza di matrici	confronto di 3 metodi: programmazione dinamica, ricorsione semplice, ricorsione con memoizzazione
Sorting by Reversals	Riordinare una permutazione di 1,2, ...,n con il minor numero di rovesciamenti di intervalli.	un algoritmo branch and bound
specchio	Rovesciare un albero in un particolare encoding.
bianconero	Minimo numero di operazioni di taglia e cuci su collanna per rendere consecutive perle dello stesso colore.
condominio	Listare velocemente i cicli diretti di un grafo diretto. Esempio di problema di listing. Qui l'obiettivo è essere efficaci nell'output.
Conteggio di occorrenze di una sottosequenza	Una sottosequenza di una sequenza S si ottiene da essa eliminandone zero o più elementi. Quindi Z = z₁ z₂ . . . z_k è una sottosequenza di X = x₁ x₂ . . . x_m se vi è una sequenza strettamente crescente di indici < i₁, i₂, . . . , i_k > riferiti a X tali che per ogni j = 1, 2, . . . , k, si ha che x_{i_j} = z_j. Ad esempio, Z = bcdb e' la sottosequenza di X = abcbdab che corrisponde alla sequenza di indici < 2, 3, 5, 7 >. Contare il numero di occorrenze di Z in X, come sottosequenza, dove Z e X sono sequenze date in input e dove due occorrenze sono considerate distinte se associate a diverse sequenze di indici.
taglio di profilato	una lunga barra va tagliata in un prefissato insieme di posizione (ad esempio la barra è lunga 10 e va tagliata nelle posizioni distanti 2, 4, e 7, dal bordo sinistro) ma il costo di ogni taglio è lineare nella lunghezza della barra al momento del taglio. L'ordine in cui si effettuano i tagli influisce quindi sul costo complessivo. (Se uno taglia prima a 2, poi a 4, e poi a 7, allora paga 10+8+6=24 mentre se taglia prima a 4, poi a 2, e poi a 7, allora paga 10+4+6=20). Minimizzare i costi.
bus	Scelta ottima dei due nodi hub per una rete.	bus.cpp
depot	Ricostruire tutte le possibili storie di un deposito.	depot
fili ed interruttori	Insistendo su una tecnica algoritmica (e strategia militare romana).
Forza Mediana	Insistendo su una tecnica (e strategia), o meglio riducendo un problema ad un altro.
Massima sottosequenza palindroma	Ricerca della massima sottosequenza palindroma di una stringa fornita in input.	palin.c
Uffici Postali	Collocando un numero limitato di facilities (uffici postali) su una linea	post.c
Gioco del 15	Quale è il minimo numero di mosse che consente di risolvere una certa configurazione nel gioco del 15.
Cubo di Rubik	Quale è il minimo numero di mosse che consente di risolvere una certa configurazione del cubo di Rubik.
Sudoku	Data una certa configurazione di Sudoku, stabilire se sia consistente. Nel caso affermativo si avvii il listing delle varie soluzioni.
Domino	Dato un certo insieme di tessere del domino si stabilisca se sia possibile calarle tutte sul tavolo in un unico serpente. In caso contrario si stabilisca il minimo numero di serpenti.
robot in Campo Minato
coniglio su linea con erba che invecchia
shuffling di stringhe
zaino bidimensionale (peso e ingombro in litri).
collage di un arcobaleno,
variazioni e miscellanea di programmazione dinamica	variazioni tipicamente cucinabili per problemi risolti con programmazione dinamica: contare le sottosequenze crescenti di data lunghezza, sottosequenza crescente a somma massima, quante sono le soluzioni ottime per un problema dello zaino.
Giochi e programmazione dinamica	Come sfruttare un'approccio di programmazione dinamica per esplorare il problema di uova da condominio. Qualche gioco posizionale a due giocatori: Gioco della rana con passi da 1 o da 2. Caratterizzazione delle posizioni "chi tocca perde". Gioco con barra di cioccolato a quadretti, con la rgola che quando uno spezza resta in gioco la parte piccola.
longest 321-free subsequence.
data una sequenza di numeri, trovarne la più lunga sottosequenza che non contenga sottosequenze decrescenti di lunghezza k
Riconoscimento di DAGs	decidere se un dato digrafo è un DAG
trovare il kernel di un DAG
trovare il cammino piu' lungo in DAG.
Partizione in Triplette	Partizionare un set di 3n numeri in triplette di costo lo scarto quadratico tra i due numeri grandi.
Matrioska	problema delle scatole cinesi, ossia, dati dei parallelepipedi, ricercare il numero massimo di parallelepipedi che possiamo collocare uno dentro l'atro (i parallelepipedi possono essere ruotati ma comunque vanno collocati ortogonalmente agli assi). Magari provate prima in 2 e solo poi in 3 dimensioni.
Node cover su alberi	Approccio greedy basta per trovare minimo node cover in un albero, ma nel caso pesato (costi sui nodi) serve allora un approccio di programmazione dinamica
k-card tree su alberi	Con un approccio di programmazione dinamica, trovare il sottoalbero di cardinalit&agrae; k e costo minimo di un albero pesato dato in input.
Node cover approssimati	2-approssimazioni per problemi di tipo node cover
Node Cover esatti	branch and bound per node cover minimi, approcci FPT per node covers piccoli su grafi anche grandi
Set Cover	approssimazioni O(log n) per problemi di set cover
Minimum Maximal Matching	dare una 2-approssimazione per il seguente problema: un matching in un grafo è un sottoinsieme di archi M tale che nessun nodo è incidente a più di un arco in M; un matching è detto massimale se aggiungendoci un qualsiasi arco del grafo smette di essere un matching; trovare un matching massimale di minima cardinalità. Il problema rimane NP-completo, e quindi interessante da approssimare, anche su grafi bipartiti.
Minimum Maximal Matching esatto	branch and bound per la ricerca di maximal matchings minimi, approcci FPT per maximal matchings su grafi anche grandi. Interessante anche il caso bipartito.

created: 1 marzo 2012
updated: 22 maggio 2012