Ateneo - UPO

Greedy and dynamic programming algorithmic techniques, notion of graph and algorithms on graphs

C. Demetrescu, I.Finocchi, G.F. Italiano, Algoritmi e Strutture Dati, Seconda Edizione, McGraw-Hillor in alternative:P. Crescenzi, G. Gambosi, R. Grossi, G. Rossi Strutture di dati e algoritmi, Seconda edizione, Pearson or Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein Introduction to Algorithms, third edition McGraw-Hill, 2010

The module's aim is: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.

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, basic algorithmic notions taught in the module Algorithms 1. Programming principles and languages taught in previous semesters courses.

The course is taught in class and in lab.
In class the fundamental notions are presented, along with examples, also with the help of a software for simulation of algorithms. 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 students can find the suggested textbooks and additional material. Moreover, after each lecture, the subject of the lecture is reported on the DIR together with relevant bibliographic references, especially (but not only) for those who couldn't attend the lecture.
In lab the student is guided in impementing the algorithms seen in class, realizing for each algorithm a few variants as a propedeutic exercise to problem solving. On DIR the students can find, for each lab lecture, slides that work as reference and guide for those who attended the class and those who didn't.
During lessons the teacher poses questions using the tool Wooclap in anonymous mode, to verify understanding of the topics and to spur participation.
On the DIR course the students have access to quizzes that serve as practice and selfevaluation for exam exercises. The aim is to offer to the stundents a means to check their own progress and comprehension, so as to discover as early as possible their weaknesses and to be able to ask for explanations to the teacher. Moreover, to the same end, specifications of exam problems proposed in the past are available to the students.
On the DIR course students find links to recordings of lessons, given by the instructor, and divided by argument. Such material is of help to students who cannot attend class but also a complement for everybody.

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 exam consists of four questions: the first one proposes to the student a simple problem that requires implementation of one of the classical algorithms presented in class.; the following three are oral questions. The oral part of the exam takes place on the same day (as far as the number of participating students allows), and its aim is to verify that the student has understood the theory underlying the algorithms that are taught in the courseand the classical algorithms presented in class.Moreover, it will be verified that the student has acquired the formal terminology, that they can explain the reasonings on which design and correctness proofs are based and that they have acquired analytical skills in reference to the course's matter. The number of questions can vary depending on the quality of the answers (with respect to clarity, completeness, precision, formality,...) and on the results of the programming task, since the final aim is to ascertain that the formative objectives have been reached.To achieve a passing score, it is necessary to show the ability to use the technical terminology, the knowledge of definitions, pseudocodes of algorithms and their complexity, and to present at least one proof of correctness.Excellence is reached showing ability to illustrate and explain the reasoning behind the design of the algorithms presented in the course, problem solving competence, ability to express all of this with the appropriate technical language and to present the topics clearly.In alternative, students can chose to take the exam with two autmatically corrected quizzes in lab, for a total of 20 questions. The first quiz (10 questions) ascertains knowledge of theroretical concepts, the second (10 questions) tests knowledge of the way the algorithms work.A passing score is achieved answering correctly to 70% of all of the questions. The maximum that can be achieved is 22/30, and it is achieved with at least 90% of correct answers. Students must express their preference for one or the other way to take the exam as they enrol for the exam.

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 concepts of graph, graph traversal, greedy techinique, dynamic programming, and with some classical problems on graphs. Applying knowledge and understanding:model problems using graphssolve problems implementing classical graph traversal algorithmssolve problems using greedy or dynamic programming techniques, also implementing classical algorithms.As a byproduct, the course develops the students' programming skills (in Java, in particular). Making judgements:analyze correctness and cost of greedy and dynamic programming algorithmsbe able to critically view the algorithms taught in the course, distinguishing the different degrees of complexity, and realizing that it is the necessary to use advanced techniques (just mentioned in this course) for problems for which polynomial time algorithms are not known recognize the ingredients common to the strategies for the design of greedy (resp. dynamic programming) algorithms presented in the course. Communication skills: the student must have acquired and must be able to use the specific formal terminology of the mentioned fields Learning skills: 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.