PROGRAMMAZIONE E LABORATORIO
– Two written tests, scheduled at the end of each semester;
– The solution (code) of the laboratory assignments;
– Oral discussion.
The exams are mainly focused on the student’s ability to understand small-scale programs and to design and organize algorithmic solutions to simple problems.
The approach is functional-first (IEEE-CS/ACM Computing Curricula 2001); the course is organized around the main forms of abstraction which are exploited to deal with problem complexity: procedural abstraction, data abstraction, and abstraction of state.
At the end of the course the student should have acquired the basic knowledge and skills to design, organize and write small-scale programs, developed according to the functional, imperative and object-oriented paradigms; moreover, he/she should be able to analyze the logic of a program to verify its correctness with respect to its formal specifications.
The laboratory sessions are about design, development and experimentation of small-scale programs; they are meant to stimulate students’ organization skills as well as their ability to work autonomously.
1.1. Knowledge and understanding
– Basic knowledge of functional and imperative programming;
– First rudiments of of object-oriented programming;
– Basic knowledge of the syntax and semantics of the main program and data structures in Scheme and Java;
– Knowledge of the relationships between recursion and iteration;
– Knowledge of the relationships between the concepts of class and object.
1.2 Applying knowledge and understanding
– Being able to code simple recursive and imperative algorithms;
– Being able to analyze the logic of a simple recursive or imperative program in order to verify its correctness with respect to the given specifications and to estimate its performances;
– Being able to apply the memoization and dynamic programming techniques to improve the performances of recursive programs;
– Being able to implement a class with a given interface.
2.1 Making judgements
– Being able to analyze problems in order to identify what can be achieved by a program, to formalize appropriate specifications and to choose appropriate programming tools;
– Being able to understand information-processing processes.
2.2 Communication skills.
– Being able to work together with peers in order to design or improve the algorithmic solution of a problem.
2.3 Learning skills
– Being able to plan experiments on a program to test its correctness and to estimate its performances;
– Being able to learn autonomously new programming languages.
Part I – Procedural abstraction (Scheme) Numerical and non-numerical expressions. Functional approach: procedural abstraction. Binary (if) and multiple-choice (cond) constructs. Numerical, boolean, character and string values. Recursive procedures. Well-founded recursive definitions. Evaluation model via substitution and reduction. Let construct. General and tail recursion. Correctness of recursive programs: proof by induction. Tree recursion and computational complexity. Higher order procedures.
Part II – Data abstraction (Java) Simple data abstractions. Basic data structures: “functional” lists and procedures on lists. Different implementations of abstract data types. Data structures from the user’s (protocol) vs. the implementor’s viewpoint (behavior). Examples of data abstraction.
Part III – Abstraction of state (Java) Concept of state and imperative paradigm. Basic statements and constructs of the Java language. Arrays and array operations. Data structures and imperative approach. Memoization and dynamic programming. Functional vs. imperative approach. State abstraction: concepts of class and object; object interface and encapsulation; constructors and methods. Examples of state abstraction. Recursion and iteration: stack-based transformation of a recursive program into an iterative program. Verification of correctness: Assertions, loop invariants and termination functions.
TESTI DI RIFERIMENTO
Max Hailperin, Barbara Kaiser & Karl Knight, Concrete Abstractions: An Introduction to Computer Science Using Scheme, Brooks/Cole Publishing, 1999 (ISBN: 0534952119), http://gustavus.edu/+max/concrete-abstractions-pdfs/index.htm
Imperative and object-oriented programming:
Robert Sedgewick & Kevin Wayne, Computer Science: An Interdisciplinary Approach, Addison-Wesley, 2016 (ISBN: 9780134076454)