Università degli studi di Modena e Reggio Emilia

You are here: Home » Study Plan » Subject

Contents download

Teachers

Manuela MONTANGERO

Overview

The course is an introduction to the design and analysis of algorithms. The outline includes the nowadays classical arguments of basic as well as some advanced data structures, arithmetic and sorting algorithms, string search algorithms (including a basic introduction to regular expressions and finite automata), graph algorithms, and programming techniques (divide and conquer, greedy, dynamic programming). The course gives special emphasis to the time-space complexity analysis of the algorithms, also introducing the notions of asymptotic worst-case and average case complexity.

Admission requirements

Basic mathematical and programming skills are required. Thus, the student has to attend Mathematical Analysis and Programming courses.

Course contents

Analysis of algorithms. Bit- vs word-complexity. Worst-case asymptotic analysis. Recurrences and master theorem. Binary search.
Data structures: Stack, queue, tree, binary search tree, heap, graph, set, dictionaries and has table.
Divide-and-conquer algorithms and binary search.
Sorting algorithms: Mergesort, quicksort, countingsort, Insertionsort and selectionsort.
Graph traversal. Depth-first search and applications: topological sorting of DAGs, (strongly)-connected components, cycle determination.
Greedy algorithms. Minimum spanning trees. Huffman codes, set covering. Dijkstra algorithm.
Dynamic programming. Bellman-Ford algorithm. Shortest paths in DAGs, All-Pairs shortest Paths. Longest increasing subsequence. Edit distance. Knapsack problems. Iterated matrix multplication.
String matching. Brute-force and Knuth-Morris-Pratt algorithms.

Teaching methods

The course will be delivered through lectures concerning theory and problem solving exercises. According to the current state of the COVID-19 sanitary emergency: - if resolved, lectures will be held in site, mainly using the blackboard and seldomly slides. - if not resolved, following directions given by the University and the Department, lectures will be held exclusively on-line, or on-site with small groups of students giving, however, the possibility to all students to synchronously follow lecture off-site.

Assessment methods

Grades are assigned based on the outcome of a mandatory written exam and one optional oral exams. The written exam is composed of two parts: in the first part students will be asked to show theoretical and applied skills concerning topics addressed during lessons. In the second part students will be asked to solve given problems similar, in complexity, to those presented during the course, i.e., they will be asked to prove they are able to autonomously apply the studied techniques to solve new problems. No material is allowed during the exam. For both parts a threshold is given. If such thresholds are met for both parts, the scores of the two parts are then combined into the final written exam score. An oral examination will be given upon students request. The oral examination might either increase or decrease the score of the written exam. According to the evolution of the sanitary emergency related to COVID-19, exams will be held on-site or on-line.

Learning outcomes

- Knowledge and understanding
Students will have a deep knowledge and understanding of the main algorithm and data structure design technique as well as of complexity analysis methods.

- Applying knowledge and understanding
Students will be helped to develop autonomous abilities to apply the acquired knowledge to: (1) the formal description of computational problems; (2) the identification of appropriate algorithmic solutions; (3) the complexity analysis of the proposed solutions.

- Making judgments
Students will have a good ability to get data and information relevant to the fulfillment of their work, particularly in relation to the formalization of problems and the choice and development of efficient algorithmic strategies for their solution. They will be able to provide independent judgments on the choices made and to critically evaluate the results obtained.

- Communication
In the context of the algorithm design, students will be able to justify the various design options, highlighting their advantages and disadvantages in terms of computational efficiency, using quantitative arguments and a sound technical language. They will be able to proficiently read technical English algorithmic literature.

- Lifelong learning skills
This course will help the student to mature and refine their skills related to lifelong learning in order to keep up with a technical discipline in continuous and rapid evolution.

Readings

Oltre al materiale fornito dal docente, (non in alternativa al testo, ma a complemento) un testo in alternativa tra:

1) Materiali per l'insegnamento di Algoritmi e Strutture Dati,
a cura di Manuela Montangero
McGraw-Hill - Create
ISBN: 978-13-076-6722-6

questo testo contiene principalmente una selezione di capitoli di:

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein
INTRODUZIONE AGLI ALGORITMI E STRUTTURE DATI - Terza Edizione
McGraw-Hill

I capitoli selezionati sono quelli relativi ad argomenti trattati nel corso.

2) A. Bertossi, A. Montresor,
"Algortimi e Strutture Dati",
Citta' Studi