Ateneo - UPO

Algorithm analysis methods. Basic data structures. Fundamental sorting and search algorithms.Greedy and dynamic programming algorithmic techniques, notion of graph and algorithms on graphs

Algoritmi e strutture dati 3/ed, Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano, MC Graw Hillor in alternative, for the module Algorithms 2:P. Crescenzi, G. Gambosi, R. Grossi, G. Rossi Strutture di dati e algoritmi, Seconda edizione, Pearsonor Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein Introduction to Algorithms, third edition McGraw-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 optimization algorithms;sharpening students' abilities in problem solving and evaluation of the complexity of solutions.

Formal prerequisites: Students cannot access final exams unless they have passed and verbalized the exams of Programming 1 and Programming 2.Substantial prerequisites: Fundamentals of programming taught in the first year courses on programming. Programming principles and languages taught in previous semesters courses.

Classroom lessons (possibly in a blended modality) and lessons in 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. Proofs are presented as a tool to analyse the problems and design the algorithms, and as a tool to study in depth the algorithmic techniques, leveraging on analogies among algorithms that use the same techniques. The presentation is completed with discussions on the usage of each algorithm in practice to solve specific kinds of problems. 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.

Hands-on activity requires active participation of the students, who this way develop pracatical skills (ability to implement a program). Moreover, the active involvement leads the students to ask themselves questions (and, as a consequence, often to ask questions to the instructor); this allows a regular monitoring of the way the subject is being understood. Morevoer the questions posed using Wooclap allow a constant monitoring of difficulties.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.
Module Algorithms 1:Theory: Written test, possibly as a quiz. An oral exam is possible. Find all details in the specific part for this module.Lab: Practical examination. The exam consists of two exercises where it is asked to develop two programs in C language. Find all details in the specific part for this module.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.Module Algorithms 2:The exam is oral with a first part in lab. Find all details in the specific part for this module.In alternative, students can chose to take the exam with automatically corrected quizzes in lab. Find all details in the specific part for this module.

Module Algorithms 1:Introduction to algorithms.Analysis of algorithms: asymptotic notation (O, Omega and Theta notations). Master theorem on recurrences.Abstract data types: stack, queue, tree.Sorting algorithms: insertion sort, selection sort, merge sort, quicksort, heap sort, integer sort, radix sortSearch 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:Binary search and Sorting algorithms: Insertion sort, selection sort, merge sort, heap sort, quicksort;Dynamic data structures: lists, queues, stacks;Data structures for search problems: binary search trees, hash tables.Module Algorithms 2:Graphsdefinitions and terminology: undirected and directed graphs, weighted graphs, paths, cycles, connected components and strongly connected components: meaning and usage of each variant to model different situations;representations: adjacency matrices and lists and their impact from the implementation point of view;breadth first and depth first traversals: common characteristics and differences and applicationsGreedy technique:introduction and examples;single source shortest paths on a weighted graph: Dijkstra's algorithm and applicationsminimum spanning tree: Prim's and Kruskal's algorithms and their use to solve practival problems;techinques for proofs of correctness and their function in designing greedy algorithms;limits of greedy techniquesDynamic programming technique:introduction to the dynamic programming technique, optimal substructure property; comparison with greedy and divide et impera techniques;implementation aspects and choices: recursive and iterative algorithms, memoization;usage of the optimal substructure theorems to analyze problems and design synamic programming algorithms; analysis of classical problems (maximal independent set, knapsack, longest common subsequence);single source shortest paths on a weighted graph: Bellman-Ford's algorithmall-pairs shortest paths on a weighted graph: Floyd-Warshall's algorithmIntroduction to intractable problems:P, NP complexity classes and NP-completenesspseudopolinomial algorithmsintroduction to the techniques to deal with intractable problems.

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.