Course Details for A.Y. 2016/2017

Course Objectives

This module invites students to study and implement the most important algorithms and data structures for information processing. The module focuses on techniques for the design and analysis of efficient algorithms, emphasizing methods useful in practice. Topics include lists, stacks, queues, trees, heaps and priority queues, binary search trees (including red-black), union-find for disjoint sets and graphs (including both array-based and linked representations) and evaluation of classic algorithms that use these structures for tasks such as sorting and searching. The module encourages students to develop implementations using the Java language, understand their performance characteristics, and estimate their potential effectiveness in applications using lectures and exercises.

Course Content

• Java review. Interfaces and abstract classes. Generics. The Java Collection Framework Interfaces and classes.
• Elementary data structures and their implementation in Java: lists, stacks and queues. Array and singly linked list implementations of lists, stacks and queues. Use of the standard classes from a client code perspective.
• Searching and sorting algorithms and their implementation in Java: sequential and binary search; bubble-sort, insertion-sort, selection-sort, merge-sort, quick-sort.
• Advanced data structures and their implementation in Java: binary trees, breadth-first search and depth-first search; binary search trees (BST), balanced BST, red-black trees; disjoint sets.
• Priority queues and their implementation in Java: binary heaps and use of a heap to implement a priority queue; use of a priority queue to develop a sorting method. Java implementation of heap-sort.
• Graphs: representations for both directed/undirected and weighted/unweighted models; Java implementation of breadth-first search and depth-first search; Java implementation of classical graph algorithms for solving the single-source shortest path problem and the minimum spanning tree problem.

Learning Outcomes (Dublin Descriptors)

On successful completion of this course, the student should

Prerequisites and Learning Activities

A basic understanding of programming in Java and a background in discrete mathematics are necessary prerequisites to this module.

Assessment Methods and Criteria

Pre-Assessment: There is no formal pre-assessment, but Course pre-requisites are clearly stated on the Module website. Formative Assessment: The formative assessment is performed via interaction between teacher and students during lectures. Students are involved in questioning and discussion, by means of open oral questions to the entire class. Summative Assessment: Written test followed by an optional oral exam. The oral exam can be required either by the student, to improve grades, or by the teacher, in presence of significant mistakes/misunderstandings in the written exam. The oral exam will occur within the same exam session of the written test and will typically cover the areas of the written answers that need clarification plus, possibly, additional subjects proposed by the teacher. An optional mid-term written test will also be provided, which is meant to cover the first part of the course, in order to help the students to split the workload. The written exam consists of a set of exercises to assess: (i) whether the student knows, can motivate and can compare the concepts, the implementation and the time and memory requirements of the data structures and algorithms; (ii) a student's general knowledge and understanding on the module material; (iii) a student's practical skills in selecting and applying suitable data structures and algorithms in software development and general problem solving. This involves writing program code with pen and paper. Criteria of evaluation will be the level of knowledge and understanding, and practical ability. The final marks of the Algorithms and Data Structures with Laboratory 12 CFU Course are roughly obtained as the average among the marks of the Algorithms and Data Structures and the Laboratory of Algorithms and Data Structures 6 CFU Modules.

Textbooks

• William J. Collins, Algoritmi e strutture dati in Java , Ed. Maggioli, Apogeo Education.    
• C. Demetrescu, U. Petrillo, I. Finocchi, G. Italiano, Progetto di Algoritmi e Strutture Dati in Java , McGraw-Hill.    

Notes

• Gli studenti immatricolati fino all'A.A. 2012/2013 che hanno nel proprio piano di studi l'insegnamento propedeutico di Laboratorio di Programmazione II potranno optare per la prova scritta di Laboratorio in Java, anziché C, previa comunicazione alla docente. Gli altri sono invitati a contattare la docente per discutere del programma d'esame in base al proprio curriculum.

Internet Resources

Course page updates

• A.Y. 2010/2011
• A.Y. 2011/2012
• A.Y. 2012/2013
• A.Y. 2013/2014
• A.Y. 2014/2015
• A.Y. 2015/2016
• A.Y. 2016/2017
• A.Y. 2017/2018
• A.Y. 2018/2019