Learning objectives

Elements and models of algorithmic graph theory, the practice of computational complexity to relate problems and as a methodological tool, methodologies and techniques in algorithm design.

Prerequisites and basic notions

Interest for the topic and basic notions of set theory.

Program

The specific topics to be covered in our class can be chosen together, according to your interests.
Just to have a rough idea, topics that I would certainly like to cover are:
1. shortest paths, negative cycles
2. maximum flows and minimum cuts
3. edge connectivity
4. vertex connectivity
5. matchings in bipartite graphs (also weighted)
6. matchings in non-bipartite graphs (also weighted)
7. good characterizations in general
8. polynomial algorithms and data structures
9. computational complexity and FPT algorithms
10. polyhedral combinatorics

Bibliography

Didactic methods

Didattica frontale in aula, con streaming verso l'esterno via Zoom e registrazione delle lezioni.
Il gruppo telegram di supporto al corso (t.me/+6PoS9O0d-MQxNjQ0) servirà anche come canale di upstream per lo streaming.

Learning assessment procedures

Some interactive problems with contextual feedback are made available on our rtal platform. Students can use them to verify their acquisition of some of the algorithmic and modeling skills introduced.
We will determine together whether some of these exercises should be considered mandatory for assessment purposes.

Assessment

Students will decide whether certifying an assessment is necessary for them or anyhow of interested to them. A possible procedure to obtain an assessment is described in the Exam Procedures section.

Criteria for the composition of the final grade

Through a reasonable and concerted monotonous function of the points collected on our rtal platform and any optional contributions that students wish to express.