Greedy algorithms. Dynamic programming. Divide and conquer. Graph algorithms. Search within texts. Probabilistic algorithms. Analysis of algorithms and computational complexity. Special numbers. Recurrence relations. Generating functions. Lagrange inversion. Exact and approximate methods. The symbolic method. Regular expressions and context-free grammars: the Chomsky-Schutzenberger methodology. Simulating algorithms and data structures and statistical tests.
D. E. Knuth, The art of computer programming, Vol. 1-3, Addison-Wesley, 1973.
R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996.
J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005
Learning Objectives
The course aims to provide students with a complete description of the main techniques used in the design and analysis of algorithms and data structures. The course focuses mainly on the analysis of the average case although the mathematical techniques described are the same used also in the analysis of the worst case. In particular, in the course are treated classical mathematical topics, such as discrete mathematics and combinatorics, as well as topics of computer science, including algorithms and data structures. The course is integrated with the presentation of a
symbolic manipulation system that is used as a tool for the study and testing of the topics covered. Once successfully passed the examination,
the student will have acquired the ability to manipulate mathematical tools to solve problems of analysis of algorithms and data structures as well as to verify the theoretical results, or hypotheses, by
computer simulation and the appropriate statistical tests.
Prerequisites
None
Teaching Methods
CFU: 9
Total number of hours of the course: 225
Number of hours for personal study and other individual learning activities: 149
Number of hours on the classroom activity: 64
Number of hours related to laboratory activities (laboratory classes): 12
Further information
Frequency of lessons and exercises: Recommended
Tools to support teaching UniFi E-Learning: http://el.unifi.it
Receiving hours
Prof. M.C. Verri
Previo appuntamento via e-mail.
Dipartimento di Statistica, Informatica, Applicazioni
Viale Morgagni, 65
50134 - Firenze (FI)
Tel: 055 4237439 Fax: 055 4237436
E-Mail: mariacecilia.verri@unifi.it
Prof. D. Merlini
Previo appuntamento via e-mail.
Dipartimento di Statistica, Informatica, Applicazioni
Viale Morgagni, 65
50134 - Firenze (FI)
Tel: 055 4237440 Fax: 055 4237436
E-Mail: donatella.merlini@unifi.it
Type of Assessment
Oral examination and project
Course program
Exact greedy algorithms: the problem of scheduling, the Huffman method, the problem of shortest paths. Approximate greedy algorithms: distribution of the workload, the problem of
selection of the centers. Divide and conquer: the fundamental theorem of recurrence, the problem of the pair of closest points, counting inversions. Dynamic Programming: scheduling
intervals weighed, subvectors of maximum value. Graph algorithms. Search within texts. Probabilistic algorithms.
Analysis of algorithms and computational complexity. Average case and worst case. Special numbers. Recurrence relations: methods of resolution. Divide and conquer recurrences. Generating functions and
extraction of their coefficients. The Lagrange inversion. Exact and approximate methods. The symbolic method. Regular expressions and context-free grammars: the
Chomsky-Schutzenberger methodology. Examples of analysis of classical algorithms, tree structures, permutations ad words. Simulating algorithms and data structures and statistical tests.