
Course unit
ADVANCED ALGORITHMS
SCP8084820, A.A. 2018/19
Information concerning the students who enrolled in A.Y. 2018/19
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 
Examination board
Board 
From 
To 
Members of the board 
1 a.a. 2018/2019 
01/10/2018 
28/02/2020 
BRESOLIN
DAVIDE
(Presidente)
BALDAN
PAOLO
(Membro Effettivo)
AIOLLI
FABIO
(Supplente)
FILE'
GILBERTO
(Supplente)
TOLOMEI
GABRIELE
(Supplente)

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:

Algorithmic thinking is the process that allows computer scientists to analyze and solve very complex computational problems at a level of abstraction that is independent from a particular language or computer system. 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, to be developed following the five steps of Algorithmic Thinking. In this case the project must be carried out alone, not in a group.
The final grade is the arithmetic mean of the votes of the two parts. 
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:

Introduction to Algorithmic Thinking. Graphs: 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. Tractable and intractable problems. NPcomplete problems and approximation algorithms. The Traveling Salesman Problem: exact solutions and approximate heuristics. Divide and conquer algorithms: clustering algorithms. Dynamic programming: similarity and alignment of sequences. 
Planned learning activities and teaching methods:

The course is divided into thematic blocks, each of which deals with a real problem and solves it by following the approach of Algorithmic Thinking. 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 teacher. 
Textbooks (and optional supplementary readings) 

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.

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

Innovative teaching methods: Teaching and learning strategies
 Laboratory
 Problem based learning
 Case study
 Working in group
 Problem solving
 Flipped classroom
 Loading of files and pages (web pages, Moodle, ...)
Innovative teaching methods: Software or applications used
 Moodle (files, quizzes, workshops, ...)

