🚀 go-pugleaf

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

\item[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 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.