CS 573: Graduate Algorithms

A collection of class notes for the course "473G/573 Graduate Algorithms" taught in the University of Illinois, Urbana-Champaign. Includes NP-Completeness, dynamic programming, approximation algorithms, randomized algorithms and linear programming.

**Tag(s):**
Algorithms and Data Structures

**Publication date**: 30 Dec 2014

**ISBN-10**:
n/a

**ISBN-13**:
n/a

**Paperback**:
273 pages

**Views**: 8,639

**Type**: Lecture Notes

**Publisher**:
n/a

**License**:
Creative Commons Attribution-NonCommercial 3.0 Unported

**Post time**: 20 Oct 2016 09:00:00

CS 573: Graduate Algorithms

A collection of class notes for the course "473G/573 Graduate Algorithms" taught in the University of Illinois, Urbana-Champaign. Includes NP-Completeness, dynamic programming, approximation algorithms, randomized algorithms and linear programming.

You are free to:

Share — copy and redistribute the material in any medium or format

Adapt — remix, transform, and build upon the material

The licensor cannot revoke these freedoms as long as you follow the license terms.

Click**here** to read the full license.

Share — copy and redistribute the material in any medium or format

Adapt — remix, transform, and build upon the material

The licensor cannot revoke these freedoms as long as you follow the license terms.

Click

Note:

More resources (including slides) are available here:

Excerpts from the Preface:

More resources (including slides) are available here:

Excerpts from the Preface:

Har-Peled wrote:This manuscript is a collection of class notes for the (no longer required graduate) course “473G/573 Graduate Algo- rithms” taught in the University of Illinois, Urbana-Champaign, in (1) Spring 2006, (2) Fall 07, (3) Fall 09, (4) Fall 10, (5) Fall 13, and (6) Fall 14.

Class notes for algorithms class are as common as mushrooms after a rain. I have no plan of publishing these class notes in any form except on the web. In particular, Jeff Erickson has class notes for 374/473 which are better written and cover some of the topics in this manuscript (but naturally, I prefer my exposition over his).

My reasons in writing the class notes are to (i) avoid the use of a (prohibitly expensive) book in this class, (ii) cover some topics in a way that deviates from the standard exposition, and (iii) have a clear description of the material covered. In particular, as far as I know, no book covers all the topics discussed here. Also, this manuscript is available (on the web) in more convenient lecture notes form, where every lecture has its own chapter.

Most of the topics covered are core topics that I believe every graduate student in computer science should know about. This includes NP-Completeness, dynamic programming, approximation algorithms, randomized algorithms and linear programming. Other topics on the other hand are more optional and are nice to know about. This includes topics like network flow, minimum-cost network flow, and union-find. Nevertheless, I strongly believe that knowing all these topics is useful for carrying out any worthwhile research in any subfield of computer science.

Tweet

About The Author(s)

Sariel Har-Peled is a Professor in the Department of Computer Science at University of Illinois at Urbana-Champaign. His main field of research is Computational Geometry, and he is also interested in clustering and learning.

Book Categories

Computer Science
Introduction to Computer Science
Introduction to Computer Programming
Algorithms and Data Structures
Artificial Intelligence
Computer Vision
Machine Learning
Neural Networks
Game Development and Multimedia
Data Communication and Networks
Coding Theory
Computer Security
Information Security
Cryptography
Information Theory
Computer Organization and Architecture
Operating Systems
Image Processing
Parallel Computing
Concurrent Programming
Relational Database
Document-oriented Database
Data Mining
Big Data
Data Science
Digital Libraries
Compiler Design and Construction
Functional Programming
Logic Programming
Object Oriented Programming
Formal Methods
Software Engineering
Agile Software Development
Information Systems
Geographic Information System (GIS)

Mathematics
Mathematics
Algebra
Abstract Algebra
Linear Algebra
Number Theory
Numerical Methods
Precalculus
Calculus
Differential Equations
Category Theory
Proofs
Discrete Mathematics
Theory of Computation
Graph Theory
Real Analysis
Complex Analysis
Probability
Statistics
Game Theory
Queueing Theory
Operations Research
Computer Aided Mathematics

Supporting Fields
Web Design and Development
Mobile App Design and Development
System Administration
Cloud Computing
Electric Circuits
Embedded System
Signal Processing
Integration and Automation
Network Science
Project Management

Operating System
Programming/Scripting
Ada
Assembly
C / C++
Common Lisp
Forth
Java
JavaScript
Lua
Rexx
Microsoft .NET
Perl
PHP
R
Python
Rebol
Ruby
Scheme
Tcl/Tk

Miscellaneous
Sponsors