CODE  65896 

ACADEMIC YEAR  2023/2024 
CREDITS 

SCIENTIFIC DISCIPLINARY SECTOR  INGINF/05 
LANGUAGE  Italian 
TEACHING LOCATION 

SEMESTER  1° Semester 
TEACHING MATERIALS  AULAWEB 
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
 SpaceTime 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, possibly delivered online.
SYLLABUS/CONTENT
Design and Analysis of Algorithms
Introduction: definition of algorithm; fundamental aspects of problem solving through algorithms; problem types and solution strategies; specification of algorithms through flow charts and pseudocode; syntax and semantics of pseudocode.
Fundamental data structures; linear structures (array, strings, stacks, queuses and listsl); graphs (definitions and data structures) ; trees (definitions and data structures) ; sets, dictionaries and maps (fundamentals).
Basic elements: algorithms efficiency, computational resources and RAM model; asymptotic notation (properties and fundamental classes); analysis of algorithms (worst case, best case, average case); lower bound and optimality; amortized efficiency.
"Brute Force" Strategy: methodology and examples of analysis for nonrecursive algorithms (finding maximum, element uniqueness, matrix multiplication). Elementary sorting algorithms on vectors (Selection Sort). Sequential search on vectors; sets, dictionaries and maps with dynamical arrays and linked lists; string search (string matching).
"Divide and conquer" Strategy: methodology and examples of analysis for recursive algorithms; Master Theorem. Sorting algorithms (Mergesort and Quicksort); lower bound for sorting algorithms based on comparisons; binary trees (definition, computing the height, visiting trees); syntax analysis in formal languages (language, context free grammars); recursive topdown parsing.
"Decrease and conquer": sorting algorithms on vectors (Insertion Sort); graph visits (depth first and breadth first); topological sort; finding strongly connected components on directed graphs; binary search in vectors; compute powers for integers and matrices; binary search trees.
"Transform and conquer": heap data structures; using heap to sort vectors and handle priority queues; experimental compariso between O(nlogn) sorting algorithms; Horner's method to compute polynomials; disjoint sets and unionfind techniques; balanced search trees: 23 trees and LLRB trees; tries.
"SpaceTime tradeoff": linear time sorting (Counting Sort); direct access tables, hash tables (separate chaining); hash functions.
"Greedy Algorithms" : Prim and Kruskal algorithms to compute minimum spanning trees; Dijkstra algorithms to compute minimum paths; Huffman codes for data compression.
Object Oriented Programming (with references to Core Java I e II)
Introduction and reprise of objects and classes (Core Java I  Cap. 4) and inheritance (Core Java I  Cap. 5), "legacy" library for reading and writing text files.
Interfaces, lambda expressions and inner classes (Core Java I  Cap. 6); strings and memory handling, measuring performances.
Object oriented programming: UML (class diagram, sequence diagram, state diagram);
Exceptions and logging (Core Java I  Cap. 7), releasing Java applications (Core Java I  Cap. 13)
Generic programming (Core Java I  Cap. 8), Java collection framework (Core Java I  Cap. 9)
Design Patterns (creational, structural and behavioral); most common patterns (Factory Method, Iterator, Composite, Decorator, Interpreter, Visitor, Observer)
Streams (Core Java II  Cap. 1) and I/O (Core Java II  Cap. 2)
RECOMMENDED READING/BIBLIOGRAPHY
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein ‐ Introduzione agli algoritmi e strutture dati ‐ 3a Edizione ‐ McGraw ‐ Hill;
R. Sedgewick ‐ Algorithms ‐ 4th edition ‐ Addison Wesley
A. Levitin ‐ Introduction to The Design and Analysis of Algorithms ‐ 2nd edition ‐ Addison ‐ Wesley;
S. Skiena ‐ The Algorithm Design Manual ‐ 2nd edition – Springer;
Cay Horstmann  Core Java (Vol. 1 e 2)  Prentice Hall
TEACHERS AND EXAM BOARD
Ricevimento: Please make an appointment with the teacher via email
Exam Board
ARMANDO TACCHELLA (President)
MARCO MARATEA
MASSIMO NARIZZANO
ENRICO GIUNCHIGLIA (President Substitute)
LESSONS
LESSONS START
Class schedule
L'orario di tutti gli insegnamenti è consultabile all'indirizzo EasyAcademy.
EXAMS
EXAM DESCRIPTION
Homework (1 project, max 10 points) and interview (max 20 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
Data  Ora  Luogo  Degree type  Note 

12/01/2024  10:00  GENOVA  Orale  
30/01/2024  10:00  GENOVA  Orale  
16/02/2024  10:00  GENOVA  Orale  
10/06/2024  10:00  GENOVA  Orale  
01/07/2024  10:00  GENOVA  Orale  
22/07/2024  10:00  GENOVA  Orale  
02/09/2024  10:00  GENOVA  Orale 