- Docente: Gianluigi Zavattaro
- Credits: 6
- SSD: ING-INF/05
- Language: Italian
- Teaching Mode: Traditional lectures
- Campus: Bologna
-
Corso:
First cycle degree programme (L) in
Mathematics (cod. 8010)
Also valid for First cycle degree programme (L) in Computer Science (cod. 8009)
Learning outcomes
Knowing the main data structures (like sequences, trees, dictionaries, priority queues, graphs) and the main algorithms for solving some basic computational problems (like searching, sorting, tree and graph visits, minimum spanning trees, shortest paths, matrix multiplication) . Understanding and using the main methodologies (e.g. divide-&-conquer, dynamic programming, greedy, backtracking, local search) for designing efficient iterative and recursive algorithms. Understanding and using the main techniques for analyzing iterative and recursive algorithms. Knowing the basic computational classes (P, NP, NP-hardness) and evaluating the inherent difficulty of basic computational problems.
Course contents
Data structures. Arrays, records, lists, stacks, queues. Trees. Tree visits (preorder, inorder, postorder). Sets. Dictionaries. Binary search. Hash tables. Priority queues. Heaps. Heapsort. Balanced search trees. MFSET. Graphs. DFS and BFS. Design and analysis of algorithms. Computational complexity. Order of growth. Recurrence equations. Lower bounds. Design techniques: divide-&-conquer, backtrack, greedy, local search, dynamic programming. Sorting: Mergesort, Quicksort, Shellsort. Complexity. The P and NP classes. NP-completeness. Pseudo-polynomial, approximate, branch-&-bound, and probabilistic algorithms. Heuristics.
There is also a module of laoratory in which data structures are implemented and used, and the Object-Oriented paradigm as well as some Java notions are introduced.
Readings/Bibliography
A.A. Bertossi & A. Montresor, Algoritmi e Strutture di Dati, Citta' Studi Edizioni, Torino, 2014.
Teaching methods
The course is aught during the second semester, and it comprises lessons and lectures. First, theoretical foundations are presented. After base notions are introduced, the main data structures and computational problems are presented. Algorithms for solving such problems are designed, pointing out the design techniques employed. For each proposed algorithm, theorems are stated, and sometimes proved, showing their correctness and temporal computational complexity. Next, several exercises are solved. Moreover, practical design and implementation of data structures are consuidered in the laboratory lessons.
Assessment methods
The assessment consists in a project and in a final written examination.
The project can be done by small goups of students and must be discussed with the teacher before the written exam.
Teaching tools
Projector.
Office hours
See the website of Gianluigi Zavattaro