Ateneo - UPO

Algorithm analysis methods. Basic data structures. Fundamental sorting and search algorithms.

Algoritmi e strutture dati 3/ed, Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano, MC Graw Hill

Providing the definition of the fundamental data structures and being able to adopt them in the proposed exercises.
Being able to analyse recursive and iterative algorithms.
Being able to describe the sorting and search algorithms.
Being able to apply a specific algorithm among them, to a given problem.
Being able to provide its implementation in C.

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.

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. Topics include those presented during classroom lessons and in the lab. 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.

- Introduction to algorithms. - Analysis of algorithms: O, Omega and Theta notations. Master theorem on recurrences. - Abstract data structures: Stack, Queue, Tree. - Sorting algorithms: insertion sort, selection sort, merge sort, quicksort, heap sort, integer sort, radix sort. - Search binary trees. AVL trees, 2-3 trees. - Hash tables. - Priority queues.
These notions will then be further examined by means of their implementation. In particular, the exercises will refer to the following topics:

Sorting algorithms: Insertion sort, Selection sort, Merge sort, Heap sort, Quicksort;
Dynamic data structures: Lists, Queues, Stacks; Trees;
Hash tables.

Knowledge and understanding: knowing the analysis of algorithms and the data structures, focusing on search and sorting algorithms. Applying knowledge and understanding: Capability to apply the analysis techniques in the exercises, capability to write a classical algorithm, or a possible variation of it, proposing novel technically correct solutions.Making judgements: being able to analyze recursive algorithms; being able to afford in a critical way the exercises, proposing correct solutions in an autonomous way.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.