Insegnamento a.a. 2019-2020

20602 - COMPUTER SCIENCE (ALGORITHMS)

Department of Decision Sciences

Course taught in English
Go to class group/s: 31
DSBA (6 credits - II sem. - OBCUR  |  FIS/02)
Course Director:
RICCARDO ZECCHINA

Classes: 31 (II sem.)
Instructors:
Class 31: RICCARDO ZECCHINA


Lezioni della classe erogate in presenza

Suggested background knowledge

To feel comfortable in this course you should have a good knowledge of calculus, statistics, probability theory and programming.

Mission & Content Summary

MISSION

Scope of the course is to provide the conceptual tools at the root of basic classes of optimization and sampling algorithms. These notions and method are extensively used in subsequent courses of the education program.

CONTENT SUMMARY

  • Review of graph theory.
  • Review of complexity theory and approximation schemes.
  • Optimization algorithms: Linear Programming and integer Programming.
  • Dynamic programming.
  • Randomized algorithms for optimization.
  • Monte Carlo Markov Chains for sampling and optimization.
  • Stochastic programming, multi stage optimization.
  • On-line algorithms over networks.

Intended Learning Outcomes (ILO)

KNOWLEDGE AND UNDERSTANDING

At the end of the course student will be able to...
  • Understand the basic notions of approximation algorithms.
  • Analyze the structure of advanced algorithmic schemes for optimization and sampling.
  • Illustrate the role of randomness in optimization.
  • Master the basic notions of on-line algorithms.

APPLYING KNOWLEDGE AND UNDERSTANDING

At the end of the course student will be able to...
  • Develop algorithms for large scale difficult optimization problerms.

Teaching methods

  • Face-to-face lectures

DETAILS

Lectures.


Assessment methods

  Continuous assessment Partial exams General exam
  • Oral individual exam
    x

ATTENDING AND NOT ATTENDING STUDENTS

The exam consists of a presentation and questions. The presentation can be either about a specific topic related to the course content, or about a project that the students complete before the exam. Several possible topics and projects will be proposed and students can also suggest also their own ideas. The questions will be about the presentation and related topics that were covered in class.


Teaching materials


ATTENDING AND NOT ATTENDING STUDENTS

  • T.H. CORMEN, C.E. LEISERSON, R.L. RIVEST, et al., Introduction to Algorithms, MIT, 3rd edition.
  • C. MOORE, S. MERTENS, The Nature of Computation, Oxford.
  • R. MOTWANI, P. RAGHAVAN, Randomized algorithms, Cambridge University Press New York, NY, USA.
  • D. BERTSEKAS, Nonlinear programming, Athena Scientific, 3rd edition.
  • Lecture notes by the instructors.
Last change 05/06/2019 22:28