.

Laboratorio di Algoritmi

Corso di Laurea Triennale in Informatica
Dipartimento di Matematica e Informatica

Orario delle lezioni

Le lezioni del corso di Laboratorio di Algoritmi si svolgeranno durante il primo semestre e si alterneranno alle lezioni del corso di Algoritmi tenute dal Prof. Cantone. Le lezioni si svolgeranno generalmente in base al seguente calendario

Martedì 08:00 – 10:00 Aula 22

Mercoledì 08:00 – 10:00 Aula 22

Giovedì 08:00 – 10:00 Aula 22

Sistema di Esercitazione

Il sistema di esercitazione è disponibile per gli studenti che intendono sosteenre l'esame di Laboratorio di Algoritmi.
Vai al Sistema



Modalità d'Esame

L'esame avrà di norma inizio alle ore 15:00 e si svolgerà presso il Laboratorio 125 (Aula Archimede). L'esame si svolgerà in due prove.
La prima prova, della durata di 45 minuti, consiste in un test a risposta multipla, che viene sostenuto attraverso il sistema di esercitazione e secondo le modalità specificate all'interno dello stesso.
Gli studenti che avranno ottenuto una valutazione superiore o uguale a 18 nella prima prova potranno accedere all seconda prova, della durata di circa 90 minuti. Tale prova di laboratorio consisterà nell'implementazione, in C++, di una o più tre le strutture dati studiate a lezione. La seconda prova verrà svolta attraverso l'utilizzo di un editor di testo e di un compilatore.

Articoli per la prova di Laboratorio

Calendario d'esami

Sessione Riservata ai Fuori Corso

14 dicembre 2017, ore 15:00, aula Archimede (Vai alla prova scritta)



Elenco degli articoli per la prova di Laboratorio

Alberi

Stout and Warren (1986)
Tree Rebalancing in Optimal Time and Space
Chang and Iyengar (1984)
Efficient Algorithms to Globally Balance a Binary Search Tree
Andersson (1991)
Binary Search Trees of Almost Optimal Height
Haeupler, Sen and Tarjan (1999)
Rank-Balanced Trees
Hanke, Ottomann and Soisalon-Soininen (1998)
Relaxed Balanced Red-Black Trees
Galperin and Rivest (1991)
Scapegoat Trees

Data Structures

Pugh (1991)
Skip Lists: A Probabilistic Alternative to Balanced Trees
Fredman and Tarjan (1987)
Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms
Vuillemin (1978)
A Data Structure for Manipulating Priority Queues

Algoritmi su Stringhe

Knuth, Morris and Pratt (1977)
Fast Pattern Matching in Strings
Boyer and Moore (1977)
A Fast String Searching Algorithm
Baeza-Yates and Gonnet (1992)
A New Approach to Text Searching
Charras, Lecroq and Pehoushek (1995)
A Very Fast String Matching Algorithm for Small Alphabets and Long Patterns
Cantone and Faro (2005)
Fast Search Algorithms: New Efficient Variants of the Boyer-Moore Pattern-Matching Algorithm
Claude, Navarro, Peltola, Salmela and Tarhio (2013)
String Matching with Alphabet Sampling
Wu and Manber (1994)
A Fast Algorithm for Multi Pattern Searching

Algoritmi su Grafi

Karger and Tarjan (1995)
A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees
Prim (1957)
Shortest Connection Networks And Some Generalizations
Allauzen, Crochemore and Raffinot (1999)
Factor Oracle: A New Structure for Pattern Matching

Programmazione Dinamica

Bergroth, Hakonen and Raita (2000)
A Survey of Longest Common Subsequence Algorithms
Needleman and Wunsch (1969)
A General Method Applicable to the Search for Similarities in the Amino Acid Sequence of Two Proteins
Ukkonen (1985)
Algorithms for Approximate String Matching

Programmazione Greedy

Vitter (1987)
Design and Analysis of Dynamic Huffman Codes
Bergroth, Hakonen and Raita (2000)
A Survey of Longest Common Subsequence Algorithms