ALGORITHM ANALYSIS AND DESIGN

ALGORITHM ANALYSIS AND DESIGN

_
iten
Code
80306
ACADEMIC YEAR
2019/2020
CREDITS
9 credits during the 3nd year of 8759 Computer Science (L-31) GENOVA
SCIENTIFIC DISCIPLINARY SECTOR
INF/01
TEACHING LOCATION
GENOVA (Computer Science)
semester
2° Semester
Teaching materials

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

Ricevimento: On request. In addition, on aulaweb there will be a discussion forum for questions and answer of general interest for all students.

Ricevimento: On request. In addition, on aulaweb there will be a discussion forum for questions and answer of general interest for all students.

Ricevimento: Appointment by email

Exam Board

ELENA ZUCCA (President)

ALESSANDRO VERRI

PAOLA MAGILLO

DAVIDE ANCONA

LESSONS

Teaching methods

Traditional.

ORARI

L'orario di tutti gli insegnamenti è consultabile su EasyAcademy.

Vedi anche:

ALGORITHM ANALYSIS AND DESIGN

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
19/06/2020 09:00 GENOVA Scritto
10/07/2020 09:00 GENOVA Scritto
27/07/2020 09:00 GENOVA Scritto
08/09/2020 09:00 GENOVA Scritto