ITA | ENG
B027514 - ANALYSIS OF ALGORITHMS AND DATA STRUCTURES
Main information
Teaching Language
Course Content
Suggested readings
Learning Objectives
Prerequisites
Teaching Methods
Further information
Type of Assessment
Course program
Sustainable Development Goals 2030
Academic Year 2022-23
Coorte 2022 - Second Cycle Degree in COMPUTER SCIENCE
Course year
First year - First Semester
Belonging Department
Statistics, IT and its applications "G. Parenti" (DISIA)
Course Type
Single education field course
Scientific Area
INF/01 - INFORMATICS
Credits
6
Teaching Hours
48
Teaching Term
12/09/2022 ⇒ 23/12/2022
Attendance required
No
Type of Evaluation
Final Grade
Course Content
show
Course program
show
Lectureship
Teaching Language
Italian
Course Content
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.
- R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996.
Learning Objectives
Knowledge - The course aims to give students knowledge about the main techniques used in the 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. 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.
Acquired skills - 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, by using a system of symbolic computation.
Skills acquired at the end of the course - Students will be able to evaluate in an exact way or through the use of symbolic tools the complexity of an algorithm or a data structure starting from the mathematical relation that describes the characteristic of interest.
Acquired skills - 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, by using a system of symbolic computation.
Skills acquired at the end of the course - Students will be able to evaluate in an exact way or through the use of symbolic tools the complexity of an algorithm or a data structure starting from the mathematical relation that describes the characteristic of interest.
Prerequisites
Basic concepts of algorithms and data structures
Teaching Methods
CFU: 6
Total number of hours of the course: 150
Number of hours for personal study and other individual learning activities: 102
Number of hours on the classroom activity: 48
Total number of hours of the course: 150
Number of hours for personal study and other individual learning activities: 102
Number of hours on the classroom activity: 48
Further information
Frequency of lessons and exercises: recommended
Tools to support teaching UniFi E-Learning: http://el.unifi.it
Receiving hours
Prof. D. Merlini
By appointment via email.
Dipartimento di Statistica, Informatica, Applicazioni
Viale Morgagni, 65
50134 - Firenze (FI)
Tel: 055 2751509
E-Mail: donatella.merlini@unifi.it
Tools to support teaching UniFi E-Learning: http://el.unifi.it
Receiving hours
Prof. D. Merlini
By appointment via email.
Dipartimento di Statistica, Informatica, Applicazioni
Viale Morgagni, 65
50134 - Firenze (FI)
Tel: 055 2751509
E-Mail: donatella.merlini@unifi.it
Type of Assessment
The exam consists in the following activities:
- Oral examination with exercises and questions on the techniques for the analysis of algorithms and data structures presented during the lessons.
- A project (to be carried out in small groups, maximum three people) consisting of a verification and/or simulation in the context of the analysis of algorithms and data structures using a symbolic calculation system.
The final grade will be calculated as the average of the oral exam and project grades.
- Oral examination with exercises and questions on the techniques for the analysis of algorithms and data structures presented during the lessons.
- A project (to be carried out in small groups, maximum three people) consisting of a verification and/or simulation in the context of the analysis of algorithms and data structures using a symbolic calculation system.
The final grade will be calculated as the average of the oral exam and project grades.
Course program
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.