37635 - Data Structure and Algorithms

Academic Year 2022/2023

  • Moduli: Gianluigi Zavattaro (Modulo 1) Pietro Di Lena (Modulo 2)
  • Teaching Mode: Traditional lectures (Modulo 1) Traditional lectures (Modulo 2)
  • Campus: Bologna
  • Corso: First cycle degree programme (L) in Computer Science (cod. 8009)

Learning outcomes

At the end of the course the student: - knows the algorithms to solve basic computational problems on elementary data structures; - knows the basic techniques to compute the computational complexity of an algorithm; - knows the computational complexity classes P, NP, and NP-hard; - is able to design efficient algorithms to solve simple computational problems; - is able to analyze the computational complexity of basic computational problems; - is able to realize and present a project for solving 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. 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, greedy, dynamic programming. Sorting: Insertion Sort, Merge Sort, Heap Sort, Quick Sort, Counting Sort, Bucket Sort, Radix Sort. Algorithms on graphs: Minimum Spanning Tree (Prim, Kruskal), Shortest Paths (Bellman-Ford, Dijkstra, Floyd-Warshall). Complexity. The P and NP classes. NP-completeness.

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

Main text:

Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Algoritmi e strutture dati
McGraw-Hill - seconda edizione. 2008.

Suggested books:

A.A. Bertossi & A. Montresor, Algoritmi e Strutture di Dati, Citta' Studi Edizioni, Torino. Terza edizione. 2014.

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Introduzione agli algoritmi e strutture dati
McGraw-Hill - terza edizione. 2010

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.

The written exam lasts 2 hours, during which no books, notes, calculator and electronic devices are allowed. The written exam consists of 4 questions, some of which are exercises whose purpose is to check the practical ability to design correct and efficient algorithms to solve computational problems, while other are open-answer questions whose objective is to verify that the expected theoretical knowledge has been acquired.

Teaching tools

Projector.

Office hours

See the website of Gianluigi Zavattaro

See the website of Pietro Di Lena

SDGs

Quality education

This teaching activity contributes to the achievement of the Sustainable Development Goals of the UN 2030 Agenda.