Information updated until 30/06/2026 CODE 80306 ACADEMIC YEAR 2026/2027 CREDITS 6 cfu anno 2 INFORMATICA 11896 (L-31 R) - GENOVA SCIENTIFIC DISCIPLINARY SECTOR INF/01 LANGUAGE Italian TEACHING LOCATION GENOVA SEMESTER 2° Semester PREREQUISITES Propedeuticità in ingresso Per sostenere l'esame di questo insegnamento è necessario aver sostenuto i seguenti esami: Computer Science 8759 (coorte 2025/2026) ALGORITHMS AND DATA STRUCTURES 80298 2025 Computer Science 11896 (coorte 2025/2026) ALGORITHMS AND DATA STRUCTURES 80298 2025 OVERVIEW The first part illustrates how to analyze algorithms from the perspective of correctness and efficiency and presents some classic algorithms for computer science training, drawing on the basic concepts of complexity and elementary data structures from the Algorithms and Data Structures course. The second part illustrates how to apply fundamental notions of probability theory to the analysis of randomized algorithms and how to evaluate the benefits of randomization in algorithm design. AIMS AND CONTENT LEARNING OUTCOMES Learning classical algorithms and algorithmic patterns by analyzing their correctness and efficiency. Appreciating the potential of randomization in algorithm design through simple examples AIMS AND LEARNING OUTCOMES At the end of the course the student will be able to: Know classical algorithms and algorithmic schemes. Analyze correctness and efficiency of an algorithm. Appreciate the potential of randomization in algorithm design through simple examples. PREREQUISITES Basic knowledge of algorithms and data structures. TEACHING METHODS Traditional. SYLLABUS/CONTENT Part One: Complexity of Algorithms and Problems. Induction Principle, Correctness, and Complexity of Recursive Algorithms. Correctness of Iterative Algorithms with Loop Invariant. Dynamic Programming Techniques and Greedy Techniques. Graph Algorithms: Visits, Topological Sorting, Strongly Connected Components, Minimum Spanning Trees, Shortest Paths. Introduction to NP-Completeness Part Two: Randomized Las Vegas and Monte Carlo Algorithms: Sorting Algorithms, Minimum Cut, Game Tree, Byzantine Fault Tolerance, Primality Tests, and Linear Programming. Introduction to Game Theory and Occupancy Problems. RECOMMENDED READING/BIBLIOGRAPHY Lecture notes. Introduction to algorithms and data structures (Third edition). Cormen, Leiserson, Rivest, Stein. McGraw Hill. TEACHERS AND EXAM BOARD ALESSANDRO VERRI Ricevimento: Appointment by email ENRICO PUPPO Ricevimento: Appointment by email: enrico.puppo@unige.it During class period appointments for groups can be set by posting on the course forum on AulaWeb. LESSONS LESSONS START According to the calendar approved by the Degree Program Board: https://corsi.unige.it/en/corsi/8759/studenti-orario Class schedule The timetable for this course is available here: Portale EasyAcademy EXAMS EXAM DESCRIPTION Written and oral exam. Guidelines for students with certified Specific Learning Disorders, disabilities, or other special educational needs are available at https://corsi.unige.it/en/corsi/8759/studenti-disabilita-dsa 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. FURTHER INFORMATION For further information, please refer to the course’s AulaWeb module or contact the instructor.
