ALGORITHMS AND DATA STRUCTURES AND LABORATORY

Academic Year 2023-2024

Teachers

Carla Piazza
Gabriele Puppis
Alessandro Giuseppe Privitera

Course Year

Unit Credits

Teaching Period

Annuity

Course Type

Basic

Prerequisites. It is necessary for the student to master the contents of the courses of the I year of the bachelor degree, with particular reference to the courses of Discrete Mathematics (Elements of Mathemathics and Linear Algebra for the degree IBML), Mathematical Analysis, Programming and Lab.

Teaching Methods. The course consists of both theoretical, practical, and lab classes. The e-learning webpage of the course contains all the useful information for the students and some additional exercises.

Verification of Learning. The exam is both written and oral. The student has also to pass a lab test. Upon agreement with the teacher, the exam can be given in English. The written test is mainly used to assess the skills acquired in the algorithmic resolution of problems and in the formalization of such solutions. The oral part is mainly aimed at assessing both the knowledge of data structures, algorithms, and analysis techniques presented during the course and the reasoning abilities.

As far as the evaluation is concerned we refer to the document: https://www.uniud.it/it/didattica/corsi/area-scientifica/scienze-matematiche-informatiche-multimediali-fisiche/laurea/informatica/studiare/criteri.pdf

Objectives

Specific Objectives.

Index:

Basics

The role of algorithms

Algorithm Design

Correctness

Computational Complexity

Basic Data Structures and Algorithms

Arrays, Heaps, Lists, Stacks, Queues, Binary Trees, Hash Tables, and similars.

Algorithms for sorting, searching, insertion, deletion over basic data structures

Proofs of correctness

Computational complexity evaluations

Advanced Data Structures and Design Techniques

Balanced binary trees and search/insert/delete algorithms

B-trees and search/insert/delete algorithms

Data structures for disjoint sets

Graphs and basic graph algorithms

Minimum Spanning Trees

Shortest paths problems/algorithms

Correctness and Complexity of the above listed algorithms

ABILITIES

The student should be able to:

1.1. Knowledge and reasoning ability

Manage basic concepts of static and dynamic data structures and design of algorithms.

Know a formal language for describing algorithms.

Evaluate computational complexities.

Know the data structures and algorithms presented during the course together with their spatial and temporal complexities.

1.2 Ability of exploiting knowledge

Implement and test algorithms seen in the course exploiting the most common programming languages.

Use the data structures and the algorithms presented in the course to design new algorithms that can solve specific problems.

Prove the correctness and evaluate the computational complexities of such algorithms

SOFT SKILLS

The student should be able to:

2.1 Judgement autonomy.

Determine which data structures, algorithms and design techniques use to provide efficient solutions to a given algorithmic problem.

Choose the most computationally efficient solution.

Combine/extend existing algorithms to solve a specific problem.

Demonstrate or refute the correctness and evaluate the computational complexity of algorithms.

Select the programming language and the most suitable libraries for implementing an algorithm.

Test implementations.

2.2 Communicative skills.

Motivate, make choices in terms of data structures and algorithms for solving a given problem.

Find any additional information needed to design an efficient algorithm.

2.3 Learning ability.

Find and exploit scientific resources for the in-depth study of topics studied in the course.

Deal with new problems of algorithmic nature.

Identify new tools for developing data structures and algorithms.

Please refer also to the web-pages:

– Laurea in Informatica

https://www.uniud.it/it/didattica/info-didattiche/regolamento-didattico-del-corso/L-informatica/all-B2

– Laurea in Internet of things, biga data, machine learning

https://www.uniud.it/it/didattica/info-didattiche/regolamento-didattico-del-corso/l-internet-things-big-data-machine-learning/all-B2

The course is an introduction to the foundations of the theory of algorithms and data structures, as well as to the analysis of the computational complexity of programs. The course main aim is to familiarize the student with the most important issues and techniques relative to the algorithm design and project. Moreover, the basic methods employed to establish the computational complexity of programs and the criteria used to choose and design data structures are introduced. 

Texts

1. Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., Introduction to Algorithms, MIT Press, Fourth edition, 2022.

2. Further useful textbooks:

1. A. Bertossi, A. Montresor. Algoritmi e Strutture Dati, 2/ed, Città Studi Edizioni, 2010.

2. C. Demetrescu, I. Finocchi, G. F. Italiano, Algoritmi e Strutture Dati, 2/ed, McGraw-Hill, 2007.

3. P. Crescenzi, G. Gambosi, R. Grossi. Strutture di Dati e Algoritmi, Addison-Wesley Pearson, 2006.

4. Aho A.V., Hopcroft J.E., Ullman J.D., Data Structures and Algorithms, Addison-Wesley, 1983.

5. Aho A.V., Hopcroft J.E., Ullman J.D., The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.

Academic Year 2023-2024