Follow us
Search

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 lectures

12 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

To have passed the exam of Informatica 1.

Attendance of Lessons

In order to fully understand the arguments and the techniques illustrated in the course, class attendance is strongly recommended. 

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

 SubjectsText References
1Introduction. Algorithms as a technology for the solution of problems.Chapt.1.1-1.2 of 1)
2Divide-et-imperaChapt. 4.1 of 1) and supplementary didactic material
3RecurrencesChapt. 4.3-4.5 of 1) and supplementary didactic material
4Sorting in linear timeChapt. 8.2 of 1) and supplementary didactic material
5Medians and order statisticsChapt. 9.1 e 9.3 of 1) and supplementary didactic material
6Elements of dynamic programmingChapt. 15 of 1) and supplementary didactic material
7Elementary graph algorithmsChapt. 22 of 1) and supplementary didactic material
8Elements of greedy strategyChapt. 16.1-16.3 of 1) and supplementary didactic material

Learning Assessment

Learning Assessment Procedures

The exam consists of two tests. 

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

Students can find the texts of the exams of past years, regarding the first and the second test on Studium portal, to the link: 

https://studium.unict.it/dokeos/2023/main/document/document.php?cidReq=6408FB46A3563199&curdirpath=/shared_folder&teacher_table_page_nr=2