View syllabus
ALGORITHMS AND DATA STRUCTURES
PIETRO DUCANGE
Academic year2021/22
CourseCOMPUTER ENGINEERING
Code756II
Credits6
PeriodSemester 2
LanguageItalian

ModulesAreaTypeHoursTeacher(s)
ALGORITMI E STRUTTURE DATIING-INF/05LEZIONI60
PIETRO DUCANGE unimap
ANTONIO VIRDIS unimap
Obiettivi di apprendimento
Learning outcomes
Conoscenze

Le conoscenze che lo studente deve acquisire riguardano la complessità computazionale degli algoritmi e alcuni algoritmi di base per la soluzione di problemi diversi su diverse strutture dati (array, liste, alberi, grafi). Inoltre deve acquisire la conosenza di elementi avanzati di programmazione a oggetti nel linguaggio di programmazione c++ (funzioni e classi modello, ereditarietà, eccezioni).

Knowledge

The knowledge that the students must acquire relates to the computational
complexity of the algorithms and some basic algorithms for solving different
problems on different data structures (arrays, lists, trees, graphs).
It must also acquire the knowledge of advanced object programming
elements in the c ++ programming language.

Modalità di verifica delle conoscenze

Tramite una prova finale scritta che presenta quesiti relativi alle conoscenze, esercizi di analisi di programmi, esercizi di programmazione di semplici algoritmi sulle strutture dati introdotte.

Assessment criteria of knowledge

Through a written final exam that introduces knowledge-related questions,
program analysis exercises, programming exercises of simple algorithms
on the data structures introduced.
  of a written final exam that presents knowledge-related questions,
program analysis exercises, programming of simple algorithms on
the data structures introduced.

Capacità

Analisi della complessità degli algoritmi. Progettazione  di algoritmi e loro implementazione in c++ sulle strutture dati presentate.

Skills

Complexity analysis of programs. c ++ programming of algorithms on introduced
data structures.

Modalità di verifica delle capacità

Mediante una prova pratica (esercizio di programmazione) in laboratorio di programmazione che riguarda la progettazione di un algoritmo e la sua realizzazione nel linguaggio c++.

 

La capacità di programmazione viene ulteriormente verificata con la prova scritta (test a risposta multipla).

Assessment criteria of skills

Through a practical programming test that involves the design of an algorithm
and its implementation in the c ++ language.
The programming capacity is further verified with the written test.

Comportamenti

Saranno acquisite sensibilità alle problematiche della programmazione.

Behaviors

Sensitivity to coding issues will be gained.

Modalità di verifica dei comportamenti

Tramite le due prove di esame.

Assessment criteria of behaviors

By two exam stages (multiple choice test and programming test)

Prerequisiti (conoscenze iniziali)

Prerequisito obbligatorio di questo insegnamento è il superamento dell'unità didattica

 Fondamenti di Programmazione

 

Prerequisites

Mathematics knowledge of higher schools. Basic knowledge of c ++ programming language.

Indicazioni metodologiche

Il corso sarà erogato secondo le modalità stabilite dall'ateneo. Sono previste sessioni di lezioni teoriche ed esercitazioni pratiche al calcolatore. Si consiglia a ciascuno studente di fornirsi di laptop personale per seguire le attività pratiche.

 

Teaching methods

The course will be delivered in the manner established by the university. There will be sessions of theoretical lectures and practical exercises at the computer. Each student is advised to provide a personal laptop to follow the practical activities.

