Discrete Algortihms

Course Description:

This course deals with advanced discrete algorithms. Topics are selected from Computational Geometry, Algorithmic Graph Theory and Computational Topology.

Credits: 4 ECTS

Prerequisites by Topics:

  • Computer programming

  • Mathematics & statistics

Course Objectives:

At the end of this course:

  • Students should be able to analyse new problems and come up with their own efficient solutions using concepts and techniques from the course.

  • Students should be able to decide which algorithm or data structure to use in order to solve a given geometric problem.

  • Students should know the basics of Graph drawing and routing techniques in geometric networks.

  • Students should have a general idea about robustness and numerical difficulties derived from geometric computing.

  • Students should know the significance and usefulness of topological concepts to solve problems in computer science and to find computer aided solutions to problems in different areas of science.

Topics Covered:

A general overview of the following topics is given and some of them are discussed in more detail depending on the students interests:

  • Geometric sorting and its applications.

  • Convex hulls.

  • Data structures and algorithms for space partitions.

  • Proximity graphs and Voronoi diagrams.

  • Spanners and routing strategies in geometric networks.

  • Introduction to Graph Drawing.

  • Fundamentals of topology.

  • Computational topology algorithms.

  • Digital topology algorithms for image processing.

Teaching staff:

  • Manuel Abellanas

  • Antonio Giraldo

  • Gregorio Hernández

Methods of Assessment:

  • Team projects

  • Oral presentation

Resources Commonly Available:

  • Bibliography

  • Open source software

  • Common hardware resources

Bibliography:

  • M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars:
    Computational Geometry: Algorithms and Applications (3rd edition).
    Springer-Verlag, Heidelberg, 2008.

  • G. Narasimhan, M. Smid: Geometric Spanner Networks, Cambridge Univ. Press, 2007

  • G. di Battista, P. Eades, R. Tamassia, I. Tollis: Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, 1999

  • A. J. Zomorodian: Topology for computing, Cambridge University Press, 2005