# ALGORITHMS AND DATA STRUCTURES

iten
Code
80298
2017/2018
CREDITS
12 credits during the 1st year of 8759 Computer Science (L-31) GENOVA
SCIENTIFIC DISCIPLINARY SECTOR
INF/01
LANGUAGE
Italian
TEACHING LOCATION
GENOVA (Computer Science)
semester
2° Semester
Teaching materials

## 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

To improve 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.

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

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

Office hours: Appointment by email

Office hours: Appointment by email

Office hours: Appointment by email

Exam Board

VIVIANA MASCARDI (President)

PAOLA MAGILLO

ENRICO PUPPO

FILIPPO RICCA

## LESSONS

TEACHING METHODS

Traditional, with frontal lessons and laboratory sessions

## EXAMS

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.

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.

ASSESSMENT METHODS

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

Exam schedule

Date Time Location Type Notes
08/01/2018 09:00 GENOVA Scritto
09/01/2018 09:00 GENOVA Laboratorio
06/06/2018 09:00 GENOVA Scritto
07/06/2018 09:00 GENOVA Laboratorio
28/06/2018 09:00 GENOVA Scritto
29/06/2018 09:00 GENOVA Laboratorio
17/07/2018 09:00 GENOVA Scritto
18/07/2018 09:00 GENOVA Laboratorio
10/09/2018 09:00 GENOVA Scritto
12/09/2018 09:00 GENOVA Laboratorio
07/01/2019 09:00 GENOVA Scritto
08/01/2019 09:00 GENOVA Laboratorio