CSE 598PM: Applied Algorithms

Autumn 2000

Instructor: Anna R. Karlin (karlin@cs)

Office: Sieg 426C, 543-9344
Office Hours: Wednesday 9:20 -- 10pm, or by appointment.

Teaching Assistant: Ashish Sabharwal (ashish@cs)

Office Hours: Wednesday 5:30-6:20 Sieg 226B, or by appointment

Meeting Time:

Wednesday 6:30pm-9:20pm, EE1 003

Recommended Text Book :

The Algorithm Design Manual by Steven Skiena.

Another very useful textbook is T. Cormen, C. Leiserson, and R. Rivest. Introduction to Algorithms. MIT Press, Cambridge MA, 1990. Here is a document about the errata in the book.

I will also be drawing material from many other sources. I'll try to give you information about these as we go.

Course Overview:

My goal in teaching this course is help you become better prepared to tackle algorithm design for "real-world" problems. This includes (1) understanding fundamental algorithmic techniques and the tradeoffs involved in designing correct, efficient and implementable algorithms, and (2) knowing how to model and abstract messy real-world problems into clean problems that can be attacked using known paradigms or specific algorithms. More generally, I hope you will gain a greater appreciation of the beauty and elegance of algorithms as well as where they are used in the real world.

Tentative Topics :

Stable Marriage

Graph Algorithms

Maximum Flow and Minimum Cost Flow

Linear Programming

Hashing

Self-adjusting Data Structures

Cryptography

Combinatorial Search and Heuristic Methods (eg. simulated annealing, local search, branch and bound)

Clustering, Indexing and Search Engines

Grading :

Weekly problem sets 50%
Final 50%

Mailing List and Threaded Archives

We will be using a mailing list for administrative and instructional purposes.

To subscribe to the list, send email to majordomo@cs.washington.edu with the single line in the message body (not the subject):

subscribe cse589

To send mails to the class, send them to cse589@cs.washington.edu.