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 settembre e 4 ottobre 2017)

• Lucidi: introduzione a Linux
• Lucidi: introduzione al linguaggio C (compilatore, tipi built-in, input/output)
• Scheda: primi programmi da scrivere a casa
• Scheda: esercizi da svolgere in labratorio

Seconda settimana (5 ottobre e 11 ottobre 2017)

• Appunti sulla funzione scanf
• Lucidi: dati aggregati
• Scheda: esercizi introduttivi su array, stringhe e strutture, da svolgere a casa
• Scheda: esercizi da svolgere in labratorio

Terza settimana (12 e 18 ottobre 2017)

• Lucidi: funzioni
• Scheda: esercizi introduttivi sulle funzioni
• Scheda: esercizi sulle funzioni ricorsive; per svolgere gli esercizi servono i file libpsgraph.c e libpsgraph.h come indicato nella scheda.

Quarta settimana (19 e 25 ottobre 2017)

• Lucidi: puntatori
• Scheda: esercizi su puntatori, da svolgere a casa
• Scheda di esercizi sugli algoritmi di ordinamento per selezione (selectionsort) e per fusione (mergesort). Gli esercizi prevedono l'uso di funzioni ricorsive e array; provate a usare anche i puntatori, ad esempio per scorrere gli array. Per un ripasso degli algoritmi potete fare riferimento a questa presentazione (usate la modalità a schermo intero per visualizzare le animazioni).

Quinta settimana (26 ottobre 2017)

• Lucidi: allocazione dinamica della memoria. Le ultime slide contengono alcuni esempi utili per svolgere gli esercizi della scheda.
• Scheda: esercizi su allocazione dinamica della memoria, da svolgere a casa.

Sesta settimana (2 e 8 novembre 2017)

• Lucidi e esercizi introduttivi, da svolgere a casa, su array frastagliati e argomenti da linea di comando.
• Lucidi e esercizio su liste concatenate.
• Esercizio su array frastagliati (registro di prenotazione) da svolgere in classe

Settima settimana (9 e 15 novembre + 22 novembre 2017)

• Lucidi su alberi binari di ricerca
• Esercizi sugli alberi
• Porzioni di codice relative all'implementazione di alberi binari di ricerca.
• Alcuni quesiti giocosi tratti dal Kangourou dell'Informatica e dal Bebras dell'Informatica.

Ottava settimana (23 e 29 novembre 2017)

• Lucidi: code di priorità e heap.
• Scheda: esercizi su heap e code di priorità.
• Scheduling
  • definizione di problema di ottimizzazione e strategia greedy
  • 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

Nona settimana (30 novembre e 13 dicembre 2017)

• Estratti di alcuni progetti proposti in appelli passati e analizzati a lezione.
• 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.
• Scheda di esercizi sull'implementazione dei grafi.
• Scheda di esercizi sull'uso dei grafi come modelli per analizzare e progettare soluzioni algoritmiche.

Decima settimana (15 e 20 dicembre 2017)

• Lucidi: programmazione dinamica: scheduling di intervalli pesati e zaino
• 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à.

21 dicembre 2017

10 e 11 gennaio 2018

• Scheda su implementazione di un dizionario con tabella di hash
• File di esempio: input_promessiSposi e output_promessiSposi.
• Svolgimento

17 gennaio 2018

• Gli esercizi di oggi vengono proposti in un formato particolare. Se tutto va bene, sarà il formato con cui saranno proposti durante la prova di laboratorio: simulazione.zip