Università di Lugano. University of Lugano. Scegli la lingua. Choose the language.

Welcome to the University of Lugano. This web site has been developed with two content access modalities: visual and oral.

You are now browsing with the visual modality. If you are listening to the web site, you can change the modality and access the oral one, following the next link.

Access to the oral modality of the web site.

CH-6904 Lugano (Svizzera)
Tel. +41 (0)58.666.4000
Fax +41 (0)58.666.4647
info@usi.ch

Home
People directory

Algorithms and Complexity

Professor: Monaldo Mastrolilli
Assistant: Georgios Stamoulis

Course type: Lecture
Value in ECTS: 6
Bibliographic references available on the University Library website

Academicyear 2012/2013 - Fall semester

Objectives
Algorithms are fundamental to computer science and software engineering. An important part of computing is the ability to select algorithms appropriate to particular purposes and to apply them, recognizing the possibility that no suitable algorithm may exist. Efficiency is a pervasive theme throughout this area. The goal of this course is to develop algorithm designanalysis techniques by drawing on problems from across many areas of computer science and related fields (systems and network, computer vision, operations research, computational biology, data mining, etc…). The notion of computational intractability, and NP-completeness in particular, plays an important role. Some of the time, an interesting problem arising in an application area will be amenable to an efficient solution, and some of the time it will be provably NP-complete; in order to fully address a new algorithmic problem, one should be able to explore both of these options with equal familiarity. The discovery that a problem is NPcomplete should not be taken as the end of the story, but as an invitation to begin looking for approximation algorithms, heuristic local search techniques, or tractable special cases. We include extensive coverage of each of these three approaches.

Contents
Analysis of algorithms. Algorithm design for tractable problems: maximumflow, linear programming. Survey of NP-complete problems, reductions. Approximation algorithm design for intractable problems: approximation algorithms with provable bounds, local search, randomized algorithms. Applications: scheduling, bin-packing, minimum spanning tree, bipartite matching, clustering, vertex cover, traveling salesman, Steiner trees, etc…

Teaching mode
Interactive lectures both for theory and exercises. Attendance is required.

References
Algorithm Design, J. Kleinberg and E. Tardos, Addison-Wesley 2005
Introduction to Algorithms, 2nd Edition, T. H. Cormen et al., The MIT Press, 2001