ALGORITHMS AND COMPLEXITY

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.

Training 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.

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.

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.