ALGORITHMS AND DATA STRUCTURES-1

The course is one of the fundamental courses of the Bachelor's Degree in Informatics and provides an introduction to algorithms, namely the formalization of problems, the identification of computational solutions, and the analysis of such solutions, from the point of view of correctness and efficiency in the use of resources. Furthermore, fundamental data structures and basic techniques for the design and analysis of the algorithms will be presented.

Knowledge and understanding:
- knowledge and understanding of the fundamental algorithms and data structures;
- understanding and evaluation of the complexity of computational problems and the ability to select appropriate methods for modeling and solving them;

Ability to apply knowledge and understanding:
- logical-deductive and problem-solving skills;
- ability to formalize and implement solutions for real problems and identification of appropriate solution patterns.

Evaluation skills
- being able to formulate and argue solutions, also developing a critical approach to the evaluation of alternative solutions.

The student is expected to be familiar with the basic concepts of discrete mathematics and calculus. Moreover, basics of programming skills are required.

Algorithms, computation models and analysis techniques: Informal introduction to algorithms. Computation models. Asymptotic notation. Recurrences.
Fundamental techniques for algorithm design: Divide-and-conquer.
Elementary Data Structures: Arrays.
Sorting: Insertion sort, Merge sort, Quicksort.
Hash Tables.
NP-complete problems: complexity classes P and NP. Polynomial reducibility and NP-completeness. Examples of NP-complete problems.

[CLRS] Introduction to Algorithms, third edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein

[KT] Algorithm Design by Jon Kleinberg and Éva Tardos. Addison-Wesley, 2005

The verification of the knowledge is done through the passing of a written exam. The written exam and the eventual oral exam include both questions on the course topics and exercises. The oral exam is compulsory for those who are almost sufficient (between 15 and 17), optional for those which have a sufficient grade. The written exam (and the eventual oral exam) are required to verify the knowledge of the course contents.
We will also offer two partial exams, one in the middle of the course (depending on the approval of the didactic board) and one after the end of the course, that can be taken only by passing the first part. Passing both parts will allow the student to be exonerated from the global written exam.

written and oral

The verification of the knowledge is done through the passing of a written exam. The oral exam is compulsory for those who are almost sufficient (between 15 and 17), optional for those which have a sufficient grade. The oral exam is worth a maximum of 6 bonus points. If passed positively, the bonus is added to the mark of the written test, forming the final mark (if it is less than 18, the exam is not passed). If, on the other hand, the oral test is evaluated negatively, the bonus is subtracted from the starting mark and the student may not even pass the entire exam. The evaluation of the exam will take into account both the ability to answer the theoretical questions on the exam topics and the ability to carry out the exercises according to a score indicated in each question.
We will also offer two partial exams, one in the middle of the course (depending on the approval of the didactic board) and one after the end of the course, that can be taken only by passing the first part. Passing both parts will allow the student to be exonerated from the global written exam. The final mark will be given by the average of the marks of the two tests.

Course organized in lectures in class, and exercises on paper.

Students have to register on the course Web page of the e-learning platform available at the link moodle.unive.it.
The course will be in English.