20874 - ALGORITHMS FOR OPTIMIZATION AND INFERENCE
Department of Computing Sciences
LAURA SANITA'
Mission & Content Summary
MISSION
CONTENT SUMMARY
Basic Notions and Algorithmic Background
Algorithmic efficiency
Complexity classes and reductions
Fundamental graph optimization problems
Mathematical Optimization techniques
Linear Programming duality and sensitivity analysis
Stochastic and Robust Optimization
Integer Programming and Large-scale optimization
Non-linear Programming models and algorithms
Inference and Learning
Clustering and k-means problems
Multiplicative weights method
Mathematics of Neural Networks
Submodular optimization and its applications in ML and AI
Intended Learning Outcomes (ILO)
KNOWLEDGE AND UNDERSTANDING
- Understand the concept of algorithmic efficiency
- Recognize fundamental optimization problems and distinguish their computational complexity classification
- Be familiar with mathematical programming theory and algorithms
- Deal with stochastic, robust, and large-scale aspects of optimization problems
- Understand the mathematics behind popular inference algorithms
APPLYING KNOWLEDGE AND UNDERSTANDING
- Analyze efficiency algorithms
- Estimate the computational and resource requirements of algorithms
- Classify optimization problems according to their computational complexity
- Formulate optimization problems as Linear/Integer/Non-linear programming models
- Solve stochastic, robust, and large-scale optimization problems using the appropriate techniques
- Apply inference algorithms
Teaching methods
- Lectures
- Practical Exercises
- Individual works / Assignments
DETAILS
The teaching method is face-to-face lectures. Several lectures will include exercises to be done in class.
Assessment methods
Continuous assessment | Partial exams | General exam | |
---|---|---|---|
|
x | ||
|
x |
ATTENDING AND NOT ATTENDING STUDENTS
There will be a written exam and two homework assignments. The homework assignments are not mandatory.
The final grade will be calculated by taking for each student the best outcome out of the following two ones:
(a) Final written test contributes 70% of the final grade, and homework assignments contribute 30%.
(b) Final written test contributes 100% of the final grade.
The exam will test the students' ability to explain and reproduce the concepts learned in class, and connect these concepts to specific problem instances. There will be no difference between attending and non-attending students.
Teaching materials
ATTENDING AND NOT ATTENDING STUDENTS
- Lecture slides and notes provided by the instructor
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, (The MIT press), 3rd/4th edition
- W. Cook, W. Cunningham, W. Pulleyblank and A. Schrijver. Combinatorial Optimization. Wiley-Interscience, 1997
- B. Guenin, J. Könemann, L. Tuncel, A Gentle Introduction to Optimization, Cambridge University Press, 2014
- Computer and Intractability. A Guide to NP-Completeness. M. R. Garey and D. S. Johnson. Publisher W. H. Freeman, 1979
- Information Theory, Inference, and Learning Algorithms, D. J. C. MacKay, Cambridge University Press, 2003