Informatica 3

News

The Informatica 3 course is held in three parallel sections (lecturers: G. Agosta, A. Campi, M. Matera).

Course contents and programs are identical across the sections, and the written exam is held on the same exam tests.

The course is roughly divided in two parts. In the first, we cover programming language design, while in the second we study the design of efficient algorithms and data structures.

The course is composed of 30 lecture hours and 20 hours of exercises. Gerardo Pelosi is the lecturer for the latter part.

1. Programming language: generalities and classification; history of programming languages
2. Syntax and semantics
3. Data structures
4. Control structures
5. Modularization
6. Object-oriented languages
7. Interpreted languages

1. Computational Complexity
2. “Big Theta” and related notations
3. Abstract data types
4. Fundamentals of data structures and algorithms
5. Search and sort algorithms
6. Tree and their implementation
7. Tree visit and management algorithms
8. B-trees
9. Graphs, representation and management
10. Stacks, queues, and hash tables
11. Applications (seminars on cryptography and other applications)

We adopt the following two books:

• For the programming language design part: Ghezzi C., Jazayeri M.: Programming language concepts, 4th edition, John Wiley & Sons, 2002.
• For the algorithm and data structures part: C.A.Shaffer: A practical Introduction to data structures and algorithm analysis.

The latter can be replaced by T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms and Data Structures 2/ed.

This second book is more of a reference text, and covers parts of algorithmics not explored in the course. It more closely fits the style of my version of the course, but has a more theoretical (and formal) approach to the topic.

You can also refer to the slides adopted in the other sections, as well as to the material associated to Shaffer's book (or the same type of material for the Cormen et al. book) for the second part of the course.

Finally, the classic book by David Harel, “Algorithmics: The Spirit of Computing”, gives a gentler introduction to the topics of the course.

During lectures, algorithms will be presented in the Python programming language (the exercises will be run mostly in Java, to provide a more traditional implementation of the algorithms presented in the lectures).

You can (actually, you need, since Python is used in the exam as well) download and install the Python interpreter from the above link, both for Linux and for Windows. If you use Linux, you already have a Python interpreter installed in your system.

To learn Python, you can rely on the following (freely available) books:

• Mark Pilgrim, Dive Into Python: a very complete survey of the language;
• Allen B. Downey, Jeffrey Elkner and Chris Meyers How to Think Like a Computer Scientist - Learning with Python: an introduction to programming, using Python; only useful if you have doubts on the basics of programming;
• Bruce Eckel, Thinking in Python: not an introductory book; it's the Python version of the classic Thinking in Java.

Not yet updated, refer to the Italian version for the scheduled dates

Here is the course calendar and notes. The notes for future lectures can change, since they come from the 2007/2008 edition.