# INFORMATICS II

**Academic Year 2023/2024**- Teacher:

**MARIANNA NICOLOSI ASMUNDO**

## Expected Learning Outcomes

The course introduces the principal design methodologies (incremental, recursion, dynamic programming, greedy algorithms), the techniques for their complexity analysis, both in the worst and average cases and the tools for their implementation. The Python programming language will be used as the main tool to present the implementations of data structures and algorithms.

*Knowledge and understanding*: students will acquire knowledge concerning the principal methods for the design of efficient algorithms (incremental, recursion, dynamic programming, greedy algorithms), the techniques for their computational analysis, both in the worst and in the average cases and for their implementation.

*Applying knowledge and understanding*: students will be able to solve problems of low difficulty, requiring the design and analysis of elementary algorithmic solutions and to implement such algorithmic solutions.

*Making judgements*: students will acquire the ability of judging the quality of an algorithmic solution in terms of efficiency and reuse and the effectiveness of its implementation.

*Communication skills*: students will acquire the necessary communication ability and expressive skill in communicating problems concerning the algorithmic studies, also to non-expert interlocutors.

*Learning skills*: students will have the ability to use the knowledge acquired also in new ambits and to improve his/her knowledge through the consultation of specialist sources in the algorithmic field.

## Course Structure

Teaching organization

total study 150 hours

103 hours of individual study

35 hours of frontal lectures12 hours of exercises

The course is articulated in frontal lectures in which the algorithms in programme are explained, also through examples, and in laboratory lectures in which the considered algorithms are implemented.

*Should teaching be carried out in mixed mode or remotely, it may be necessary to introduce changes with respect to previous statements, in line with the programme planned and outlined in the syllabus.*

## Required Prerequisites

## Attendance of Lessons

## Detailed Course Content

The course introduces the principal design methodologies (incremental, recursion, dynamic programming, greedy algorithms), the techniques for their complexity analysis, both in the worst and average cases and the tools for their implementation. The Python programming language will be used as the main tool to present the implementations of data structures and algorithms.

**DETAILED SYLLABUS**

**Introduction**

Algorithms as technology to solve computational problems. Incremental methodology. Divide-and-Conquer methodology.

Asymptotic notations and relationships among them. Standard notations and common functions.

**Recurrences**

The substitution method. The iterative method and the recursion tree. The master theorem

**Sorting and order statistics **Sorting in linear time. Medians and order statistics.

**Elements of dynamic programming**

Optimal substructure, overlapping subproblems, reconstructing an optimal solution. Some case studies: matrix-chain multiplication, longest common subsequence, editing distance.

**Elementary graph algorithms**

Breadth-first search. Depth-first search (edges classification). Topological sorting. Strongly connected components

**Elements of the greedy strategy**

Greedy-choice property, optimal substructure. Some case studies: the activity-selection problem, Huffman codes.

## Textbook Information

1) T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to algorithms (Third Edition), The MIT Press, Cambridge - Massachusetts, 2009

## Course Planning

Subjects | Text References | |
---|---|---|

1 | Introduction. Algorithms as a technology for the solution of problems. | Chapt.1.1-1.2 of 1) |

2 | Divide-et-impera | Chapt. 4.1 of 1) and supplementary didactic material |

3 | Recurrences | Chapt. 4.3-4.5 of 1) and supplementary didactic material |

4 | Sorting in linear time | Chapt. 8.2 of 1) and supplementary didactic material |

5 | Medians and order statistics | Chapt. 9.1 e 9.3 of 1) and supplementary didactic material |

6 | Elements of dynamic programming | Chapt. 15 of 1) and supplementary didactic material |

7 | Elementary graph algorithms | Chapt. 22 of 1) and supplementary didactic material |

8 | Elements of greedy strategy | Chapt. 16.1-16.3 of 1) and supplementary didactic material |

## Learning Assessment

### Learning Assessment Procedures

The first test is a written exam on the theoretical arguments treated in the course.

The second test consists in the implementation, in Python, of an algorithm studied in class.

The verbalization will be preceded by a brief discussion on the results of the two tests and, in dubious cases, by a short oral test.

Verification of learning can be carried out also in a telematic way, in case the situation would require it.

Final grades will be assigned taking into account the following criteria:

__Rejected:__ Basic knowledges have not been acquired. The student is not able to solve simple exercises and implement simple Python programs.

__18-23__: Basic knowledges have been acquired. The student solves simple exercises and has a moderate ability of implementing simple Python programs.

__24-27: __All the knowledges have been acquired. The student solves all the proposed exercises and implements the requested program making few errors.

__28-30 cum laude__: All the knowledges have been completely acquired. The student applies knowledge and has excellect communication skills, learning skills and making judgements.

### Examples of frequently asked questions and / or exercises