CODE 80298 ACADEMIC YEAR 2019/2020 CREDITS 12 cfu anno 1 INFORMATICA 8759 (L-31) - GENOVA SCIENTIFIC DISCIPLINARY SECTOR INF/01 LANGUAGE Italian TEACHING LOCATION GENOVA SEMESTER 2° Semester TEACHING MATERIALS AULAWEB OVERVIEW The course of Algorithms and Data Structures aims at expanding the students' knowledge and skills related to programming in the small with imperative languages; it provides the basis for designing efficient algorithms and for developing data structures that enable effective information organization. AIMS AND CONTENT LEARNING OUTCOMES The course aims at improving knowledge and skills of programming in the small, through imperative languages, providing the basics for designing correct and efficient algorithms, and for developing data structures that enable effective and efficient organization of data. AIMS AND LEARNING OUTCOMES At the end of the course, the student will be able to: - compute the complexity of known algorithms (sorting, adding, searching and modifying elements in a data structure) in order to identify the most efficient one - design the interface of a data type - implement the data type with different data structures that include indexed and linked structures - understand the difference in the efficiency of the functions supported by the data type, when different data structures are employed TEACHING METHODS Traditional, with frontal lessons and laboratory sessions SYLLABUS/CONTENT Methods for algorithm analysis: cost criteria, asymptotic notation, complexity analysis of recursive algorithms. Examples of development and analysis of algorithms. Sorting algorithms: insertion sort, selection sort, bubble sort, mergesort, quicksort Basic data structures: arrays and lists; stacks and queues; dictionaries implemented with lists. Dictionaries: implementation with binary search trees and hash tables. Trees: indexed and linked representations for binary trees and general trees; depth-first search and breadth-first search of trees. Search Trees: Binary search trees, search trees as a data structure for implementing dictionaries, balanced trees. Hash tables: collision lists and open addressing. Priority queues: implementation with lists and heaps. Graphs: definitions, data structures, primitives for querying and updating graphs; graph visits in depth and in width; examples of application of a graph visit algorithms. Laboratory: C++ laboratories related to course topics RECOMMENDED READING/BIBLIOGRAPHY All topics covered by the program are faced during the frontal lessons. The teaching material provided by the teachers via AulaWeb (including the fragments of C++ code implementing the algorithms and data structures addressed during the course) and notes taken during classroom lessons are essential for preparing the exam. TEACHERS AND EXAM BOARD VIVIANA MASCARDI Ricevimento: Appointment by email Office: Valle Puggia – third floor FILIPPO RICCA Ricevimento: Appointment by email NICOLETTA NOCETI Exam Board VIVIANA MASCARDI (President) NICOLETTA NOCETI ENRICO PUPPO FILIPPO RICCA LESSONS Class schedule The timetable for this course is available here: Portale EasyAcademy EXAMS EXAM DESCRIPTION Exam description The exam consists of a written test (3 hours, 14 points maximum, 8 threshold for passing this part) and a laboratory test (3 hours, 14 points maximum, 8 threshold). The two tests are independent of each other: students can book and perform only the written test in one exam session and book and perform the lab test in another session, and vice versa. It is not necessary to pass one of the two tests to be admitted to the other. The written test consists of an initial part that represents a "barrier": if the student does not reach a threshold on the questions in that initial part, the test is non sufficient. The written test can be either passed during the semester through intermediate tests (quizzes and tasks), or in one of the five available appeals. Some of the exercises developed in the labo sessions during the year are evaluated. Students will be informed in advance of the evaluated labos and the evaluation methods. Exercise ratings accredit 5 points maximum. Computation of the final mark The final mark is obtained as the sum of the written mark + the lab mark + the mark of the exercises evaluated during the year. This sum is rounded to the nearest integer. For example, 24.45 becomes 24 and 24.5 becomes 25. The "laude" is given to marks > = 30.5 ASSESSMENT METHODS The various parts of the exam have been carefully designed by the teachers to verify whether the student is able to - compute the complexity of known algorithms (sorting, adding, searching and modifying elements in a data structure) in order to identify the most efficient one - design the interface of a data type - implement the data type with different data structures that include indexed and linked structures - understand the difference in the efficiency of the functions supported by the data type, when different data structures are employed Details on how to prepare for the exam and the degree of understanding of each topic delat with during the course will be given during the lessons. Examples of previous exam texts will be made available to allow students to understand how the acquisition of the required skills is assessed. Exam schedule Data appello Orario Luogo Degree type Note 07/01/2020 09:00 GENOVA Scritto 08/01/2020 09:00 GENOVA Laboratorio 03/06/2020 09:00 GENOVA Scritto 04/06/2020 09:00 GENOVA Laboratorio 25/06/2020 09:00 GENOVA Scritto 26/06/2020 09:00 GENOVA Laboratorio 22/07/2020 09:00 GENOVA Scritto 23/07/2020 09:00 GENOVA Laboratorio 07/09/2020 09:00 GENOVA Scritto 08/09/2020 09:00 GENOVA Laboratorio 12/01/2021 09:00 GENOVA Scritto 13/01/2021 09:00 GENOVA Laboratorio