CSCE 629: Analysis of Algorithms

Fall 2012

Algorithm design and analysis is a fundamental and important part of computer science. This course introduces students to advanced techniques for the design and analysis of algorithms, and explores a variety of applications.

The topics and applications that we tentatively plan to cover include greedy algorithms, network algorithms and network design, huffman codes and data compression, NP-hardness, approximation and randomized algorithms. Enroute, we will encounter various useful ideas, including randomization, probabilistic analysis, amortized analysis, competitive analysis, eigenvalues, linear and semi-definite programming, high dimensional geometry, and random walks.


Course Information

Course Outline

There is a dynamic component to the course, as topics drop in and out, or get longer or shorter treatment, depending on audience interest/reaction/resistence. Given this, here is a rough outline of the course material:


The lecture notes below, except otherwise stated, are from the course Advanced Algorithms by Shuchi Chawla.
Abbreviations: K&T=Kleinberg & Tardos

Online Resources

LaTeX: Feel free to use the following template for writing your assignments in LaTeX. The template contains commands for Theorem, Lemma, Corollary, Proposition, Claim, Definition, Construction, Remark etc. An example file where this template is used is here which results in the following pdf.

Similar classes at other universities: