The aim of the course is to illustrate the main techniques for algorithms design and to describe and analyze the most known basic algorithms together with respective used data structures, with particular focus on computational complexity facets.

01. Introduction to algorithms and data structures:
   01.01 Algorithms and their typologies
   01.02 Correctness of an algorithm with respect to a problem
   01.03 Complexity of an algorithm with respect to resource usage
   01.04 Data structures and their typologies

02. Classes of problems:
   02.01 Decidable and undecidable problems
   02.02 Tractable and intractable problems
   02.03 Cook theorem
   02.04 NP-completeness

03. Complexity of the algorithms:
   03.01 Notations to express the asymptotic complexity
   03.02 Computing the complexity of non-recursive algorithms
   03.03 Computing the complexity of recursive algorithms

04. Array algorithms:
   04.01 Arrays: basic definitions and classical problems
   04.02 Traversal algorithm for arrays
   04.03 Linear search algorithm for arrays
   04.04 Binary search algorithm for sorted arrays
   04.05 Comparison criteria for sorting algorithms for arrays
   04.06 Insertsort
   04.07 Selectsort
   04.08 Bubblesort
   04.09 Mergesort
   04.10 Quicksort
   04.11 Heapsort

05. List algorithms:
   05.01 Lists: basic definitions and classical problems
   05.02 Traversal, search, insertion and removal algorithms for lists
   05.03 Insertion and removal algorithms for queues
   05.04 Insertion and removal algorithms for stacks

06. Tree algorithms:
   06.01 Trees: basic definitions and classical problems
   06.02 Traversal and search algorithms for binary trees
   06.03 Search, insertion and removal algorithms for binary search trees
   06.04 Balancing criteria for binary search trees

07. Hash tables:
   07.01 Dictionaries, associative arrays, maps: basic functions and implementation through arrays, lists, trees
   07.02 Direct access tables
   07.03 Hash functions
   07.04 Collision resolution: collision lists, open addressing

08. Graph algorithms:
   08.01 Graphs: basic definitions and classical problems
   08.02 Traversal and search algorithms for graphs
   08.03 Topological sorting algorithm for direct acyclic graphs
   08.04 Properties of the shortest path
   08.05 Bellman-Ford algorithm
   08.06 Dijkstra algorithm

09. Algorithmic techniques:
   09.01 Divide-and-conquer technique
   09.02 Dynamic programming
   09.03 Greedy technique
   09.04 Backtracking technique

10. Laboratory activity:
   10.01 C language fundamentals: recall, editing, compilation, debugging
   10.02 Algorithms complexity experimental evaluation: timing and counters
   10.03 Pseudorandom number generators: rand and srand functions
   10.04 Experimental comparison of sorting algorithms for arrays
   10.05 Implementation of algorithms for lists
   10.06 Implementation of traversal and search algorithms for binary trees
   10.07 Implementation of graph algorithms: breadth-first and depth-first traversal algorithms

Although there are no mandatory prerequisites for this exam, students are strongly recommended to take it after Procedural Programming and Calculus 1.
It is also worth noticing that the topics covered by this course will be used in Operating Systems, Databases, Object Oriented Programming and Modeling, and Logic and Functional Programming.

Knowledge and understanding:
At the end of the course, the student will learn: to be aware of the importance of efficient design of algorithms; the fundamental knowledge for analyzing the computational resources required by an algorithm; the main algorithms and data structures for solving basic computational problems.

Applying knowledge and understanding:
The student will learn the methodologies typical of algorithmic design and analysis. In particular she/he will be able to design a series of classic algorithms (sorting, search, etc.) working on different data structures (arrays, lists, trees, graphs) and to analyze their computational complexity. The ability to apply these techniques will be developed and sharpened during laboratory activities, where various algorithms will be analyzed and implementated in C language.

Making judgements:
The student will learn how to apply the algorithmic methodologies to understand and solve new problems of computational nature. Critical discussions during classes and laboratory activities will stimulate and develop the making judgements ability of the student.
 
Communication skills:
The student will acquire the ability to communicate the fundamental concepts of algorithms and data structures with an appropriate and rigorous terminology. She/he will learn to describe the problems related to the design and analysis of efficient algorithms, and the methodologies adopted to solve them. 

Learning skills:
The student will acquire the ability to study and learn algoritmic techniques and fundamental data structures. She/he will learn to recognize the importance of computational resources (in particular space and time) in order to be able to autonomoulsy develop solutions for novel problems related to efficient program design.

The teaching material prepared by the lecturer in addition to recommended textbooks (such as for instance slides, lecture notes, exercises, bibliography) and communications from the lecturer specific to the course can be found inside the Moodle platform › blended.uniurb.it

Multiple choice questions and solved exercises for the self-assessment of the student's preparation available on the Moodle platform for blended learning.

Teaching

Theory lectures and laboratory exercises.

Attendance

Although recommended, course attendance is not mandatory.

Course books

Cormen, Leiserson, Rivest, Stein, "Introduzione agli Algoritmi e alle Strutture Dati", McGraw-Hill, 2023.
(Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms", MIT Press, 2022.)
Demetrescu, Finocchi, Italiano, "Algoritmi e Strutture Dati", McGraw-Hill, 2008.
Crescenzi, Gambosi, Grossi, "Strutture di Dati e Algoritmi", Pearson/Addison-Wesley, 2012.
Sedgewick, "Algoritmi in C", Pearson, 2015.
(Sedgewick, "Algorithms in C", Addison-Wesley, 1998.)

Assessment

Written exam and oral exam. 
This procedure is aimed in particular at evaluating the achievement of applying knowledge and understanding, with respect to problem solving and efficient usage of computational resources and, at the same time, at assessing the student's capabilities of summarizing concepts and her/his communication skills.

The written exam (2 hours long) consists of a programming exercise (to be solved at the computer) and of a set of multiple choice questions; it is considered passed if the mark (which is valid only for the exam call in which the written exam is taken) is at least 18/30. 

If scheduled by the academic calendar, during the period of suspension of teaching activities of the semester in which the course is held, an intermediate written test is held, in which only first-year students can participate, consisting of 15 multiple choice questions to be answered in 45 minutes. It is passed if the grade is at least 8/15 out of a maximum of 15/15, in which case exemption from the questions of the written test relating to the sections of the program covered by the intermediate test is obtained; the grade remains valid only for the exams of the first exam session following the semester in which the intermediate test takes place.

The oral exam, which can be taken only if the written exam has been passed, consists of questions about the course program. If passed, it determines a spread between -5/30 and 5/30 of the previous marks, thus yielding the final mark. 

During the period of suspension of the teaching activities envisaged in the academic calendar intermediate tests will take place.

Disability and Specific Learning Disorders (SLD)

Students who have registered their disability certification or SLD certification with the Inclusion and Right to Study Office can request to use conceptual maps (for keywords) during exams.

To this end, it is necessary to send the maps, two weeks before the exam date, to the course instructor, who will verify their compliance with the university guidelines and may request modifications.

Teaching

As for attending students.

Attendance

As for attending students.

Course books

As for attending students.

Assessment

As for attending students.

Disability and Specific Learning Disorders (SLD)

Students who have registered their disability certification or SLD certification with the Inclusion and Right to Study Office can request to use conceptual maps (for keywords) during exams.

To this end, it is necessary to send the maps, two weeks before the exam date, to the course instructor, who will verify their compliance with the university guidelines and may request modifications.