Table of Contents

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.

Course program: Programming Language Design

  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

Course program: Algorithms and Data Structures

  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)

Courseware

We adopt the following two books:

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.

Python

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:

Calendar

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.

Topic Date Type
Syntax and semantics 29/9 L
Function calls 6/10 L
Python 8/10 L
Operational Semantics 15/10 E
Concurrency and Threading 20/10 L
Threading & Mutual Exclusion 22/10 L
Lists, stacks and queues 27/10 L
Iterators, generators and coroutines 29/10 L
Computational complexity 5/11 L
Parallelism and Threads 10/11 E
Seminar: parallel programming on NVIDIA GPUs 10/11 S
O, Ω e Θ notations 12/11 L
Induction and recurrences 24/11 L
Sorting algorithms 26/11 L
Sorting algorithms 1/12 E
Binary Trees, part 1 1/12 L
Binary Trees, part 2; Binary Search Trees 3/12 L
Trees 10/12 E
B-Tree, Heaps 15/12 L
B-Tree 7/01 E
Graphs 12/01 L
Graphs 14/01 E
Hash & Huffman code 19/01 L
Seminar: Cryptographic algorithms 19/01 S
Hash e Exercises on Complexity and Induction 21/01 E
Pre-exam exercises, part 1 26/01 E
Pre-exam exercises, part 2 28/01 E