The course will provide students with a description of the main mathematical techniques used in the analysis of algorithms, particularly those that use the concept of generating function, and focuses on the average case analysis, although the techniques described are the same used in the worst case analysis. The course is integrated with the presentation of a system of symbolic computation for deepening and testing the subjects discussed.
R. H. Greene and D. E. Knuth, “Mathematics for the Analysis of Algorithms”, Second Edition, Birkhauser, 1982.
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.
Learning Objectives
Knowledge acquired:
The student acquires knowledge of the major mathematical techniques used in the analysis of algorithms and data structures.
Competence acquired
The student acquires the competence to achieve precise and mathematically rigorous predictions about the performance of algorithms and data structures. The techniques learned are applicable mainly to the analysis of the average case but may also be used for the analysis the worst case. Also acquires knowledge of a system of symbolic computation that is used to deepen and verify the topics covered in the course.
Skills acquired (at the end of the course):
The student acquires the ability to manipulate mathematical tools to solve problems of analysis of algorithms and data structures and to check the theoretical results, or hypotheses, through computer simulation and appropriate statistical tests.
Prerequisites
Courses recommended: Programming, Algorithms and Data Structures, Mathematical Analysis I: Differential and Integral Calculus, Probability Calculus and Statistics.
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
Contact hours for: Lectures (hours): 48
Further information
Office hours:
By appointment via e-mail
Type of Assessment
Oral examination and project in Maple or, alternatively, study and simulation with Maple of scientific papers on the analysis of algorithms of the recent literature
Course program
Analysis of an algorithm and a data structure: average case and worst-case analysis. Special numbers. Generating functions. Extraction of the coefficient of a generating function. The method of Lagrange inversion. The symbolic method for the study of properties of data structures. Symbolic manipulation with the system Maple. Computer simulation for checking the results. Applications: classical searching and sorting algorithms, tree structures, regular and context-free languages, etc..