Salta al contenuto principale della pagina

ALGORITHM ANALYSIS AND DESIGN

CODE 80306
ACADEMIC YEAR 2021/2022
CREDITS
  • 6 cfu during the 2nd year of 8759 INFORMATICA (L-31) - GENOVA
  • 6 cfu during the 2nd year of 9011 MATEMATICA(LM-40) - GENOVA
  • SCIENTIFIC DISCIPLINARY SECTOR INF/01
    LANGUAGE Italian
    TEACHING LOCATION
  • GENOVA
  • SEMESTER 2° Semester
    TEACHING MATERIALS AULAWEB

    OVERVIEW

    The aim of the course is to learn classical data structures and algorithms, and to analyze their correctness and efficiency. Base notions on complexity and elementary data structures are assumed as prerequisites. 

    AIMS AND CONTENT

    LEARNING OUTCOMES

    To learn classical data structures and algorithms, and to be able to analyze their correctness and efficiency. Base notions on complexity and elementary data structures are assumed as prerequisites. Topics include design and analisys techniques, sorting algorithms, advanced data structures, graph algorithms, NP-completeness.

     

    TEACHING METHODS

    Traditional.

    SYLLABUS/CONTENT

    Design and analysis techniques, asymptotic notations, correctness and complexity of recursive and iterative algorithms, divide-et-impera, dynamic programming, greedy algoritms.

    Sorting: simple sorts, mergesort, quicksort, heapsort, lower bound for comparison-based sorting algorithms, linear sorts.

    Advanced data structures: heaps, union-find structures.

    Graphs: definitions, representations, visits, topological sorting, strongly-connected components, single-source shortest paths (Dijkstra algorithm), minimum spanning tree (Prim and Kruskal algorithms). 

    Theory of NP-completeness: complexity classes, NP-complete problems, approximation algorithms

     

    RECOMMENDED READING/BIBLIOGRAPHY

    Lecture notes.

    Introduction to algorithms and data structures. Cormen, Leiserson, Rivest, Stein. McGraw Hill. 

    TEACHERS AND EXAM BOARD

    Exam Board

    ELENA ZUCCA (President)

    PAOLA MAGILLO

    ALESSANDRO VERRI (President Substitute)

    LESSONS

    Class schedule

    All class schedules are posted on the EasyAcademy portal.

    EXAMS

    EXAM DESCRIPTION

    Written and oral exam.

    ASSESSMENT METHODS

    The written exam checks the ability of the student to apply in practice learned notions.

    The oral exam checks the understanding of concepts and the ability to appropriately illustrate learned notions.

     

    Exam schedule

    Date Time Location Type Notes
    17/06/2022 09:00 GENOVA Scritto 7 settembre aula 506
    08/07/2022 09:00 GENOVA Scritto 7 settembre aula 506
    06/09/2022 09:00 GENOVA Scritto 7 settembre aula 506
    18/01/2023 09:00 GENOVA Scritto 7 settembre aula 506
    09/02/2023 09:00 GENOVA Scritto 7 settembre aula 506