Module page
Informatica generale
| academic year: | 2013/2014 |
| instructor: | Giancarlo Bongiovanni |
| degree course: | Mathematics - DM 270/04 (triennale) |
| type of training activity: | di base |
| credits: | 9 (72 class hours) |
| scientific sector: | INF/01 Informatica |
| teaching language: | italiano |
| program: | I-Z |
| period: | II sem (03/03/2014 - 13/06/2014) |
Lecture meeting time and location
Presence: highly recommended
Module subject:
Description and design of efficient algorithms
- Introduction to the concepts of algorithms, data structures, efficiency, computational complexity.
- Asymptotic notation.
- Introduction to recursion.
- The sorting problem.
- Fundamental data structures (arrays, lists, queues, stacks, priority queues, trees).
- Dictionaries.
- Graphs.
C Language
- Rules of "good programming".
- Elementary notions of C language.
- Arrays.
- Functions.
- Recursion in C.
- Pointers.
- Lists and binary trees.
Suggested reading: T.H. Cormen, C.E. Leiserson, R.L. Rivest e C. Stein, "Introduzione agli Algoritmi", seconda edizione, Mc Graw Hill, 2005. (disponibile sia in vers. italiana che inglese)
Type of course: standard
Knowledge and understanding: At the end of this course the students will know fundamental methodologies for the design and analysis of iterative/recursive algorithms, fundamental data structures and sorting algorithms, and basic implementations of dictionaries. Furthermore, they will have basic notions on trees and graphs. Finally, they will have enough knowledge to write simple C functions and programs, iterative or recursive.
Skills and attributes: At the end of this course the students will be able to explain the behavior of the most important data structures, to analyze their running times, and to design new variants for specific problems, highlighting how the performance varies changing the data structure. They will be able to describe and to analyze the most important sorting algorithms, and to apply the same design techniques to different problems; will be able to compare asymptotically execution times of the studied algorithms; will be able to design and analyze recursive algorithms. Finally, they will be able to write simple C programs both iterative and recursive.
Personal study: the percentage of personal study required by this course is the 65% of the total.