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
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.
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…
Interactive lectures both for theory and exercises. Attendance is required.
Algorithm Design, J. Kleinberg and E. Tardos, Addison-Wesley 2005
Introduction to Algorithms, 2nd Edition, T. H. Cormen et al., The MIT Press, 2001