
Course unit
ADVANCED ALGORITHMS
SCP8084820, A.A. 2019/20
Information concerning the students who enrolled in A.Y. 2019/20
ECTS: details
Type 
ScientificDisciplinary Sector 
Credits allocated 
Core courses 
INF/01 
Computer Science 
6.0 
Course unit organization
Period 
Second semester 
Year 
1st Year 
Teaching method 
frontal 
Type of hours 
Credits 
Teaching hours 
Hours of Individual study 
Shifts 
Lecture 
6.0 
48 
102.0 
No turn 
Prerequisites:

The course requires familiarity with some basic algorithmic concepts, such as asymptotic complexity, searching and sorting algorithms, and basic data structures such as trees, lists, maps, and arrays.
There are no preparatory courses. 
Target skills and knowledge:

The course aims to teach students to think "in an algorithmic way", providing the following knowledge and skills:
1. Being able to understand a problem, what data are available and how the solution should be provided.
2. Being able to formulate a problem in terms of input and output that can be processed by a computer.
3. Being able to define an algorithm and to analyze its correctness and computational complexity properties.
4. Being able to implement an algorithm in a concrete programming language.
5. Being able to execute the implementation on a mediumsized dataset and to understand and analyze the results. 
Examination methods:

The exam is divided into a theoretical part and a practical part.
The theoretical part consists of a written test held during the regular exam session.
The practical part can be done in two different ways:
 DURING THE COURSE: a group of maximum three students implements all the algorithms seen in the laboratories and submits the code and the obtained results.
 AFTER THE COURSE: a single personal project. In this case the project must be carried out alone, not in a group. 
Assessment criteria:

The evaluation criteria are the following:
1. Completeness of the acquired knowledge;
2. Property of the technical terminology used;
3. Ability to formalize a problem in algorithmic terms
3. Ability to analyze the correctness and computational complexity of an algorithm
4. Ability to implement an algorithm consistently with the theory
5. Ability to use an algorithm to solve a concrete problem 
Course unit contents:

1) Algorithms on graphs:
Graph basics and representation. Randomized generation of graphs. Breadthfirst and depthfirst visit of a graph. Connected Components. Greedy algorithms. Weighted graphs: shortest paths and minimum spanning trees. Data structures for disjoint sets.
2) Approximation algorithms for intractable problems:
Tractable and intractable problems. NPcomplete problems and approximation algorithms. Approximation for the vertex cover problem. The Traveling Salesman Problem: exact solutions and approximate heuristics.
3 Randomized algorithms:
Main techniques and applications: Markov inequalities, Chernoff bounds, analysis of Quicksort, randomized algorithms for the minimum cut problem 
Planned learning activities and teaching methods:

The course is divided into thematic blocks. Each block begins with a series of classroom lectures during which the course contents are dealt with. After the frontal activity, the block continues with one or more laboratory lessons where the students, divided into groups, will implement and test the solution of the real problem on a mediumsized dataset, and ends with a phase of comparison and discussion of the various proposed solutions. 
Additional notes about suggested reading:

The course has a dedicated section on the Moodle of the Department of Mathematics. The Moodle will collect the handouts of the course, the detailed specifications of the individual laboratories, the exercises and their solutions. It will also be used for communications and updates by the teachers. 
Textbooks (and optional supplementary readings) 

Cormen, Thomas H., Introduction to algorithmsThomas H. Cormen ... [et al.]. Cambridge (Mass.): MIT Press, 2009.

Cormen, Thomas H.; Colussi, Livio, Introduzione agli algoritmi e strutture datiThomas Cormen ... [et al.]edizione italiana a cura di Livio Colussi. Milano [etc.]: McGrawHill, 2010.


