First cycle
degree courses
Second cycle
degree courses
Single cycle
degree courses
School of Science
COMPUTER SCIENCE
Course unit
ADVANCED ALGORITHMS
SCP8084820, A.A. 2019/20

Information concerning the students who enrolled in A.Y. 2019/20

Information on the course unit
Degree course Second cycle degree in
COMPUTER SCIENCE
SC1176, Degree course structure A.Y. 2014/15, A.Y. 2019/20
N0
bring this page
with you
Number of ECTS credits allocated 6.0
Type of assessment Mark
Course unit English denomination ADVANCED ALGORITHMS
Website of the academic structure http://informatica.scienze.unipd.it/2019/laurea_magistrale
Department of reference Department of Mathematics
Mandatory attendance No
Language of instruction Italian
Branch PADOVA
Single Course unit The Course unit can be attended under the option Single Course unit attendance
Optional Course unit The Course unit can be chosen as Optional Course unit

Lecturers
Teacher in charge MICHELE SCQUIZZATO INF/01

ECTS: details
Type Scientific-Disciplinary 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

Calendar
Start of activities 02/03/2020
End of activities 12/06/2020
Show course schedule 2019/20 Reg.2014 course timetable

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)

Syllabus
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 medium-sized 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. Breadth-first and depth-first 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. NP-complete 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 medium-sized 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. Cerca nel catalogo
  • Cormen, Thomas H.; Colussi, Livio, Introduzione agli algoritmi e strutture datiThomas Cormen ... [et al.]edizione italiana a cura di Livio Colussi. Milano [etc.]: McGraw-Hill, 2010. Cerca nel catalogo