20602 - COMPUTER SCIENCE (ALGORITHMS)
Department of Decision Sciences
Course taught in English
Go to class group/s: 31
Course Director:
RICCARDO ZECCHINA
RICCARDO ZECCHINA
Lezioni della classe erogate in presenza
Prerequisites
Prerequisites: To feel comfortable in this course you should have a good knowledge of calculus, statistics, and probability theory.
Mission & Content Summary
MISSION
Scope of the course is to provide the basic conceptual tools at the root of basic classes of optimization and sampling algorithms.
These notions and method which are extensively used in subsequent courses of the education program.
CONTENT SUMMARY
- Review of complexity theory and approximation schemes.
- Optimization algorithms: Linear Programming and integer Programming.
- Dynamics 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 chemes 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 | |
|---|---|---|---|
|
x |
ATTENDING AND NOT ATTENDING STUDENTS
The exam consists of a single written problem solving exercise. The students are asked to formulate rigorously an optimization problem and provide a detailed description of the algorithmic solution of choice.
The results are used to assess both the "knowledge and understanding" and the "applying knowledge and understanding" learning objectives.
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.
Last change 10/07/2018 11:20