Materiale didattico
Il materiale didattico a supporto del laboratorio di algoritmi e strutture dati verrà messo a disposizione su questo sito. Indicativamente, il materiale sarà raggruppato per moduli settimanali.
Prima settimana (28 e 29 settembre 2016)
- Lucidi: introduzione a Linux
- Lucidi: introduzione al linguaggio C (compilatore, tipi built-in, input/output)
- Scheda: primi programmi
Seconda settimana (5 e 6 ottobre 2016)
Terza settimana (12 e 13 ottobre 2016)
Quarta settimana (19 e 20 ottobre 2016)
Quinta settimana (26 e 27 ottobre 2016)
- Lucidi: uso avanzato di puntatori e allocazione dinamica della memoria
- Scheda: esercizi su array frastagliati, argomenti da linea di comando, allocazione dinamica della memoria.
Sesta settimana (2 e 3 novembre 2016)
Settima settimana (9 e 10 novembre 2016)
Ottava settimana (23 e 24 novembre 2016)
- Lucidi: paradigma client-interfaccia-implementazione.
- Scheda: esercizi sulla pila come esempio di struttura dati astratta.
Nona settimana (30 novembre e 1 dicembre 2016)
- Lucidi: code di priorità e heap.
- Scheda: esercizi su heap e code di priorità.
- Scheduling
- Scheda su attività "festival del cinema"
- Software di supporto
- Scheda su "festival del cinema" compilata
- Traccia per l'implementazione della strategia greedy per il problema dello scheduling
Decima settimana (15 e 16 dicembre 2016)
- Lucidi: alberi binari e alberi binari di ricerca.
- Scheda di esercizi su alberi binari e esempio di applicazione (occorrenze di parole in un testo). Se preferite, potete partire direttamente dall'esercizio 2 e concentrarvi sul modulo "occorrenze" utilizzando l'implementazione degli alberi binari di ricerca forniti in bistree.zip.
- Alcuni quesiti giocosi tratti dal Kangourou dell'Informatica e dal Bebras dell'Informatica. Le soluzioni dei quesiti Bebras saranno pubblicate a breve sul sito della competizione; le soluzioni commentate dei quesiti Kangourou, tratte dai libretti pubblicati nell'archivio online della competizione, sono raccolte qui.
Undicesima settimana (21 dicembre 2016)
- Lucidi: preparati dal collega Prof. Stefano Aguzzoli, contengono una presentazione sull'implementazione dei grafi come liste di adiacenza e le visite in prfondità e in ampiezza.
- Estratti di alcuni progetti proposti in appelli passati e analizzati a lezione.
- Scheda di esercizi sulla struttura dati grafo.
- Altri estratti di progetti da analizzare per esercizio.
Dodicesima settimana (11 e 12 gennaio 2017)
- Lucidi: programmazione dinamica: scheduling di intervalli pesati e zaino eparati
- Scheda: tutti gli esercizi sono risolubili con tecniche di programmazione dinamica; la parte difficile non è la scrittura del codice vero e proprio, ma l'analisi dei problemi, la loro riduzione a sottoproblemi, la costruzione di algoritmi efficienti; gli esercizi sono indipendenti tra loro, ma in ordine di difficoltià.
- I più coraggiosi possono anche cimentarsi nell'esercizio Uffici postali, proposto alle Olimpiadi dell'Informatica qualche anno fa!