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.
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.Reference Bibliography
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. McGraw-Hill, 3rd edition, 2009. Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani. Algorithms. McGraw-Hill, 2016. Bernhard Korte, Jens Vygen. Combinatorial Optimization. Springer, 4th edition, 2008. Michael R. Garey, David S. Johnson. Computers and Intractability. Freeman, 1979.Type of delivery of the course
Frontal lectures with recitations and lab. For the class' diary see the teacher's webpage: http://ricerca.mat.uniroma3.it/users/vbonifaci/in440.htmlType of evaluation
Oral exam. 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.Reference Bibliography
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. McGraw-Hill, 3rd edition, 2009. Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani. Algorithms. McGraw-Hill, 2016. Bernhard Korte, Jens Vygen. Combinatorial Optimization. Springer, 4th edition, 2008. Michael R. Garey, David S. Johnson. Computers and Intractability. Freeman, 1979.Type of delivery of the course
Frontal lectures with recitations and lab. For the class' diary see the teacher's webpage: http://ricerca.mat.uniroma3.it/users/vbonifaci/in440.htmlType of evaluation
Oral exam. 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.
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.Reference Bibliography
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. McGraw-Hill, 3rd edition, 2009. Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani. Algorithms. McGraw-Hill, 2016. Bernhard Korte, Jens Vygen. Combinatorial Optimization. Springer, 4th edition, 2008. Michael R. Garey, David S. Johnson. Computers and Intractability. Freeman, 1979.Type of delivery of the course
Frontal lectures with recitations and lab. For the class' diary see the teacher's webpage: http://ricerca.mat.uniroma3.it/users/vbonifaci/in440.htmlType of evaluation
Oral exam.