Ateneo - UPO

Algorithm analysis methods. Basic data structures. Fundamental sorting and search algorithms. Algorithmic techniques, notion of graph and algorithms on graphs

- Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Algoritmi e strutture dati 2/ed MacGraw-Hill, 2008; ISBN: 978 88 386 64687- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein Introduction to Algorithms, third editionMcGraw-Hill, 2010

The module Algorithms 1 aims at teaching toprovide the definition of the fundamental data structures, being able to adopt them in the proposed exercises;analyse recursive and iterative algorithmsdescribe the sorting and search algorithms, apply a specific algorithm among them, to a given problem, provide its implementation in C.The module Algorithms 2 aims at:presenting graphs, teaching how to model problems with graphs and giving tools to deal with them;teaching the greedy and dynamic programming algorithmic strategies, presenting techniques of approximation of solutions of optimmization algorithms;sharpening students' abilities in problem solving and evaluation of the complexity of solutions.

Having passed the Programming 1 and 2 exams.

Frontal teaching in the classroom (possibly in blended modality) and interactive teaching in the lab.
Classroom lessons will present the fundamental concepts, and will also include example exercises. Different data structures and different algorithms meant to solve problems of the same class will be compared. On the DIR platform the students will find indications about the textbooks and materials, closely related to the topics presented at the lessons; this will help students that do not attend to easily follow the course development. Exercises and example tests will be provided as well.In the lab, the student is guided in the implementation of the algorithms studied in the classroom lessons, realizing some variations. On the DIR platform the students will find slides and additional material referring to the single lab lessons, as a guide also for those who did not attend.

Students with physical disabilities, Learning Disabilities or Special Education Needs can request
specific services and tools via the Staff Sviluppo e Coordinamento Carriere e Servizi alle Studentesse

e agli Studenti, consulting the University webpage: https://www.uniupo.it/en/services/services-
students-physical-or-learning-disabilities

Students with disabilities, learning disabilities or special education needs, once they have contacted
the University Staff, can refer to the tutor in charge of the course to define the examination
modalities, concerning academic aspects.

The final score is based on the knowledge, competences and capabilities proved during the exam, weighing the results consistently with the number of CFUs of each module.
Precisely, the grades are assigned according to the following evaluation grid:
Less than 18: Significant gaps in content, missing answers, or inadequate responses.
18–22: Acceptable preparation, but with significant gaps or topics not adequately studied. Sufficient application skills. Basic use of technical vocabulary.
23-25: Appropriate knowledge with some gaps, fair application skills; articulated presentation and appropriate use of technical language.
26–28: Good knowledge of the content and ability to establish connections between different parts of the syllabus. Solid use of technical language.
29–30 with honors: Complete and thorough preparation, with a clear and coherent view of the topics covered. Precise use of technical language.
First module.Theory: Written test, possibly as a quiz. The test will be composed by typically 4 exercises, focused on different course topics. One exercise will involve complexity analysis, while the others will involve topics among: fundamental data structures, sorting algorithms, searching algorithms by using trees, hash tables, priority queues. The exercises will be devoted to evaluate the theoretical/practical knowledge and the ability of judgement (exercises where the student has to provide a choice or a judgement). The final score will take into account the partial scores of the different exercises. Possibly, the same exam type will be executed orally, or integrated by means of an oral examination. The test allows to get a maximum score of 24/30. Optionally, the student can complete a proof, possibly reaching a score of 30 cum laude (excellence if the proof is correct and complete). Through the proof, the communication skills (vocabulary and clarity in the exposition),and the learning skills (ability to critically motivate the steps) will be evaluated. Those who get a score of 18/30 at least, are immediately admitted to the practical part, which takes place on the same day. Lab: Practical examination. The exam consists of two exercises where it is asked to develop two programs in C language. Each exercise allows to get a score of 15/30. The exam is passed if the student gets at least a score of 18/30 overall, while correctly carrying out both exercises allows you to obtain a score of 30/30. The global score will take into account the final scores obtained in the Theory and Lab examinations, weighting 2/3 for the theory part, consistently with the number of credits. Second module. Written exam followed by oral exam (with evaluation of the lab exercises) Usually, a written exam contains 6 questions. A student obtaining a mark greater or equal to 18 accesses the oral examination. The oral examination consists of the evaluation of the theoretical competencies. The aim of the oral exam is to verify that the student has acquired the formal terminology and analysis capability; it normally consists of three questions (which number may vary depending on the provided answers). The aim is to ascertain that the student has acquired (i) familiarity with the concept of graph in all its variants, (ii) ability to analyze graph traversal algorithms, (iii) ability to analyze greedy and dynamic programming algorithms, (iv) basic sensibility on how to deal with difficult problems. At the end of the oral examination, a mark is given depending (in equal parts) both on the written exam and on the oral one.

Introduction to algorithms. Analysis of algorithms. Sorting algorithms. Search algorithms. Algorithms on graphs. Algorithmic techniques.

Knowledge and understanding: familiarity with the analysis of algorithms and the data structures, focusing on search and sorting algorithms; familiarity with the concepts of graph, graph traversal, greedy techinique, dynamic programming, and with some classical problems on graphs.Applying knowledge and understanding:applying the analysis techniques in the exercises,writing a classical algorithm, or a possible variation of it, proposing novel technically correct solutionsmodelling problems using graphssolving problems implementing classical graph traversal algorithmssolving problems using greedy or dynamic programming techniques, also implementing classical algorithms.As a byproduct, the course develops the students' programming skills (in C and Java, in particular).Making judgements:analyze correctness and cost of recursive algorithmsanalyze correctness and cost of greedy and dynamic programming onesbeing able to afford in a critical way the algorithms and exercises, proposing correct solutions in an autonomous way, distinguishing the different degrees of complexity,realizing that it is the necessary to use advanced techniques (just mentioned in this course) for problems for which polynomial time algorithms are not knownrecognize the ingredients that are common to the strategies for the design of greedy (resp. dynamic programming) algorithms presented in the course.Communication skills: knowing and correctly applying the terminology of the field, justifying the choices and clearly communicating them also to a non expert audience.Learning skills: Being able to proceed in more advanced algorithmic notions studies; the comprehension of algorithmic techniques and of the machanisms of reasoning and analisys thereof will allow the students to understand and learn algorithms for different problems that are based on the algorithmic techinques taught in the course.