Acquire skills on key solution techniques for combinatorial optimization problems; improve the skills on graph theory; acquire advanced technical skills for designing, analyzing and implementing algorithms aimed to solve optimization problems on graphs, trees and flow networks.
Curriculum
teacher profile teaching materials
2. Basics of algorithm analysis. Computational tractability. Asymptotic order of growth.
3. Graphs. Graph connectivity and graph traversal. Graph bipartiteness. Connectivity in directed graphs. Directed acyclic graphs and topological ordering.
4. Greedy algorithms. Interval scheduling. Optimal caching. Shortest paths in a graph. Minimum spanning trees.
5. Divide and conquer. Mergesort. Counting inversions. Closest pair of points.
6. Dynamic programming. Weighted interval scheduling. Principles of dynamic programming. Subset sums and knapsacks. All-pairs shortest paths. Shortest paths and distance vector protocols.
7. Network flow. Maximum flow and the Ford-Fulkerson algorithm. Maximum flows and minimum cuts in a network. Augmenting paths. Bipartite matching. Disjoint paths in directed and undirected graphs.
8. Computational intractability. Polynomial-time reductions. Reductions via "gadgets". Efficient certification and the definition of NP. NP-complete problems. Covering, packing, partitioning, sequencing, and numerical problems. Other examples.
Mutuazione: 20410626 IN440 - OTTIMIZZAZIONE COMBINATORIA in Scienze Computazionali LM-40 BONIFACI VINCENZO
Programme
1. Optimization and combinatorial optimization problems. Enumeration of solutions.2. Basics of algorithm analysis. Computational tractability. Asymptotic order of growth.
3. Graphs. Graph connectivity and graph traversal. Graph bipartiteness. Connectivity in directed graphs. Directed acyclic graphs and topological ordering.
4. Greedy algorithms. Interval scheduling. Optimal caching. Shortest paths in a graph. Minimum spanning trees.
5. Divide and conquer. Mergesort. Counting inversions. Closest pair of points.
6. Dynamic programming. Weighted interval scheduling. Principles of dynamic programming. Subset sums and knapsacks. All-pairs shortest paths. Shortest paths and distance vector protocols.
7. Network flow. Maximum flow and the Ford-Fulkerson algorithm. Maximum flows and minimum cuts in a network. Augmenting paths. Bipartite matching. Disjoint paths in directed and undirected graphs.
8. Computational intractability. Polynomial-time reductions. Reductions via "gadgets". Efficient certification and the definition of NP. NP-complete problems. Covering, packing, partitioning, sequencing, and numerical problems. Other examples.
Core Documentation
Jon Kleinberg, Eva Tardos. Algorithm Design. Pearson Education, 2013.Type of delivery of the course
Frontal lectures with recitations and lab (algorithms implementation in Python). For the class' diary see the teacher's webpage: http://ricerca.mat.uniroma3.it/users/vbonifaci/in440.html The lectures will be in presence, and at the same time they will be streamed and recorded.Type of evaluation
The oral exam consists of an in-depth examination at the blackboard about at most 4 distinct topics in the syllabus. teacher profile teaching materials
2. Basics of algorithm analysis. Computational tractability. Asymptotic order of growth.
3. Graphs. Graph connectivity and graph traversal. Graph bipartiteness. Connectivity in directed graphs. Directed acyclic graphs and topological ordering.
4. Greedy algorithms. Interval scheduling. Optimal caching. Shortest paths in a graph. Minimum spanning trees.
5. Divide and conquer. Mergesort. Counting inversions. Closest pair of points.
6. Dynamic programming. Weighted interval scheduling. Principles of dynamic programming. Subset sums and knapsacks. All-pairs shortest paths. Shortest paths and distance vector protocols.
7. Network flow. Maximum flow and the Ford-Fulkerson algorithm. Maximum flows and minimum cuts in a network. Augmenting paths. Bipartite matching. Disjoint paths in directed and undirected graphs.
8. Computational intractability. Polynomial-time reductions. Reductions via "gadgets". Efficient certification and the definition of NP. NP-complete problems. Covering, packing, partitioning, sequencing, and numerical problems. Other examples.
Mutuazione: 20410626 IN440 - OTTIMIZZAZIONE COMBINATORIA in Scienze Computazionali LM-40 BONIFACI VINCENZO
Programme
1. Optimization and combinatorial optimization problems. Enumeration of solutions.2. Basics of algorithm analysis. Computational tractability. Asymptotic order of growth.
3. Graphs. Graph connectivity and graph traversal. Graph bipartiteness. Connectivity in directed graphs. Directed acyclic graphs and topological ordering.
4. Greedy algorithms. Interval scheduling. Optimal caching. Shortest paths in a graph. Minimum spanning trees.
5. Divide and conquer. Mergesort. Counting inversions. Closest pair of points.
6. Dynamic programming. Weighted interval scheduling. Principles of dynamic programming. Subset sums and knapsacks. All-pairs shortest paths. Shortest paths and distance vector protocols.
7. Network flow. Maximum flow and the Ford-Fulkerson algorithm. Maximum flows and minimum cuts in a network. Augmenting paths. Bipartite matching. Disjoint paths in directed and undirected graphs.
8. Computational intractability. Polynomial-time reductions. Reductions via "gadgets". Efficient certification and the definition of NP. NP-complete problems. Covering, packing, partitioning, sequencing, and numerical problems. Other examples.
Core Documentation
Jon Kleinberg, Eva Tardos. Algorithm Design. Pearson Education, 2013.Type of delivery of the course
Frontal lectures with recitations and lab (algorithms implementation in Python). For the class' diary see the teacher's webpage: http://ricerca.mat.uniroma3.it/users/vbonifaci/in440.html The lectures will be in presence, and at the same time they will be streamed and recorded.Type of evaluation
The oral exam consists of an in-depth examination at the blackboard about at most 4 distinct topics in the syllabus.