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
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.
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.
Lectures and exercises.
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.