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

Information concerning the students who enrolled in A.Y. 2018/19

Information on the course unit
Degree course Second cycle degree in
COMPUTER SCIENCE
SC1176, Degree course structure A.Y. 2014/15, A.Y. 2018/19
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/2018/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 DAVIDE BRESOLIN 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 25/02/2019
End of activities 14/06/2019

Examination board
Examination board not defined

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: 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 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, 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. 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. Tractable and intractable problems. NP-complete 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 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 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.]: McGraw-Hill, 2010. Cerca nel catalogo
  • Cormen, Thomas H., Introduction to algorithmsThomas H. Cormen ... [et al.]. Cambridge (Mass.): MIT Press, 2009. Cerca nel catalogo

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, ...)