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
 04.12 Priority queues based on binary heaps
 
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
 06.05 Search, insertion and removal algorithms for red-black binary search trees
 
07. Graph algorithms:
 07.01 Graphs: basic definitions and classical problems
 07.02 Traversal and search algorithms for graphs
 07.03 Topological sorting algorithm for direct acyclic graphs
 07.04 Strongly connected component algorithm for graphs
 07.05 Kruskal algorithm
 07.06 Prim algorithm
 07.07 Properties of the shortest path
 07.08 Bellman-Ford algorithm
 07.09 Dijkstra algorithm
 07.10 Floyd-Warshall algorithm
 
08. String algorithms:
 08.01 Strings: basic definitions and classical problems
 08.02 String matching naive algorithm
 08.03 Edit distance computation algorithm
 08.04 Longest common subsequence algorithm
 
09. Selection and order statistics:
 09.01 Basic definitions and problems
 09.02 Heapselect
 09.03 Randomized selection
 09.04 Deterministic selection
 
10. Algorithmic techniques:
 10.01 Divide-and-conquer technique
 10.02 Dynamic programming
 10.03 Greedy technique
 10.04 Backtracking technique
 
11. Laboratory activity:
 11.01 C language fundamentals: recall, editing, compilation, debugging
 11.02 Pseudorandom number generators: rand and srand functions
 11.03 Algorithms complexity experimental evaluation: timing and counters
 11.04 Experimental comparison of sorting algorithms for arrays 
 11.05 Experimental comparison of search algorithms for binary trees 
 11.06 Implementation of graph algorithms: breadth-first and depth-first traversal algorithms, Dijkstra algorithm
 11.07 Implementation of string algorithms: Edit Distance and LC

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

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

Teaching

Theory lectures and laboratory exercises, both face-to face and on-line.

Attendance

Although recommended, course attendance is not mandatory.

Course books

Cormen, Leiserson, Rivest, Stein, "Introduzione agli Algoritmi e alle Strutture Dati", McGraw-Hill, 2010.
(Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms", MIT Press, 2009.)
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

Project (to be developed individually or by groups of two students), written exam, and oral exam.

The individual project, which changes at each exam session, has to be submitted at least seven days before the written exam. The project is passed if the mark (which is valid for all the exam calls of the same academic year) is at least 18/30. Should the project be resubmitted in a subsequent exam call, the mark of the previously submitted project is cancelled. If the resubmission takes place in the same exam session, a 5/30 penalty is applied to the mark of the newly submitted project. 

The written exam, which can be taken only if the project has been passed, consists of seven questions to be answered in one hour and is passed if the mark (which is valid only for the exam call in which the written exam is taken) is at least 18/30. 

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

Disabilità e DSA

Le studentesse e gli studenti che hanno registrato la certificazione di disabilità o la certificazione di DSA presso l'Ufficio Inclusione e diritto allo studio, possono chiedere di utilizzare le mappe concettuali (per parole chiave) durante la prova di esame.

A tal fine, è necessario inviare le mappe, due settimane prima dell’appello di esame, alla o al docente del corso, che ne verificherà la coerenza con le indicazioni delle linee guida di ateneo e potrà chiederne la modifica.

The course is offered also on-line inside the Moodle platform > elearning.uniurb.it