Topics in Algorithms

Professor: Evanthia Papadopoulou
Instructor: Panagiotis Cheilaris
Assistant: Elena Khramtcova

Tipo di corso: Lecture
Valore in crediti ECTS: 3
Riferimenti bibliografici sul sito della biblioteca (CoRe)

Academic year 2012/2013 - Fall semester

Prerequisite: Algorithms and Data Structures

Objectives
This course will cover a variety of topics on algorithms and data structures, building upon the material of the course “Algorithms and Data Structures”. Algorithms and data structures are fundamental to computer science, as they are the essence of computer programs. They lie at the core of every complex computing system and the performance of any software system depends on the efficiency of its algorithms and data structures. When designing systems, it is essential to have good understanding of important applicable algorithmic tools and techniques. This course will extend the students knowledge on fundamental algorithms by focusing on several important topics.

Contents
The course will cover a variety of topics such as disjoint-sets data structures and the union-find algorithm, graphs and graph algorithms (for example, shortest paths computation), interval trees, randomized algorithms (Monte Carlo and Las Vegas algorithms) and their probabilistic analysis, intractability and NP completeness, how to deal with intractability, approximation algorithms.

Teachning mode
Lectures and exercises.

References
Main: Introduction to Algorithms, 3rd Edition, T. H. Cormen et al, the MIT Press, 2009.
Secondary references: Algorithms, S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, McGraw-Hill, 2006
Algorithm Design, Jon Kleinberg, Eva Tardos, Addison Wesley, 2005.