CSE 598PM: Applied Algorithms

Autumn 1997

Instructor: Anna R. Karlin (karlin@cs)

Teaching Assistants:

Meeting Time:

Wednesday 6:30pm-9:20pm, Sieg 134

Special Request:

Please come to Sieg 134 for class on Wednesday October 8. We'd like to have the opportunity to meet face to face at least once. Pizza will be provided!

Important Announcement:

CLASS ON OCTOBER 22 IS CANCELLED.

Recommended Text Book :

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

Another very nice textbook, that is unfortunately not yet available, is The Algorithm Design Manual by Steven Skiena.

I will also be drawing material from many other sources. Many of these books will be on reserve in the Engineering Library.

Scribe System:

We will be instituting a scribe system. For each lecture, a group of 3-4 students will take notes and format them in LaTex or HTML. You are encouraged to augment and clarify material presented in class. Our hope is to have a dynamite set of notes at the end of the quarter.

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 :

  • Dynamic Programming
  • Graph Algorithms
  • Maximum Flow and Minimum Cost Flow
  • Linear Programming and Integer Programming
  • Hashing
  • Cryptography
  • Combinatorial Search and Heuristic Methods (eg. simulated annealing, local search, branch and bound)
  • Data Compression
  • Pattern matching
  • Clustering, Indexing and Search Engines

  • Grading :


    Mailing List and Threaded Archives

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