Academic Year 2021/2022 - 2° Year - Elaborazione Dati e Applicazioni Curriculum and Sistemi e Applicazioni Curriculum

9 CFU - 1° Semester

**Algorithms***Knowledge and understanding*: students will acquire knowldege relative to the main methodologies for the design of efficient algorithms (incremental, recursion, dynamic programming, greedy algorithms), as well as the techniques for their computational analysis, both in the worst and in the average cases.

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

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

*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.**INTRODUCTION TO ALGORITHMS & LABORATORY***Knowledge and understanding*: the course is focused on the implementation of the main data structures analyzed in the theoretical module of Algorithms.*Applying knowledge and understanding*: the course is focused both on implementation skills and on the design of algorithmic solutions.*Making judgements*: students shall be able to judge the effectiveness of the provided implementation and of the adopted solution.*Learning skills*: students shall be able to adapt all solutions and algorithms for other contexts.

**Algorithms**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 programme planned and outlined in the syllabus.

**INTRODUCTION TO ALGORITHMS & LABORATORY**Practical laboratory.

*Should teaching be carried out in mixed mode or remotely, it may be necessary to introduce the required changements in line with the programme planned and outlined in the syllabus. Learning assessment may also be carried out on line, should the conditions require it.*

**Algorithms****General description**The course presents the main design methodoligies (incremental, recursion, dynamic programming, greedy algorithms) and the techniques for their complexity analysis, both in the worst and average cases.

**DETAILED SYLLABUS****Introduction**

Computational problems and algorithms: the sorting problem

Algorithms as technology

Incremental methodology: Insertion-Sort (correctness and complexity)

Divide-and-Conquer methodology: Merge-Sort (complexity)

Asymptotic notations and relationships among them

Standard notations and common functions.**Recurrences**

The substitution method

The iterative method and the recursion tree

The master theorem**Sorting and order statistics**

Heaps and their construction

Priority queues

Quicksort and its randomized version

Analysis of Quicksort in the worst- and average case

Lower bounds for sorting

Sorting in linear time: Counting-Sort, Radix-Sort, Bucket-Sort

Medians and order statistics**Hashing**

Hash table

Hash functions (division method, multiplication method, universal hashing)

Open addressing**Red-black trees**

Rotations, insertions, deletions

Complexity analysis**Elements of dynamic programming**

Optimal substructure, overlapping subproblems, reconstructing an optimal solution

Some case studies: assembly line scheduling, matrix-chain multiplication, longest common subsequence, editing distance**Elements of the greedy strategy**

Greedy-choice property, optimal substructure

Some case studies: the activity-selection problem, Huffman codes**Elementary graph algorithms**

Single-source shortest paths: the Bellman-Ford algorithm, single-source shortest paths in oriented acyclic graphs, Dijkstra's algorithm

All-pairs shortest paths: the Floyd-Warshall algorithm, transitive closure of oriented graphs**INTRODUCTION TO ALGORITHMS & LABORATORY**The aim of the course is to provide students with the tools for implementing algorithms and the data structures discussed in the Algorithms course. Classes will be held by leveraging an object-oriented programming language. Specifically, the C ++ programming language will be adopted as the main tool to illustrate the implementations of data structures and algorithms.

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

**INTRODUCTION TO ALGORITHMS & LABORATORY**T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to algorithms (Third Edition), The MIT Press, Cambridge - Massachusetts, 2009