Ateneo - UPO

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

Algoritmi e strutture dati 2/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.

Classroom lessons (possibly in a blended modality) for about 2/3 of the hours, and assisted exercises in the lab for about 1/3 of the hours.
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.

Theory: Written test, possibly as a quiz. The test will be composed by three exercises at least, focused on different course topics. One exercise will involve complexity analysis, while the other two will involve two topics among: fundamental data structures, sorting algorithms, searching algorithms by using trees, hash tables, priority queues. The final score will take into account the partial scores of the different exercises. Possibly (e.g., on student's request), the same exam type will be executed orally, or integrated by means of an oral examination.

Lab: Practical examination. The exam consists in developing one or more programs in C language. Topics include those presented during classroom lessons and in the lab. The final score will take into account the partial scores of the different exercises.

The global score will take into account the final scores obtained in the Theory and Lab examinations.

- 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.