# ALGORITHMS AND COMPLEXITY

**Academic Year 2019/2020**- 1° Year

**Teaching Staff:**

**Domenico CANTONE**

**Credit Value:**9

**Scientific field:**INF/01 - Informatics

**Taught classes:**36 hours

**Exercise:**36 hours

**Term / Semester:**1°

## Learning Objectives

*Knowledge and understanding*: students will acquire knowldege relative to various data structures and relative management operations, as well as knowledge reltaive to the main fundamental algorithms.

*Applying knowledge and understanding*: students will acquire the ability to solve problems of medium difficulty, requiring the design and analysis of advanced algorithmic solutions.

*Making judgements*: students will be able to evaluate the quality of an algorithmic solution in terms of efficiency and reuse capacity.

*Communication skills*: students will acquire the necessary communication skills and expressive ability in communicate problems regarding the algorithmic studies, also to non-expert interlocutors.

*Learning skills*: students will have the ability to adapt the knowledge acquired also in new contexts and to advance his/her knowledge through the consultation of specialist sources in the algorithmic field.

## Course Structure

Classroom-taught lessons

## Detailed Course Content

**General description**

Various advanced data structures (such as B-trees, splay trees, binomial heaps, and Fibonacci heaps) and relative operations will be presented and analysed, by means also of the technique of amortized analysis. We shall also study, design, and analyse graph algorithms for the efficient solution of various optimizations problems.

**SYLLABUS**

**Amortized analysis**

Stack with multipop and binary counter.

Aggregation method, accounting method, and potential method.

Dynamic tables with insertions and deletions.

**Advanced data structures**

B-trees: applications, height, search, insertions and deletions

Splay trees: search, insertions and deletions, amortized analysis of m operations with n insertions; top-down splay trees

Data structures for disjoint sets: union by rank, paths compression, algorithm Union-Find, Knuth notation, Ackermann function and its inverse

Binomial heaps: binomial trees, operations of insertion, find minimum and delete minimum, decrease key, key deletion, union

Fibonacci heaps: unordered binomial trees, operations of insertion, find minimum and delete minimum, decrease key, key deletion, union, amortized analysis

**Shortest paths from a single source in digraphs**

Shortest paths graph, minimum paths tree, generic algorithm for shortest paths from a single source, Bellman-Ford algorithm, Dijkstra's algorithm, linear algorithm on acyclic graphs.

**All-pairs shortest-paths in digraphs**

Floyd-Warshall algorithm, transitive closure of a digraph, Johnson's algorithm for sparse digraphs

**Minimum spanning trees**

Red and blue rules, color invariant, Boruvka algorithm, Kruskal algorithm, Prim algorithm, clustering of maximum spacing

**Flow networks and applications**

Real and net flow in a flow network, properties of net flows, flow networks with multiple sources and sinks, notation of implicit summation, Ford-Fulkerson methods, residual capacities and networks, augmenting paths, cuts in flow networks, Max-flow/min-cut Theorem, analsysis of the Ford-Fulkerson method, maximum matching in bipartite graphs, Edmonds-Karp algorithm and it complexity analysis, edge-connectivity.

## Textbook Information

1) T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to algorithms (Third Edition), The MIT Press, Cambridge - Massachusetts, 2009.

2) M.A. Weiss. Data structures and algorithmic analysis in C (Second Edition), Addison-Wesley, 1996.