69443 - ALGORITHMS AND DATA STRUCTURES FOR COMPUTATIONAL BIOLOGY

Conoscenze e abilità da conseguire

At the end of the course, the student has the basic Knoledge in design and analysis of correct and efficient algorithms and data structures. In particular, the student has basic knowledge on algorithms and data structures. The student will be able to: design correct and efficient algorithm for common computational tasks; analyze existing algorithms and data structures; design and analyze new algorithms and data structures.

Contenuti

Essendo un corso di studio internazionale, il corso di Algorithms and Data Structures for Computational Biology viene tenuto completamente in lingua inglese.  
Introduction to algorithms and basic data structures: definitions, algorithms, simple data structures. Lists, arrays, simple operations, examples, implementation. Complex data structures, computation efficiency and relation between computation efficiency and data structures. Stacks and queues (definition, examples, implementation). Trees, visit algorithms of a tree and tree operations. Sets, dictionaries and hash tables, their operations and implementation concepts. Graphs, visit algorithms for graphs, operations and implementation concepts. Exercices and tests ( graphs and trees, priority queues and heaps). Binary trees, search trees, balanced binary trees, B-trees, AVL trees.
Algorithms. Decision tree. Analysis of computational complexity of algorithms. O(), Omega() and Theta() functions. Iterative and recursive programming methodologies. Divide and conquer. Recursion. Greedy techniques (knapsack problem, radix sorting problem, Huffman codes). Binary search. Sorting algorithms. Sequence pattern analysis and matching. Algorithm optimization. Complexity analysis of algorithms. Exercises and tests.

Testi/Bibliografia

It is fundamental to use the electronic slides and material provided during the classes, including live exercises. Electronic slides will be provided (also made available on the teachers' website).
Suggested readings (not to be necessarily purchased).    

 Books more specific on computational biology topics:
- Carlos Setubal, Joao Meidanis, Introduction to computational molecular biology, Cengage Learning eds.; 1997 
- C. Gibas, P. Jambeck, Developing Bioinformatics Computer Skills, O'Reilly media, 2001 
 
Books more general on computer algorithms and data structures topics:

- Alfred V. Aho, Jeffrey D. Ullman, John E. Hopcroft. Data Structures and Algorithms. Addison Wesley, 1983.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. McGraw-Hill, 2001.
- Donald E. Knuth. The Art of Computer Programming, Volumes 1-3. Addison-Wesley Professional, 1998.
- S.B. Kishor Data Structures, Edition 3. Das Ganu Prakashan, Nagpur, 2008.

Metodi didattici

Il corso si svolge al secondo semestre e rappresenta un modulo unico di 10 cfu. Il modulo è strutturato in lezioni frontali in aula, tutte in inglese, in cui vengono presentati innanzitutto gli aspetti teorici degli argomenti trattati. In particolare, dopo aver introdotto le nozioni di base, relative alla progettazione di strutture dati e della loro relazione con il costo in termini di spazio e con l'efficienza di esecuzione di algoritmi al calcolatore, vengono enunciati, e in alcuni casi dimostrati, i principali risultati nell'ambito della progettazione di algoritmi e della complessità computazionale nell'esecuzione degli algoritmi su architetture di calcolo non parallele. Vengono infine introdotte le tecniche di programmazione iterative, ricorsive, divide et impera, greedy e di programmazione dinamica e vengono illustrati i loro utilizzi in funzione diella riduzione della complessità computazionale e spaziale sul calcolatore. Successivamente ampio spazio viene dedicato alle applicazioni delle nozioni e delle tecniche presentate, e alla risoluzione di esercizi nel contesto delle metodologie di analisi della bioinformatica e biologia molecolare. Oltre alle lezioni frontali in aula, vengono svolte esercitazioni in aula (semplici), e vengono fornite esercitazioni (homework) sui temi analizzati.

Modalità di verifica e valutazione dell'apprendimento

La verifica dell'apprendimento avviene attraverso una prova scritta finale di 3 ore e una contestuale prova orale di circa 30 minuti. Per la prova scritta viene ammesso l'uso di: libri, appunti, ma non l'uso di calcolatrici e supporti informatici, e nemmeno l'uso di strumenti che consentano accesso a Internet. La prova scritta è strutturata in più parti: la prima riguarda la progettazione di un algoritmo e della relative strutture dati orientate alla massima efficienza computazionale, secondo requisiti di prestazioni e di spazio di memoria predefiniti, facendo ricorso alle conoscenze sviluppate nel corso. Viene richiesto di sviluppare le strutture dati e lo pseudo codice dell'algoritmo e commentare le scelte effettuate definendo la complessità spaziale e computazionale ottenuta. Il primo esercizio richiede circa 90 minuti e vale circa metà della valutazione della prova scritta. I dettagli su durata e peso della valutazione di ogni esercizio sono indicati nel testo di volta in volta. La seconda parte della prova scritta riguarda una serie di esercizi mirati a verificare la conoscenza e la capacità di interpretare e applicare i concetti studiati. Tali esercizi sono spesso simili e derivati dalle esercitazioni svolte durante il corso. Il tempo a disposizione per la seconda parte è di 90 minuti e il peso della seconda parte è circa la metà della valutazione totale. 
La calendarizzazione delle prove scritte avviene entro la fine del corso in aula. Sono previsti appelli della prova scritta nei mesi di Giugno, Luglio, Settembre, ottobre, Dicembre e Febbraio. E' necessario effettuare l'iscrizione alle prove sulla piattaforma almaesami entro le scadenze fissate di volta in volta.
Previo superamento della prova scritta, ottenendo una valutazione di almeno 18/30, si procede alla convocazione per la successiva prova orale, da effettuarsi entro la fine della sessione di esame, nei giorni immediatamente successivi alla prova scritta. Il non superamento della prova orale comporta la necessità di ripetere la prova scritta contestuale in un appello successivo. In caso di superamento della prova scritta e della prova orale, viene effettuata la proposta di voto finale del corso, calcolata come media pesata delle prove scritte e orale. Il peso delle prove scritte e orale è di 80% e 30% rispettivamente (totale 110%). La somma dei valori (voto scritto * 0,80) + (voto orale * 0,30) fornisce il valore della proposta di voto. In caso di superamento del valore di 30/30 è prevista l'attribuzione della lode. Per superare l'esame dovranno risultare sufficienti entrambe le prove scritta e orale.
 E' possibile per i candidati presentare un progetto facoltativo, inerente la progettazione, analisi e realizzazione prototipale di soluzioni algoritmiche per problemi di bioinformatica, basandosi sulle tecniche allo stato dell'arte. La valutazione del progetto facoltativo, da 0 a 3 punti, si somma alla valutazione finale della prova scritta e orale.

Strumenti a supporto della didattica

Proiettore e slide elettroniche.
Personal computer.
Lavagna.

Link ad altre eventuali informazioni

http://www.cs.unibo.it/~bononi/

Orario di ricevimento

Consulta il sito web di Luciano Bononi