View syllabus
ALGORITHM ENGINEERING
PAOLO FERRAGINA
Academic year2023/24
CourseCOMPUTER SCIENCE AND NETWORKING
Code531AA
Credits9
PeriodSemester 1
LanguageEnglish

ModulesAreaTypeHoursTeacher(s)
ALGORITHM ENGINEERINGINF/01LEZIONI72
PAOLO FERRAGINA unimap
Obiettivi di apprendimento
Learning outcomes
Conoscenze

Lo studente che completerà il percorso didattico acquisirà una serie di abilità e conoscenze nella progettazione e nell'analisi (teorica e sperimentale) di algoritmi e strutture dati avanzate per la soluzione efficiente di problemi combinatori che coinvolgono tipi di dati elementari quali interi, stringhe, punti geometrici, alberi e grafi. Questi "strumenti" algoritmici saranno progettati e analizzati in vari modelli di computazione —quali RAM, memoria a 2-livelli,  cache-oblivious, streaming— così da tenere in considerazione le caratteristiche architetturali dei moderni PC.

Knowledge

The student who successfully completes the course will have the knowledge and skills to design and analyze (theoretically and experimentally) advanced algorithms and data structures for the efficient solution of combinatorial problems involving all basic data types, such as integers, strings, (geometric) points, trees and graphs. These algorithmic tools will be designed and analyzed in several models of computation— such as RAM, 2-level memory, cache-oblivious, streaming— in order to take into account the architectural features and the memory hierarchy of modern PCs.

Modalità di verifica delle conoscenze

Gli studenti verranno valutati sulle base delle loro abilità e conoscenze relative ai contenuti del corso sia per quanto riguarda l'uso della terminologia, sia per quanto riguarda le loro capacità di problem solving basate sugli strumenti algoritmici appresi in classe. La verifica consisterà di un esame scritto/orale, con l'eventualità di prove intermedie. 

Ulteriori informazioni sono disponibili nella home page del corso.

Assessment criteria of knowledge

The student will be assessed on his/her demonstrated ability and knowledge about the main course contents using the appropriate terminology and about his/her problem-solving capabilities given the algorithmic tools taught in class.

Methods:

  • Final oral exam
  • Final written exam, with possibly midterm exams

Further information can be found in the home page of the course.

Capacità

Gli studenti saranno in grado di progettare e analizzare algoritmi e strutture dati per la memorizzazione, la ricerca e il processing di vari tipi di Big Data.

Skills

Students will be able to design and analyze algorithms and their corresponding data structures for the storage, searching and processing of Big Data of various types.

Modalità di verifica delle capacità

La verifica consisterà di un esame scritto/orale, con l'eventualità di prove intermedie. Ulteriori informazioni sono disponibili nella home page del corso.

Assessment criteria of skills

Methods:

  • Final oral exam
  • Final written exam

Further information can be found in the home page of the course

Comportamenti

Gli studenti apprenderanno le tecniche fondamentali per il progetto di algoritmi e strutture dati avanzati per Big Data, e alcuni risultati allo stato dell'arte.

Behaviors

Students will be aware of latest algorithm design techniques to be deployed in their software design choices.

Modalità di verifica dei comportamenti

La verifica consisterà di un esame scritto/orale, con l'eventualità di prove intermedie. Ulteriori informazioni sono disponibili nella home page del corso.

Assessment criteria of behaviors

Methods:

  • Final oral exam
  • Final written exam, possibly with midterm exams

Further information can be found in the home page of the course

Prerequisiti (conoscenze iniziali)

Corso base di algoritmi e strutture dati, math e programmazione

Prerequisites

Basics of Algorithms, Maths, Programming.

Indicazioni metodologiche

Lezioni di didattica frontale, e attraverso lo studio individuale.

 

 

Teaching methods

Delivery: face to face 

Learning activities:

  • attending lectures
  • individual study

Attendance: Advised

Teaching methods:

  • Lectures
Programma (contenuti dell'insegnamento)

In questo corso studieremo, progetteremo e analizzeremo (dal punto di vista teorico e pratico)  algoritmi e strutture dati avanzate per la soluzione efficiente di problemi combinatori che coinvolgono tipi di dato elementare quali interi, stringhe, punti geometrici, alberi e grafi. Questi "strumenti" algoritmici saranno progettati e analizzati in vari modelli di computazione —quali RAM, memoria a 2-livelli,  cache-oblivious, streaming— così da tenere in considerazione le caratteristiche architetturali dei moderni PC.

Ogni lezione seguirà un approccio top-down che partirà dalla discussione di un problema reale che occorre nel progetto di software che gestiscono Big Data, lo astrarrà in modo formale utilizzando un linguaggio matematico, utile per un indagine algoritmica, e poi introdurrà soluzioni algoritmiche atte a minimizzare l'uso di alcune risorse computazionali quali tempo, spazio, comunicazione, I/O, energia, ecc..

Syllabus

In this course we will study, design and analyze (theoretically and experimentally) advanced algorithms and data structures for the efficient solution of combinatorial problems involving all basic data types, such as integers, strings, (geometric) points, trees and graphs. These algorithmic tools will be designed and analyzed in several models of computation— such as RAM, 2-level memory, cache-oblivious, streaming— in order to take into account the architectural features and the memory hierarchy of modern PCs. Every lecture will follow a problem-driven approach that starts from a real software-design problem, abstracts it in a combinatorial way (suitable for an algorithmic investigation), and then introduces algorithmic solutions aimed at minimizing the use of some computational resources like time, space, communication, I/O, energy, etc.

Bibliografia e materiale didattico

Le lezioni faranno uso della lavagna.

Il docente ha pubblicato un libro per Cambridge University Press proprio sui contenuti del corso: https://www.cambridge.org/core/books/pearls-of-algorithm-engineering/95061352D7263CCCBD4F243018236EB2

Bibliography

No slides for teaching, and we will use just the old-fashioned blackboard. 

 

The teacher has published a book for Cambridge University Press on the course's content: https://www.cambridge.org/core/books/pearls-of-algorithm-engineering/95061352D7263CCCBD4F243018236EB2

Indicazioni per non frequentanti

Come per i frequentanti

Non-attending students info

Same as attending students

Modalità d'esame

L'esame consiste di due parti scritte: una ha come obiettivo quello di valutare le conoscenze acquisite (teoria), e l'altra ha come obiettivo quello di valutare le capacità di problem solving (esercizi) degli studenti. 

Assessment methods

The exam consists of two parts: a written set of exercises to be solved in a given amount of time, and a written set of theory questions on the content of the course.

Altri riferimenti web

https://www.cambridge.org/core/books/pearls-of-algorithm-engineering/95061352D7263CCCBD4F243018236EB2

Additional web pages

https://www.cambridge.org/core/books/pearls-of-algorithm-engineering/95061352D7263CCCBD4F243018236EB2

Updated: 26/07/2023 11:47