CODE 80306 ACADEMIC YEAR 2019/2020 CREDITS 6 cfu anno 2 INFORMATICA 8759 (L-31) - GENOVA 9 cfu anno 3 INFORMATICA 8759 (L-31) - GENOVA SCIENTIFIC DISCIPLINARY SECTOR INF/01 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 ELENA ZUCCA Ricevimento: On request. In addition, on aulaweb there will be a discussion forum for questions and answer of general interest for all students. PAOLA MAGILLO Ricevimento: On request. In addition, on aulaweb there will be a discussion forum for questions and answer of general interest for all students. ALESSANDRO VERRI Ricevimento: Appointment by email Exam Board ELENA ZUCCA (President) DAVIDE ANCONA PAOLA MAGILLO ALESSANDRO VERRI LESSONS Class schedule 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 Data appello Orario Luogo Degree type Note 29/01/2020 09:00 GENOVA Scritto 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