Ateneo - UPO

Algorithmic techniques, the concept of a graph, and graph algorithms, with an introduction to computationally hard problems and to approximation techniques.

- Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano, *Algoritmi e strutture dati*, McGraw-Hill (both the 2nd edition, 2008, ISBN 978 88 386 64687, and the more recent 3rd edition may be used).
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, *Introduction to Algorithms*, third edition, McGraw-Hill, 2010 (also available in Italian).

The course (6 ECTS credits: approximately 32 hours of lecture-based teaching, approximately 16 hours of interactive teaching split between computer lab sessions and exercise sessions, plus a workload of independent study proportional to the credits as set out in the University's Teaching Regulations) pursues the following objectives.

Knowledge and understanding: students will become familiar with the concept of a graph and its representations, with graph traversal techniques, with the greedy technique and with the dynamic programming technique, with a number of classical graph problems solved using these techniques, and with the basic concepts of computational tractability (classes P and NP) and of approximation and local search techniques for tackling hard problems.

Applying knowledge and understanding: students will be able to model a problem using a graph, choosing the most suitable representation; to solve problems by implementing classical graph traversal algorithms; to solve problems using greedy and dynamic programming techniques, including by implementing classical algorithms; to recognize a computationally hard problem and set up an approximate or local-search-based solution for it. As a side effect, the course also develops programming skills, in particular in the Java language.

Making judgements: students will be able to analyse the correctness and computational cost of greedy and dynamic programming algorithms; to critically assess the algorithms presented, distinguishing their different degrees of difficulty and appreciating the need to resort to advanced techniques for problems for which no polynomial algorithms are known; to recognize the common ingredients of the design strategies for greedy or dynamic programming algorithms for the problems studied.

Communication skills: students will have acquired, and will be able to use, the specific formal terminology of the areas covered, including for the oral discussion of proposed solutions.

Learning skills: understanding the algorithmic techniques and the associated reasoning and analysis mechanisms will put students in a position to understand and independently learn algorithms for problems other than those seen in class, provided they can be traced back to the algorithmic techniques presented.

Formal prerequisites: students may not sit the examination unless they have already passed and had recorded the Programming 1 and Programming 2 exams.

Substantive prerequisites: programming concepts taught in the Programming 1 and Programming 2 courses; basic algorithmic concepts taught in the first part of the Algorithms course; programming principles and languages taught in courses from previous semesters.

The course is taught in the classroom and in the computer lab.

In classroom lectures, the fundamental concepts are presented, together with examples. Proofs are presented as a tool for deepening understanding of the techniques, drawing on the analogy between algorithms that use the same technique. The practical usefulness of the different algorithms for solving specific types of problems is discussed.

In the computer lab, students are guided through the implementation of the algorithms seen in class, producing several variants of each algorithm so as to appreciate the insights that can be drawn from using each one.

Exercise and self-assessment quizzes are available on the course's Moodle platform (including practice exercises similar to those of the written examination), giving students a way to test themselves against the topics presented, so that they can identify any gaps or doubts in good time and turn to the instructor for clarification.

Direct interaction with the instructor during lectures, lab sessions and office hours, together with the oral discussion held during the examination, also contributes to developing the communication skills included among the intended learning outcomes.

Lab activities require active, individual participation by students, who thereby develop practical skills (the ability to write a program). Active involvement also prompts students to raise questions (and, as a result, often to ask the instructor); this provides a regular check on how the topics are being understood.

Students with disabilities, Specific Learning Disorders (SLD/DSA) or Special Educational Needs (BES) may request services and tools specifically dedicated to them by contacting the University's Career Development and Coordination Staff and Student Services, and by consulting the dedicated page on the University website: https://uniupo.it/it/servizi/servizi-studenti-disabili-e-dsa

Students with disabilities, SLD/DSA or BES, once they have contacted the University Staff, may contact the instructor responsible for the course regarding how the examination arrangements are adapted, with respect to teaching-related aspects.

The examination takes place in a single day per exam session: in the first part of the morning, students sit the written examination at a computer, on the Moodle platform, which grades it automatically; those who achieve a passing grade in the written examination sit the oral examination on the same day.

The written examination is intended to verify that students have understood the classical algorithms and their use, and are able to apply them to solve problems. It consists of:
- 3 practical exercises (carrying out or modifying an algorithm seen in class, or writing code), worth a total of 26 points shared almost equally among the three exercises;
- 3 closed-answer theoretical questions (multiple choice, with 3 possible answers each), worth a total of 6 points: 2 points for a correct answer, -1 point for a wrong answer, 0 points for no answer (a penalty calibrated so that the expected value of a random guess is zero).

The maximum score for the written examination is 32/30 (30 cum laude); the examination is considered passed with a score of 18/30 or higher, a threshold that grants access to the oral examination on the same day. The written examination lasts about an hour and a half.

The oral examination assesses theoretical competencies: in particular, familiarity with the concept of a graph in its various forms, the ability to analyse graph traversal algorithms, greedy algorithms and dynamic programming algorithms, and an awareness of how to approach computationally hard problems (classes P/NP, approximation, local search). Three questions are asked, covering the entire course syllabus, including proofs and the explanation/discussion of topics covered in class; it lasts about 20 minutes per student. The oral examination is also graded out of thirty, with a maximum score of 32/30.

The final grade is determined by approximately 50% from the written examination grade and approximately 50% from the oral examination grade, without prejudice to the instructor's ability to apply reasoned adjustments in specific cases. A modifier linked to the completion of the lab exercises (mandatory for attending students) is also added to the oral examination grade, and can range from -2 to +2 points depending on the quality of the work done.

The material best suited to preparing for the written examination consists of the practice exercises available on the course's Moodle platform; the material best suited to preparing for the oral examination consists of the reference textbooks and the theoretical material available on the same platform.

**Graphs**
- definitions and terminology: undirected graphs, directed graphs, weighted edges, paths, cycles, connected and strongly connected components: meaning and use of the different variants to model different situations;
- graph representations (edge lists, adjacency lists, incidence lists, adjacency matrices and incidence matrices) and their impact from an implementation standpoint;
- breadth-first and depth-first graph traversal: common features and differences between the various traversals presented, and their applications for computing connected components, strongly connected components, topological ordering and cycle testing.

**Greedy technique**
- introduction to the technique through the fractional knapsack problem example; correctness-proof techniques (optimal-substructure and greedy-choice properties) and their role in designing greedy algorithms; Huffman's algorithm for optimal coding;
- shortest paths on a weighted graph from a single source: Dijkstra's algorithm and its applications;
- minimum spanning tree: the cut lemma, Prim's and Kruskal's algorithms and their use in solving practical problems;
- the Union-Find data structure (quick find, quick union, balancing and path-compression heuristics, amortized analysis) and its use in Kruskal's algorithm;
- limits of the greedy technique (the coin-change problem).

**Dynamic programming technique**
- introduction to the technique and the optimal-substructure property; comparison with the greedy technique and with divide-and-conquer; implementation aspects and choices (recursive and iterative algorithms, memoization);
- use of optimal-substructure theorems for problem analysis and the design of dynamic programming algorithms; analysis of classical problems (maximum independent set, 0-1 knapsack, longest common subsequence);
- shortest paths from a single source: the Bellman-Ford algorithm (used in routing algorithms);
- shortest paths between all pairs of nodes: the Floyd-Warshall algorithm.

**Intractable problems and approximation techniques**
- complexity classes P and NP, NP-completeness; pseudo-polynomial-time algorithms;
- techniques for tackling computationally hard problems: approximation algorithms (using the minimum vertex cover problem as an example) and local search (using the travelling salesman problem, TSP, as an example).

**Knowledge and understanding**
- State the definition of a graph and describe its various representations, analysing their advantages and disadvantages in relation to their applications.
- Describe the concept of graph traversal (breadth-first and depth-first) and identify its applications (connected components, strongly connected components, topological ordering, cycle testing).
- Describe the greedy technique and the dynamic programming technique, identifying examples of algorithms that use them (Dijkstra, Prim, Kruskal, Huffman; Bellman-Ford, Floyd-Warshall, 0-1 knapsack, LCS).
- Describe the complexity classes P and NP and the concept of NP-completeness, and illustrate the idea underlying approximation and local search techniques.

**Applying knowledge and understanding**
- Model a given problem as a classical graph problem, choosing the most appropriate type of graph and representation.
- Apply the classical algorithms presented in class to simple instances, including by modifying them to solve variants of the problems addressed.
- Implement in Java the classical graph algorithms presented in class.

**Making judgements**
- Explain the reasoning that leads to the design of, and proves the correctness of, the classical algorithms presented, and analyse their computational complexity.
- Recognize whether a given problem can be reduced to a known problem and choose the most appropriate algorithmic technique to address it.

**Communication skills**
- Present clearly, and with correct formal terminology, the definition of a problem, the proposed solving algorithm, and the related correctness proof.

**Learning skills**
- Independently extend the algorithmic techniques presented to problems not explicitly covered in class, recognizing their common structure.

To achieve a passing grade, the above is required as applied to simple, well-structured instances; an excellent grade requires full autonomy in tackling variants of the problems covered and in the critical, formal presentation of results.