Scheda programma d'esame
ALGORITHMS AND DATA STRUCTURES
ANTONIO VIRDIS
Academic year2023/24
CourseCOMPUTER ENGINEERING
Code756II
Credits6
PeriodSemester 2
LanguageItalian

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

Le conoscenze che lo studente dovrá acquisire riguardano la complessità computazionale degli algoritmi e alcuni algoritmi di base per la soluzione di problemi su diverse strutture dati (array, liste, alberi, grafi). Lo studente inoltre dovrá acquisire conoscenze relative a 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 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 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 progettazione e valutazione di algoritmi, e della loro 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 saranno messi a disposizione sulla piattaforma Microsoft Teams.

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 will be made available on the Microsoft Teams platform.

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 sará reso disponibile sulla piattaforma Microsoft Teams. 

Il docente è a disposizione per ricevimenti prenotabili tramite email.

Non-attending students info

All teaching materialwill be made available on the Microsoft Teams platform

The teacher is available for booking meetings via email.

Modalità d'esame

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

Per poter accedere alla prova pratica di programmazione lo studente deve aver raggiunto la sufficienza al test. Le prove devono essere svolte nello stesso appello.

La valutazione finale sarà calcolata tenendo conto dei voti delle due prove.

Il non superamento della prova pratica 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 considering the marks from the two tests.

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

 

Updated: 23/10/2023 09:52