CMSC 651: Advanced Algorithms
Catalog Description:
Techniques for the design and analysis of algorithms and data
structures. Study of efficient algorithms from areas
such as graph theory, networks, pattern matching, geometry,
integer and polynomial arithmetic.
Understanding of the inherent complexity of problems:
polynomial time, NP-completeness and approximation algorithms.
The following broad aims will be attempted.
- Understanding techniques to design and analyse data structures.
These will find applications in combinatorial algorithms that we study.
- Learning and designing efficient algorithms for basic graph theoretic
problems that are used as building blocks elsewhere. These
include shortest paths, minimum spanning trees, matching, flow etc.
- An understanding of the inherent complexity of problems:
Polynomial time, NP-completeness, Approximation Algorithms etc.
Prerequisites:
CMSC 451 or an equivalent course.
Topics:
The topics listed below give a general idea about the course content.
- Advanced Data Structures (splay trees, F-heaps, union-find,
amortized analysis).
- Graph Algorithms (minimum spanning trees, shortest paths,
light approximate shortest path trees, spanners, flows, matchings). .
- NP-completeness (Cook's theorem, reductions).
- Approximation Algorithms (set cover, vertex cover, bin packing,
traveling salesman, optimal location problems).
Texts:
-
Thomas Cormen, Charles Leiserson, Ron Rivest,
Introduction to Algorithms, McGraw Hill and MIT Press, 1990.
-
Robert Tarjan,
Data Structures and Network Algorithms, SIAM, 1983.
We use the first text only for the advanced data structures part of the
course. We will cover a lot of material from Tarjan's book, as well
as from research papers.
Course Work:
Course work will consist of homework assignments (approximately 6),
one in-class midterm
and a comprehensive final. Homework problems will be mathematically oriented.
Grading:
Homeworks: 30%
Midterm: 30%
Final: 40%
