Catalog Course Description

Rationale

Computational complexity focuses on the existence or non-existence of efficient algorithms to certain classes of problems. The complexity of several non-traditional types of algorithms such as parallel or randomized algorithms, as well as the analysis of approximation algorithms to a number of practical problems are also important research areas. These topics of theoretical computer science have proven to be widely applicable to many real-world combinatorial problems in operations research, engineering and many other disciplines. This course will provide students and researchers with the necessary tools for the analysis of problems, the design of efficient algorithms (when possible), and the design and analysis of alternative methods such as approximation algorithms for computationally intractable problems.

Objectives

At the end of the course, the student should be able to:

• identify decision problems for which efficient algorithms exist;
• design efficient algorithms (when possible) for some decision problems; and
• design and analyze alternative solutions when efficient algorithms are proven to be non-existent.