Scheda programma d'esame
ALGORITMICA E LABORATORIO
PAOLO FERRAGINA
Anno accademico2017/18
CdSINFORMATICA
Codice008AA
CFU12
PeriodoSecondo semestre
LinguaItaliano

ModuliSettoreTipoOreDocente/i
ALGORITMICA E LABORATORIOINF/01LEZIONI96
ANNA BERNASCONI unimap
PAOLO FERRAGINA unimap
ALINA SIRBU unimap
Learning outcomes
Knowledge

The goal is to introduce (basic) algorithms and data structures to solve problems on sequences, lists, trees and graphs, in efficient time and/or space. We will also deal with techniques for evaluating the complexity of algorithms and problems. Finally, we will experiment these algorithmic techniques by implementing some of them using the C language.

Assessment criteria of knowledge

The student will be assessed on her/his demonstrated ability to discuss and put into practice the main topics presented during the course.

Methods:

  • Final oral exam
  • Final written exam
  • Final laboratory practical demonstration
Skills

Basic skills on algorithm and data structure design and time/space complexity evaluation.

Assessment criteria of skills

Via written and oral exams.

Behaviors

Students will be able to evaluate performance of basic algorithms before their implementation, directly from their design. Know some difficult problems and which algorithmic design choices can impact positively or negatively the algorithm design.

Assessment criteria of behaviors

Via written and oral exams

Prerequisites

Basics of Maths and C programming.

Teaching methods

Delivery: face to face

Learning activities:

  • attending lectures
  • participation in discussions
  • individual study
  • Laboratory work

Attendance: Advised

Teaching methods:

  • Lectures
  • laboratory

For details look at the home page of the course.

Syllabus

Short introduction to computational issues: decidability and tractability (P, NP, NPC, EXP-TIME). Computational complexity: computation model, input and output size, decision tree, lower and upper bounds, worst and avarage case. Divide-et-impera; recurrence relations, fundamental theorem. Algorithms on static/dinamic sequences: search and sorting. Stable marrigies problem and maximum sum subsequence. Dynamic Programming: LCS, Partition and Backpack. Combination and permutation generation. Greedy: Knapsack and its variants. Trees representation and visit. Dictionaries: 2-3 trees, hash tables, trie. Randomized Algorithms: Quicksort, QuickSelect. Graphs: representation and visit (DFS e BFS), DAG and topological sorting.

Bibliography

T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms. MIT Press, third edition, 2009.

Further bibliography will be indicated and linked in the home page of the course.

Assessment methods

Via written and oral exams, and a C programming test.

Ultimo aggiornamento 24/11/2017 08:57