ITA | ENG
B013003 - ALGORITHMS DESIGN AND ANALYSIS
Main information
Teaching Language
Course Content
Suggested readings
Learning Objectives
Prerequisites
Teaching Methods
Further information
Type of Assessment
Course program
Academic Year 2016-17
Coorte 2016 - Second Cycle Degree in MATHEMATICS
Course year
First year - First Semester
Belonging Department
Mathematics and Computer Science "Ulisse Dini" (DIMAI)
Course Type
Single education field course
Scientific Area
INF/01 - INFORMATICS
Credits
9
Teaching Hours
72
Teaching Term
19/09/2016 ⇒ 23/12/2016
Attendance required
No
Type of Evaluation
Final Grade
Course Content
show
Course program
show
Lectureship
Teaching Language
Italian
Course Content
Recursive algorithms and recurrence relations.The "Divide et Conquer" approach. "Greedy" algorithms. Dynamic Programming. String matching. NP-Complete problems. Approximation Algorithms. Unsolvable problems. Elements of computational geometry
Suggested readings (Search our library's catalogue)
S. Baase, Computer Algorithms Introduction to Design and Analysis, 2nd Edition, Addison Wesley, 1988.
A. Bertossi, Algoritmi e strutture di dati, Utet Libreria, 2000.
A. Bertossi, A. Montresor, Algoritmi e strutture di dati, Citt a’ Studi Edizioni, 2010.
T. H. Cormen, C.E. Leiserson, R. L. Rivest, Introduzione agli algoritmi, Jackson Libri, 2003.
P. Crescenzi, G. Gambosi, R. Grossi, Strutture di dati e algoritmi - Progettazione, analisi e visualizzazione, Pearson Addison Wesley, 2006.
C. Demetrescu, I. Finocchi, G. F. Italiano, Algoritmi e strutture dati, Seconda edizione, McGraw-Hill, 2008.
J.E. Hopcroft, R. Motwani, J.D. Ullman, Automi, linguaggi e calcolabilit a’, Addison-Wesly, 2003.
M. Sisper, Introduzione alla teoria della computazione, Maggioli Editore, 2016. Collana Apogeo education.
A. Bertossi, Algoritmi e strutture di dati, Utet Libreria, 2000.
A. Bertossi, A. Montresor, Algoritmi e strutture di dati, Citt a’ Studi Edizioni, 2010.
T. H. Cormen, C.E. Leiserson, R. L. Rivest, Introduzione agli algoritmi, Jackson Libri, 2003.
P. Crescenzi, G. Gambosi, R. Grossi, Strutture di dati e algoritmi - Progettazione, analisi e visualizzazione, Pearson Addison Wesley, 2006.
C. Demetrescu, I. Finocchi, G. F. Italiano, Algoritmi e strutture dati, Seconda edizione, McGraw-Hill, 2008.
J.E. Hopcroft, R. Motwani, J.D. Ullman, Automi, linguaggi e calcolabilit a’, Addison-Wesly, 2003.
M. Sisper, Introduzione alla teoria della computazione, Maggioli Editore, 2016. Collana Apogeo education.
Learning Objectives
Knowledge acquired:
Knowledge of the most important algorithm techniques and the basic principles of computational complexity.
Competence acquired:
Know how to develop new algorithms and evaluate their complexity.
Skills acquired (at the end of the course):
Ability to use their own knowledge with awareness in order to find resolutive strategies of real problems.
Knowledge of the most important algorithm techniques and the basic principles of computational complexity.
Competence acquired:
Know how to develop new algorithms and evaluate their complexity.
Skills acquired (at the end of the course):
Ability to use their own knowledge with awareness in order to find resolutive strategies of real problems.
Prerequisites
Courses recommended: Computer science
Teaching Methods
Total hours of the course (including the time spent in attending lectures, seminars, private study, examinations, etc...): 150
Hours reserved to private study and other indivual formative activities: 102
Hours for lectures: 72
Hours for laboratory: 0
Hours for laboratory-field/practice: 0
Seminars (hours): 0
Stages (hours): 0
Intermediate examinations (hours): 0
Hours reserved to private study and other indivual formative activities: 102
Hours for lectures: 72
Hours for laboratory: 0
Hours for laboratory-field/practice: 0
Seminars (hours): 0
Stages (hours): 0
Intermediate examinations (hours): 0
Further information
Attendance of lectures, practice and lab:
Not mandatory
Office hours:
Tuesday 9:30-10:30
Thursday 11:00-13:00
Contact:
Viale Morgagni, 65 - 50134 Firenze
Phone: 055 4237446
Fax: 055 4796363 - 4237436
E-mail: elisabetta.grazzini@unifi.it
Web: http://www.unifi.it/dpsinf/CMpro-v-p-75.html
Not mandatory
Office hours:
Tuesday 9:30-10:30
Thursday 11:00-13:00
Contact:
Viale Morgagni, 65 - 50134 Firenze
Phone: 055 4237446
Fax: 055 4796363 - 4237436
E-mail: elisabetta.grazzini@unifi.it
Web: http://www.unifi.it/dpsinf/CMpro-v-p-75.html
Type of Assessment
The final exam is designed to ensure the acquisition of knowledge and skills by conducting an oral test.
The oral test is a conversation with the teacher in order to verify the ability in problem-solving and theoretical knowledges.
The oral test is a conversation with the teacher in order to verify the ability in problem-solving and theoretical knowledges.
Course program
Recursive algorithms and recurrence relations.
The “Divide et Conquer” approach: product of integers; matrix multiplication and the Strassen algorithm; the fast Fourier Transform and the polynomial product; the problem of the nearest points.
“Greedy” algorithms: activity planning; Huffman codes; points covered withs intervals.
Dynamic Programming: multiplication of n matrices; optimal triangulations; a shortest-path algorithm; the change problem; partition of integers; the Knapsack problem.
String matching: the distance of two strings; the problem of the longest common subsequence; finite autotomaton; the Knuth-Morris-Pratt algorithm; the Rabin-Karp algorithm.
NP-Complete problems. Approximation Algorithms. Unsolvable problems. Elements of computational geometry.
The “Divide et Conquer” approach: product of integers; matrix multiplication and the Strassen algorithm; the fast Fourier Transform and the polynomial product; the problem of the nearest points.
“Greedy” algorithms: activity planning; Huffman codes; points covered withs intervals.
Dynamic Programming: multiplication of n matrices; optimal triangulations; a shortest-path algorithm; the change problem; partition of integers; the Knapsack problem.
String matching: the distance of two strings; the problem of the longest common subsequence; finite autotomaton; the Knuth-Morris-Pratt algorithm; the Rabin-Karp algorithm.
NP-Complete problems. Approximation Algorithms. Unsolvable problems. Elements of computational geometry.