COMPUTER SCIENCE 2

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.

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.

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.

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