🚀 go-pugleaf

CMSC 651 is not listed on the course schedule that the Graduate and
Undergraduate offices have been handing out. We wanted to be sure that you
were aware of the class being offered:

CMSC 651: Advanced Algorithms
	  FALL 1999
          Class time MW 11-12:15pm, CLB 0109


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 etc.
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.


\item[Prerequisites:]
CMSC 451 or an equivalent course.

\item[Topics:]
The topics listed below give a general idea about the course content.

	Advanced Data Structures (splay trees, F-heaps, union-find).
	
	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, scheduling).
	
	Other random topics...

\item[Texts:]
Thomas Cormen, Charles Leiserson, Ron Rivest, 
{\sl Introduction to Algorithms}, McGraw Hill and MIT Press, 1990.

Robert Tarjan,
{\sl 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 and lecture notes.

\item[Course Work:]
Course work will consist of homework assignments (approximately 4), 
one in-class midterm and a comprehensive final.