Course 2024-2025 a.y.

20874 - ALGORITHMS FOR OPTIMIZATION AND INFERENCE

Department of Computing Sciences

Course taught in English

Class timetable
Exam timetable
Go to class group/s: 29
AI (8 credits - I sem. - OB  |  INF/01)
Course Director:
LAURA SANITA'

Classes: 29 (I sem.)
Instructors:
Class 29: LAURA SANITA'


Mission & Content Summary

MISSION

The course will teach the students the fundamentals of designing and analyzing algorithms for optimization and inference problems. The students will be able to estimate the computational complexity and the resource requirements of the algorithms they encounter, and to use them as building blocks in their own work. They will be familiarized with fundamental algorithmic theory and optimization techniques, and their interplay with inference and learning methods.

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

At the end of the course student will be able to...
  • 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

At the end of the course student will be able to...
  • 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
  • Written individual exam (traditional/online)
    x
  • Individual Works/ Assignment (report, exercise, presentation, project work etc.)
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

 

Last change 24/07/2024 10:19