OVERVIEW

We introduce:
data types, which are the theoretical counterpart of a software module, and consist of values with their operations;
data structures and algorithms to implement a data type (the implementation is not unique);
techniques for evaluating the space and time complexity of an implementation;
object oriented (OO) programming and the Java language.
We use Java to implement some classical data types (stack, queue, dictionary) and algorithms for the sorting problem.

AIMS AND CONTENT

LEARNING OUTCOMES

Introduction to: data types; algorithms, data structures and complexity evaluation; object-oriented programming with the Java language as an example; implementation of data types in Java.

AIMS AND LEARNING OUTCOMES

We introduce the concept of data type (consisting of stored values and operations acting on them); we introduce data structures which describe how to organize stored data in memory and algorith ms which describe the processed used to perform the operations; we introduce examples of data types (stack, queue, dictionary) and their classic implementations, and various classic algorithms for the sorting problem. In parallel, we introduce object oriented programming on the example of the Java language. In this way, we will immediately see the practical application in laboratory of what we see in the lessons.

After attending, the student will be aboe to implement a data type by choosing suitable data structures and algorithms, based a complexity analysis of the various possible implementations. He/she will know classical data types (stack, queue, dictionary) and their implementations. He/she will know classical sorting algorithms and their properties.  Moreover, he/she will know object-oriented programming and how to program in the Java language.

PREREQUISITES

Knowledge of the basic concepts of an imperative programming language: instruction, variable, cycle, function, argument, result, typing of variables.

Knowledge of the basic concepts of mathematics and logics: operation, argument, result, domain, codomain, relations and their properties (reflexive, symmetric, transitive), logical operators (and, or, not, implication).

TEACHING METHODS

Coordinated lessons in classroom and in laboratory (with exercises). Each week has three lessons of two hour each.  In the typical week, one lesson is in classroom, one lesson in laboratory, and one is either in classroom or in laboratory depending on the flow of teaching material.
Part of the laboratory hours will be dedicated to (a couple of) practical exercitations, that will allow the student, who delivers them, to bypass the practical part of the exam (see exam and assessment methods).

SYLLABUS/CONTENT

Abstract data type. From operations to algorithms; from types to data structures. Space and time complexity. Data types: stack, queue, dictionary, and various implementations for them. Sorting algorithms.
Object-oriented programming paradigm and Java language. Classes and objects, equality and copy of objects, constructors, clientship,  inheritance, overriding, exceptions. Implementation of data types in
Java.

RECOMMENDED READING/BIBLIOGRAPHY

Course notes. On-line manual  and tutorials for Java. Book: M.T.Goodrich, R.Tamassia, Data structures and algorithms in Java, John Wiley & Sons.

TEACHERS AND EXAM BOARD

Exam Board

PAOLA MAGILLO (President)

ELENA ZUCCA (President)

DAVIDE ANCONA

LESSONS

LESSONS START

The class will start according to the academic calendar.

Class schedule

PROGRAMMING 2

EXAMS

EXAM DESCRIPTION

The exam consists of a pratical part in laboratory and of an oral part. Students who have delivered the exercitations during the year may not to attend the practical part.

Esercitations remain valid for the entire academic year: the student can give the oral exam in any date and, in case of failure, he keeps his/her
esercitations and has to repeat the oral exam only.
If a student has not or does not want to use the esercitations, them he/she has to give the laboratory exam as well. The laboratory exam is strictly connected with the oral exam: a student who fails the oral exam at a date, has to repeat the laboratory part as well.

ASSESSMENT METHODS

During the year, some practical exercitations will be given, to be done individually. Students who deliver such exercitations may access the
oral exam directly without needing the practical part of the exam.
Such exercitations consist in implementing some data structures and/or algorithms explained in the lessons. Some hours during the normal schedule are dedicated to these exercitations.
The exercitations require to deliver the produced Java code and written documentation; the documentation may need not only to explain, but also
to evaluate the produced implementation. The correctness and the quality of both code and documentation will be evaluated.

The laboratory part of the exam will ask to write, or to modify, Java code to implement variants of algorithms and data structures presented
during the year.

The oral exam will ask questions about the teaching program, and may involve writing examples in code or pseudocode. It may involve a
discussion of the laboratory part of the exam or of the exercitations. The student will be required to show understanding of the concepts and ability to use the analysis and evaluation technique seen in the lessons.

Exam schedule