INFORMATICS II
Academic Year 2022/2023 - Teacher: MARIANNA NICOLOSI ASMUNDOExpected 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
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.
Examples of frequently asked questions and / or exercises