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

Expanding knowledge and skills related to programming in the small through imperative languages, learning to design correct and efficient algorithms, and implementing data structures that support effective and efficient organization of information.

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

At the end of the course, the student who decides to participate in the innovative teaching initiatives proposed by the teachers and possesses the minimum disciplinary requirements to be involved in such innovative activities, will also have acquired the following transversal skills:

- Functional literacy skills - advanced level (communicating effectively in written and oral form, adapting communication to the context, using sources and aids of various kinds, critical thinking, ability to use, process and evaluate information)

- Ability to learn to learn - advanced level (awareness of one's own learning strategies, organization and evaluation of personal learning according to what has been understood and learned, understanding of one's own needs and methods of developing skills, ability to identify and pursue learning objectives)

- Competence in project creation - basic level (ability to develop one's imagination and creativity, critical reflection, strategic thinking, problem solving with particular reference to contexts of innovation and evolving creative processes)

PREREQUISITES

The basic skills that students should already possess to properly face the course contents are those provided by the "Introduction to Programming" course.

TEACHING METHODS

Traditional, with frontal lessons and laboratory sessions

The course includes the development of an optional individual project.

For students who intend to develop the transversal skills illustrated in the training objectives, the teaching methods also include some of the following activities:
- production of short videos on topics already explained during the classes
- production of documentation that explains in written form topics already presented during the classes
- peer review activities
- flipped classroom on a topic for which the teachers have provided documentation before the class takes place
- development of an individual project (mandatory to obtain the corresponding open badge)

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) is essential for preparing the exam.

TEACHERS AND EXAM BOARD

Exam Board

VIVIANA MASCARDI (President)

ARNAUD HENRI PAUL SANGNIER

MAURIZIO LEOTTA (President Substitute)

LESSONS

LESSONS START

According to the calendar approved by the Degree Program Board:  https://corsi.unige.it/en/corsi/11896/studenti-orario 

Class schedule

The timetable for this course is available here: Portale EasyAcademy

EXAMS

EXAM DESCRIPTION

Exam description

The exam consists of a written part and a laboratory part. The two parts 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 part consists of an initial quiz that represents a "barrier", and whose outcome is "passed"/"not passed": if the student does not pass the quiz, the student can face neither the written part, not the laboratory session. The "barrier" quiz can be faced in any of the five available appeals.

An oral discussion can be requested by the teachers, if the results of the written exam or of the laboratory exam are not definitive and clear enough to assess that the student achieved all the learning outcomes.

Guidelines for students with certified Specific Learning Disorders, disabilities, or other special educational needs are available at  https://corsi.unige.it/en/corsi/11896/studenti-disabilita-dsa 

Computation of the final mark

The final mark is obtained as the sum of the written mark + the lab mark + the mark of the individual (optional) project. This sum is rounded to the nearest integer. 

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.

An oral exam may be requested by the teachers to further assess the competencies acquired by the student, in case the results of the written and/or laboratory exams are not enough convincing.

FURTHER INFORMATION

Students with special needs are required to contact the instructors, to devise the most effective way to follow the course, given their constraints and needs.

For further information, please refer to the course’s AulaWeb module or contact the instructors.