Ateneo - UPO

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 edition
McGraw-Hill, 2010

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 graphs
- solve problems implementing classical graph traversal algorithms
- solve 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 algorithms- be 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.

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 Algorithms and Data Structures 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 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.
In lab the student is guided in implementing the algorithms seen in class, realizing for each algorithm a few variants as a propaedeutic exercise to problem solving.
On the DIR site of the course the students have access to quizzes that serve as practice and self-evaluation. The aim is to offer to the students 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.

Hands-on activity requires active participation of the students, who this way develop prcatical skills (ability to implement a program). Moreover, he 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.

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.

Written exam followed by oral exam (with evaluation of the lab exercises)
The aim of the written exam is to verify that the student has understood the classical algorithms and their usage, and is capable of applying them to problem solving. Two types of skills are required: (i) understanding the classical algorithms presented in class and using them on simple instances; (ii) solving simple problems by implementing (or modifying) one of the classical algorithms presented in class. Usually, a written exam contains 5 questions, among which:
- at least a question involving the application of a standard graph algorithm
- at least a question involving the application of a greedy or dynamic programming algorithm
- at least a question involving the modification of a known algorithm
- at least a theoretical question (with open or closed answers)
A student obtaining a mark >= 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. The evaluation of the lab exercises (mandatory for attending students) can modify the oral mark.

Graphs
-definitions 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 applications
Greedy technique:
-introduction and examples;
-single source shortest paths on a weighted graph: Dijkstra's algorithm and applications
-minimum spanning tree: Prim's and Kruskal's algorithms and their use to solve practical problems;
-techinques for proofs of correctness and their function in designing greedy algorithms;
-limits of greedy techniques (the problem of coin change)
Dynamic 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 algorithm (use in routing algorithms)
-all-pairs shortest paths on a weighted graph: Floyd-Warshall's algorithm
Introduction to intractable problems:
-P, NP complexity classes and NP-completeness
-pseudopolinomial algorithms
-introduction to the techniques to deal with intractable problems.

Define a graph, and analyze the different ways of representing a graph for different applications.
Describe the concept of graph traversal, and identify examples thereof.
Describe the freedy and dynamic programming strategies.
Identify examples for each one of the mentioned strategies.
Describe and explain the reasoning that leads to the design (and proves the correctness) of classical algorithms on graphs.
Describe the complexity/correctness analysis of such algorithms.
Apply classical algorithms to simple instances.
Describe classes P and NP and their relashionship and the idea of approximate solution; explain the analysis of approximate algorithms presented in class.
Model a given problem with a classical problem on a graph, choosing the appropriate kind of graph.
Implement the classical algorithms on graphs studied in class.