Ateneo - UPO

Algorithmic techniques, notion of graph and algorithms on graphs

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

The course'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;
-sharpen 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 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 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.
On the DIR course a question and answer forum offers the students a virtual room for discussing and reasoning on course subjects; after each lesson the instructor proposes a few questions to help understand in depth what has just been presented in class. The instructor monitors answers and participates just to offer a minimal guide, leaving the discussion to the students.
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.

Programming task followed by oral exam
For the programming task, the student is proposed a simple problem that requires implementation of one of the classical algorithms presented in class. This part is followed on the same day (as far as the number of participating students allows), by an oral exam whose aim is to verify that the student has understood the theory underlying the algorithms that are taught in the course
and the classical algorithms presented in class.
Moreover, it will be verified that the student has acquired the formal terminology, that he/she can explain the reasonings on which design and correctness proofs are based and that he/she has 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.
The final evaluation takes into account the quality of both the implementation and of the interview.

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 practival problems;
-techinques for proofs of correctness and their function in designing greedy algorithms;
-limits of greedy techniques
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
-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.

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.