OVERVIEW

The course aims to introduce the student to the design and analysis of algorithms. Through the presentation of the amain data structures and the algorithms related to them, the student will learn how to understand algorithms and the  main techniques related to them.

AIMS AND CONTENT

LEARNING OUTCOMES

The course introduces the main strategies to design algorithms and the tools to assess their correctness and performances. The goal is to develop the student's capabiliry to formalize and solve problems algorithmically. Also, the student should gain the capability of analising and evaluating alternative solutions.

AIMS AND LEARNING OUTCOMES

The course introduces the main strategies of algorithm design:

• Brute Force: solving problems starting from their formal definition
• Divide and Conquer: approaching problems by dividing them up into smaller ones (usually of the same size) and the recombining partial solutions
• Diminish and Conquer: reduce the problem size iteratively (of a constant, of a constant factor, of a variable factor)
• Transform and Conquer: approaching problems by reformulating them in order to simplify their solution
• Space-Time Tradeoff: improving on time efficiency by utilizing memory overheads
• Greedy Algorithms: solving combinatorial optimization problems by adopting greedy strategies, i.e., locally optimal choices which reveal to be optimal also in the global sense.

Overall, the expected outcome is to obtain a good knowlege of the main algorithms, at least one per family. The result will be the ability to solve computational problems with an algorithms approach and analyze the complexity through analytical or empirical means.

PREREQUISITES

A good knowledge of at least one programming language of the family C/C++/Java is required.

Knowledge of combinatorics, basic algebra and theoretical computer science are useful to better understand the topics covered in the course.

TEACHING METHODS

Lectures and computer labs

SYLLABUS/CONTENT

Models for the evaluation of algorithms. Analytical instruments. Problem ‐ solving strategies: “Brute Force”, “Divide and Conquer”, “Diminish and Conquer”, “Transform and Conquer”, “Space ‐ time trade ‐ off”, “Greedy Strategy”, Study and analysis of algorithms and data structures: sorting and searching, sequential structures, trees and heaps, hash tables, string and text analysis.

RECOMMENDED READING/BIBLIOGRAPHY

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein ‐ Introduzione agli algoritmi e strutture dati ‐ 3a Edizione ‐ McGraw ‐ Hill; A. Levitin ‐ Introduction to The Design and Analysis of Algorithms ‐ 2nd edition ‐ Addison ‐ Wesley; S. Skiena ‐ The Algorithm Design Manual ‐ 2nd edition – Springer; R. Sedgewick ‐ Algorithms in C++ ‐ 3rd edition ‐ Vol 1 ‐ 5 ‐ Addison Wesley

TEACHERS AND EXAM BOARD

Exam Board

ARMANDO TACCHELLA (President)

GIUSEPPE CICALA

ENRICO GIUNCHIGLIA

MARCO MARATEA

MASSIMO NARIZZANO

LESSONS

LESSONS START

September 2019

Class schedule

DESIGN AND ANALYSIS OF ALGORITHMS

EXAMS

EXAM DESCRIPTION

Homeworks (2 projects, max 3 points each)  Computer ‐based test (max 12 points) and interview (max 12 points)

ASSESSMENT METHODS

Capability to frame solutions of computational problems through algorithms, and analyze the correctness and the performances of the solutions with analytical means.

Exam schedule