ITA | ENG
B018968 - DESIGN AND ANALYSIS OF ALGORITHMS
Main information
Course Content
Suggested readings
Learning Objectives
Further information
Type of Assessment
Course program
Academic Year 2012-13
Coorte 2012 - Second Cycle Degree in COMPUTER SCIENCE
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
76
Teaching Term
24/09/2012 ⇒ 21/12/2012
Attendance required
No
Type of Evaluation
Final Grade
Course Content
show
Course program
show
Lectureship
Course Content
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.
Suggested readings (Search our library's catalogue)
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
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.
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.
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
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.
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.