Algorithms and Complexity

Applying knowledge and understanding:  Students will develop the ability to solve medium-difficulty problems that require the design and analysis of advanced algorithmic solutions.

Making judgments: Students will be able to evaluate the quality of algorithmic solutions in terms of efficiency and potential for reuse.

Communication skills: Students will acquire the communication and expressive skills necessary to present and discuss algorithmic problems, including with non-expert interlocutors.

Learning skills: Students will be able to apply the knowledge acquired in new contexts and to further advance their expertise by consulting specialized sources in the algorithmic field.

Classroom-taught lessons

Should teaching be offered in mixed mode or remotely, it may be necessary to introduce changes with respect to previous statements, in line with the organization and contents set out in the syllabus.

Information for students with disabilities and / or SLD

To guarantee equal opportunities and in compliance with the laws in force, interested students can ask for a personal interview in order to plan any compensatory and / or compensatory measures, based on the didactic objectives and specific needs. It is also possible to contact the referent teacher CInAP (Center for Active and Participated Integration - Services for Disabilities and / or SLD) of our Department, prof. Filippo Stanco.

Elementary data structures and algorithms for their manipulation (lists, queues, stacks, trees, etc.)

Elements of discrete mathematics, of programming I e II, and of mathematical analysis.

Elementary algorithms and programming and dynamic and greedy programming methodologies.

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

1)        T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms (3rd Edition), The MIT Press, Cambridge (MA), 2009.

• Available also in Italian translation:

  Introduzione agli algoritmi e strutture dati (3ª ed.), McGraw-Hill Italia, 2010.

Additional reference

2)       M.A. Weiss, Data Structures and Algorithmic Analysis in C (2nd Edition), Addison-Wesley, 1996.

These examinations may also take place online, should circumstances require it. The optional oral examination may be held on the same day as the written test or within a few days thereafter.

The oral test has an integrative function with respect to the written one and contributes inseparably to the determination of the final grade. It does not represent an opportunity to increase the score, but rather a necessary completion for the overall assessment of the student’s preparation.

The following criteria are generally applied for the assignment of the final grade:

Not approved: the student has not yet acquired the basic concepts and is unable to adequately solve the exercises.

18–23: the student demonstrates an essential knowledge of the basic concepts; exposition and ability to connect topics are limited, but the student manages to solve simple exercises.

24–27: the student demonstrates a good knowledge of the course contents, presents them clearly and connects them appropriately; exercises are solved with few errors.

28–30 with honors: the student has acquired a complete knowledge of the contents, presents them with clarity and critical insight, and solves the exercises accurately and without errors.

Students with disabilities and/or specific learning disorders (DSA) must contact the instructor, the CInAP representative of the DMI (Prof. Daniele), and CInAP sufficiently in advance of the exam date to notify their intention to take the exam with the appropriate compensatory measures.