Programma (contenuti dell'insegnamento)

Nozione di algoritmo.

Definizione di complessità computazionale (notazioni O-grande, Omega-grande e Theta-grande).

Complessità dei programmi iterativi. Principi e metodi di programmazione ricorsiva. Complessità dei programmi ricorsivi: relazioni di ricorrenza.

Strutture lineari : array e liste. Principali algoritmi di ricerca (lineare, binaria) e ordinamento (selection-sort, bubble-sort, quicksort, mergesort, heapsort, counting sort, radix sort)

Alberi binari: memorizzazione, visite e programmazione di semplici algoritmi.

Alberi generici: : memorizzazione, visite e programmzione di semplici algoritmi. 

Alberi binari di ricerca.

Tipo di dato heap.

Metodo di ricerca Hash.

Metodologie di costruzione di algoritmi: divide et impera, programmazione dinamica, programmazione greedy.

Algoritmo per trovare la più lunga sottosequenza comune fra due sequenze.

Algoritmo di Huffman di compressione del codice.

Limiti inferiori: metodo per trovarli mediante gli alberi di decisione.

Grafi orientati e non orientati: definizione e memorizzazione. Visita in profondità

 Algoritmo di Kruskal per trovare il minimo albero di copertura

Algoritmo di Dijkstra per trovare i cammini minimi da un nodo a tutti gli altri nodi.

Cenni alla NP-completezza: problemi intrattabili, le classi P e NP, riducibilità  fra problemi, problemi NP-completi, problemi non risolubili.

Nozioni avanzate di programmazione a oggetti in c++: funzioni e classi modello, eraditarietà semplice, gestione delle eccezioni.

 

 

Syllabus

Notion of Algorithm.

Computational complexity of algorithms: big-O , big-omega and big-theta notations.

Complexity of iterative programs. Principles and methods of recursion. Complexity of recursive programs: recurrence equations.

Principal research algorithm: linear serach, binary search.

Principal sorting algorithms: selection-sort, bubble-sort, quicksort, mergesort, heapsort, counting sort, radix sort.

Binary trees and bynary search trees. Generic trees. Heap. Hash tables. Decision trees.

programming methodologies: divide and conquer, dynamic programming, greedy algorithms.

Graphs: depth visit, Kruskal algorithm for finding the minimum spanning tree, Dijkstra algorithms for finding the minimum paths from a node.

Theory of NP-completness.

Advanced notions of objecy tprogramming in c++: templates, inheritance, exceptions.

 

Bibliografia e materiale didattico

Gli appunti del corso e le slide delle lezioni e dei laboratori sono a disposizione sulla piattaforma di eLearning (Google Classroom).

Testi consigliati:

Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano «ALGORITMI E STRUTTURE DATI 2/ED»

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein «INTRODUZIONE AGLI ALGORITMI E STRUTTURE DATI 3/ED»

Bibliography

Course notes and slides from lectures and practical classes are available on the eLearning platform (Google Classroom).

Recommended texts:

Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano «ALGORITMI E STRUTTURE DATI 2/ED»

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein «INTRODUZIONE AGLI ALGORITMI E STRUTTURE DATI 3/ED»

Indicazioni per non frequentanti

Tutto il materiale didattico è presente sulla piattaforma di eLearning (Google Classroom).

Il docente è a disposizione per ricevimenti prenotabili all'indirizzo: shorturl.at/fgjFL

Non-attending students info

All teaching material is available on the eLearning platform (Google Classroom).

The teacher is available for booking meetings at: shorturl.at/fgjFL

Modalità d'esame

L'esame è costituito da due  prove obbligatorie:
- Test a risposta multipla
- Esercizio di programmazione

Per poter accedere all’esercizio lo studente deve aver raggiunto la sufficienza al test. Le prove devono essere svolte nello stesso appello.

La valutazione finale sarà calcolata come la media dei voti delle due prove.

Il non superamento dell’esercizio di programmazione annulla la valutazione del test a risposta multipla.

 

Assessment methods

The examination consists of two compulsory tests:
- Multiple-choice test
- Programming exercise

To be eligible for the exercise, the student must have achieved a pass mark in the test. The tests must be taken in the same call.

The final mark will be calculated as the average of the marks from the two tests.

Failure to pass the programming exercise invalidates the assessment of the multiple-choice test.

 

Updated: 28/01/2022 17:14